Re: considering only interpretations with small domains in RDF entailment

Yes indeed, most ingenious. We could phrase this as the number of names in the skolemization of the entailing graph, I guess, or the number of distinct referring expressions in the syntax, but its probably not worth trying to state it the second way. 

I will try re-drafting that appendix. 

BTW, do you have any insight onto whether 

_:x rdf:type ddd .

is RDFS valid when ddd is a recognized datatype?  In effect, this outlaws datatypes with empty value sets. This seems to me to be a reasonable assumption, but I wonder if it is universal. 

Pat

On May 22, 2013, at 9:43 AM, Peter F. Patel-Schneider wrote:

> 
> There is the claim in the current version of RDF 1.1 Semantics (and
> elsewhere, I think - pointers into the literature would be helpful) that 
> for several variations of RDF entailment, it
> suffices to consider interpretations where the size of the domain is at most
> the number of names (IRIs plus literals) plus one.   This is not correct.
> 
> Consider, for example, the following situation:
> 1/ Pick n > 1, m > 0 such that nn = m.  
> 2/ Pick n distinct IRIs, I1, ..., In, without any special significance in
>   any RDF-related entailment.
> 3/ Pick m-n distinct bnodes, bn+1, ..., bm.
> 4/ Let Ni be Ii for 0<i<=n; bi for n<i<=m.
> 5/ Construct the RDF graph G containing the following triples
> 	<Ni,Ij,Ik>
>   for each 0<i<=m and each 0<j,k<=n except when j+n(k-1)=i, i.e., each Ni
>   has m-1 out of m triples for which it is the subject, but each Ni is
>   missing a different combination of the predicate and object.
> 6/ Construct G' as the following triples
> 	<b,Ij,Ik>
>   for b distinct from each bnode in G and for each 0<j,k<=n 
> 
> Then G does not entail G', as can easily be seen in a Herbrand-like (i.e.,
> also adding domain elements for each blank node) interpretation for G.  
> However, in an interpretation with fewer than m elements some No and Np with
> o/=p must end up denoting the same domain element, which then acts as the
> subject of facts for every combination of Ii as predicate and Ij as object
> (speaking a bit loosely here). In such interpretations G' is thus
> true, demonstrating that in some cases interpretations with domains of size at least
> the number of IRIs plus the number of blank nodes in the entailing graph
> must be considered.
> 
> Literals from uninterpreted datatypes can also increase this lower bound.
> 
> When recognized datatypes are present the above constructions can be
> relativized to each datatype, providing a bound on the minimum interpreted
> size of large (particularly infinite) datatypes that must be considered.
> 
> 
> peter
> 

------------------------------------------------------------
IHMC                                     (850)434 8903 or (650)494 3973   
40 South Alcaniz St.           (850)202 4416   office
Pensacola                            (850)202 4440   fax
FL 32502                              (850)291 0667   mobile
phayesAT-SIGNihmc.us       http://www.ihmc.us/users/phayes

Received on Wednesday, 22 May 2013 22:21:53 UTC