The details of reasoning in RDF [2] and RDFS [1] are generally well known. There is a model-theoretic semantics for RDF [3, 4] and there are sound and complete proof theories for RDF without datatypes [6]. However, the model-theoretic characteristics of RDF3 have been less studied, particularly when datatypes are added. We show that RDF reasoning can be performed by only considering nite models or pre-models, and sometimes only very small models need be considered. Ter Horst [6] does de ne Herbrand models for RDF and RDFS, providing the basis for some model-theoretic characteristics of RDF and RDFS, but he does not provide a full analysis of RDF datatypes, analyzing instead an incomplete semantics for datatypes that is easier to reason in. As well, the recent minor modi cations to the semantics of RDF [4], while cleaning up some aspects of entailment in RDF, do make some technical changes that might appear to interfere with nite model-based reasoning in RDF. An analysis of nite models for RDF shows that the modi ed semantics does not introduce any unintended changes to reasoning in RDF. As well, it provides insights into the modeling strength of RDF, particularly when blank nodes are not present, and illustrates how nite datatypes interact with the rest of RDF.
axioms, except that no container membership property not occurring in the graph is an identi er for the graph.
We then build some models for the RDF graph as follows.4 We start with the data values for the recognized datatypes. For every identi er that is not a literal with a recognized datatype we nondeterministically either nondeterministically choose some data value as its denotation or add a new domain element as its denotation. This results in denotation functions where identi ers that do not denote data values all denote di erent domain elements. For IRIs and literals with unrecognized datatypes that are not identi ers of the graph we add two extra domain elements, one being the denotation of the container membership properties that are not identi ers for the graph and one being the denotation of all other identi ers. We then build up the rest of the semantic structure using the graph and the axioms and rules of inference from ter Horst augmented with axioms for datatypes and co-denoting identi ers, resulting in a structure like a datatype-aware Herbrand interpretation except that some non-literal identi ers might denote data values.
Some of these denotation functions might fail to produce an interpretation because some datatype domain or range restriction requires a domain element to be a data value for a particular datatype when it is not. However, if there is a model for the RDF graph, then this construction will produce at least one model, because there are no semantic conditions in RDF that require a particular denotation for an identi er or require or prohibit co-denotation between identi ers except those related to data values and we have not constrained data value denotations here except for non-identi ers.
So for every satis able RDF graph we have ended up with a set of models. We now need to show that any model of the graph is at least as strong as one of these models. For a particular set of denotations the inference rules produce the weakest possible model. Now consider the extra domain element added for unmentioned container membership properties. Replicating this domain element and splitting denotations produces a model that has the same strength as the original model because the RDF semantic conditions treat all these domain elements the same and identity cannot be detected. Similarly replicating the other additional domain element produces a model of the same strength. Because there is no inequality in RDF, identifying any two domain elements always produces model that is at least as strong, if it produces a model at all. Thus the restriction that denotations that are not data values be unique produces the weakest possible models.
In these models all the data values in a datatype that are not the denotation of some identi er have exactly the same characteristics. A pre-model can thus be constructed that collapses all these data values into one, nally resulting in nite model reasoning for RDF. (The result is, of course, not generally a model because it violates the semantic conditions on the denotation of literals.) A completely nite semantic structure can be constructed by simply ignoring these denotation mappings and the mappings for other non-identi ers. 4 For purposes of space some shortcuts in notation will be taken throughout this paper.
In the absence of recognized datatypes, the above construction results in unique Herbrand models just like the ones in ter Horst. In the presence of recognized datatypes this construction is di erent from that in ter Horst, as it captures the full meaning of datatypes, including the requirement to consider several models. For example, consider a datatype with only two data values, say ex:two, and the RDF graph ex:p rdf:range ex:two.
ex:a ex:p ex:u, ex:v. ex:b ex:p ex:u, ex:w. ex:c ex:p ex:v, ex:w. This RDF graph entails :x ex:p ex:u, ex:v, ex:w. To determine entailment in these situations more than one model must be considered, hence the choice of values in the graph above.
If datatypes have su cient data values of the right kind, however, then it is possible to only consider models that are more like Herbrand models. Given a nite set of recognized datatypes D and E a subset of D, let the unconstrained portion of E be the elements of the intersection of the data spaces for each e in E that are not in any other datatype in E that is not a superset of the intersection. Consider two RDF graphs A and B and a set of recognized datatypes D. If the unconstrained portion of every E, a non-empty subset of D, is of size greater than the number of data values in it denoted by literals in A and B plus the number of identi ers in A that are not literals with recognized datatypes plus one then it is possible to always choose unconstrained elements when picking data values for identi ers that are not literals with recognized datatypes. Then all such identi ers will have di erent denotations, and di erent denotations from all literals. This in turn permits the determination of the datatypes that the denotation of an identi er must belong to by using the D* rules of ter Horst. Then when determining the denotation of an identi er, if this set is empty add a new domain element and otherwise pick an unconstrained value for this set. This results in a single, nite model that can be used for reasoning. Note, however, that the presence of even a single too-small unconstrained portion may require examining multiple models.
So we have shown that RDF reasoning can be done by considering only models of the size of the RDF graph. Is it possible to consider only very small models? (Datatypes make these considerations even more complex, so this section of the paper will ignore datatypes.) If RDF had disjunction, then it would not be possible to signi cantly shrink the minimum size of considered models. For example, consider RDF graphs containing n triples of the form
Si S1 Si. for 1 <= i <= n.
In any model with less than n domain elements, there is some 1 i 6= j n such that Si and Sj have the same denotation. In this model Si S1 Sj . is true and so in any such model the disjunction of all these triples is true, which is not a valid entailment.
Even with RDF lacking disjunctions, it is possible to show that very small models are not adequate. Consider RDF graphs containing triples of the form Si S1 Sj . for 1 n. In any model with less than n domain elements, there is some 1 i 6= j n such that Si and Sj have the same denotation, which is then related to the denotation of each of the Si by the denotation of S1, so the graph containing :x S1 Sj . for 1 <= i <= n, is true in each of these models, but this graph is not entailed. Therefore considering only models of this size or smaller is not su cient.
If we only consider entailments with no blank nodes in the entailed graph then smaller models su ce. Consider an interpretation I (for RDF or RDFS without any recognized datatypes) containing two domain elements e1 and e2 that are neither properties nor classes (call these domain elements ordinary). Form I0 from I by simply replacing e1 and e2 with a single domain element e throughout. Then I0 is an interpretation, which can be determined by examining all the appropriate semantic conditions.
So for B1 and B1 identi ers whose denotation in I are neither e1 nor e2, I0 supports any triple of the form B1 P B2., if and only if I supports the triple. For any particular such triple this process can be repeated until only three ordinary domain elements remain. Considering all such shrunken interpretations is adequate to rule out any invalid entailments, so we need only consider models with three ordinary domain elements, but of course we need to consider many interpretations. The ability to have such small models and to then only consider them shows how weak RDF is as a logic.
We have argued that RDF reasoning can be done by only considering nite models, even in the presence of datatypes. The exact size and number of the models that need to be considered depends on a number of factors, including which recognized datatypes are involved, but generally models of size at least the number of identi ers in the graph must be considered. If there are no datatypes or the datatypes are of su cient size, then a single Herbrand-like model is all that need be considered. If there are no blank nodes in the entailed graph, then much smaller models su ce, although multiple models must then be considered.