considering only interpretations with small domains in RDF entailment

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

Received on Wednesday, 22 May 2013 14:44:22 UTC