Logical Foundations of RDF(S) with Datatypes
This addresses foundational complexity issues for Semantic Web standards, providing insights into the computational limits of RDF reasoning, though it is incremental in extending prior logical embeddings.
The paper tackles the problem of reasoning with RDF and its extensions with datatypes by embedding RDF in logic, establishing novel complexity bounds: RDFS entailment is PTime-complete and simple-D entailment is coNP-hard in graph size.
The Resource Description Framework (RDF) is a Semantic Web standard that provides a data language, simply called RDF, as well as a lightweight ontology language, called RDF Schema. We investigate embeddings of RDF in logic and show how standard logic programming and description logic technology can be used for reasoning with RDF. We subsequently consider extensions of RDF with datatype support, considering D entailment, defined in the RDF semantics specification, and D* entailment, a semantic weakening of D entailment, introduced by ter Horst. We use the embeddings and properties of the logics to establish novel upper bounds for the complexity of deciding entailment. We subsequently establish two novel lower bounds, establishing that RDFS entailment is PTime-complete and that simple-D entailment is coNP-hard, when considering arbitrary datatypes, both in the size of the entailing graph. The results indicate that RDFS may not be as lightweight as one may expect.