Abstract
This paper extends the model theory of RDF with rules, placing an emphasis on integration with OWL and decidability of entailment. We start from an abstract syntax that views a rule as a pair of rule graphs which generalize RDF graphs by also allowing rule variables in subject, predicate and object positions. We include RDFS as well as a decidable part of OWL that weakens D-entailment and OWL Full. Classes can be used as instances. Almost all examples in the DAML set of test rules are covered by our approach.
For a set of rules R, we define a general notion of R-entailment. Extending earlier results on RDFS and OWL, we prove a general completeness result for R-entailment. This result shows that a restricted form of application of rules that introduce blank nodes is sufficient to determine R-entailment. For rules that do not introduce blank nodes, we prove that R-entailment and R-consistency are decidable and in PSPACE. For rules that do not introduce blank nodes and that satisfy a bound on the size of rule bodies, we prove that R-consistency is in P, that R-entailment is in NP, and that R-entailment is in P if the target RDF graph is ground.
Chapter PDF
Similar content being viewed by others
References
Baader, F., et al. (eds.): The Description Logic Handbook, Cambridge (2003)
Berners-Lee, T., Hawke, S., Connolly, D.: Semantic Web Tutorial Using N3 (May 2004), http://www.w3.org/2000/10/swap/doc/
Cadoli, M., Palopoli, L., Lenzerini, M.: Datalog and Description Logics: Expressive Power. In: Cluet, S., Hull, R. (eds.) DBPL 1997. LNCS, vol. 1369, pp. 281–298. Springer, Heidelberg (1998)
Dantsin, E., Eiter, T., Gottlob, G., Voronkov, A.: Complexity and Expressive Power of Logic Programming. ACM Computing Surveys 33, 374–425 (2001)
Donini, F.M., Lenzerini, M., Nardi, D., Schaerf, A.: \(\mathcal{AL}\)-log: Integrating Datalog and Description Logics. Journal of Intelligent Information Systems 10, 227–252 (1998)
Grant, J., Beckett, D. (eds.): RDF Test Cases, W3C Recommendation, (February 10, 2004), http://www.w3.org/TR/2004/REC-rdf-testcases-20040210/
Grosof, B., Horrocks, I., Volz, R., Decker, S.: Description Logic Programs: Combining Logic Programs with Description Logic. In: Proceedings of the 12th International Conference on the World Wide Web (WWW 2003), pp. 48–57 (2003)
Hayes, P. (ed.): RDF Semantics, W3C Recommendation (February 10, 2004), http://www.w3.org/TR/2004/REC-rdf-mt-20040210/
Horrocks, I., Patel-Schneider, P.F.: Reducing OWL Entailment to Description Logic Satisfiability. Journal of Web Semantics 1, 345–357 (2004)
Horrocks, I., Patel-Schneider, P.F., Bechhofer, S., Tsarkov, D.: OWL Rules: A Proposal and Prototype Implementation. J. Web Semantics 3, 23–40 (2005)
ter Horst, H.J.: Extending the RDFS Entailment Lemma. In: McIlraith, S.A., Plexousakis, D., van Harmelen, F. (eds.) ISWC 2004. LNCS, vol. 3298, pp. 77–91. Springer, Heidelberg (2004)
ter Horst, H.J.: Completeness, Decidability and Complexity of Entailment for RDF Schema and a Semantic Extension Involving the OWL Vocabulary, Revised and extended version of [11]. Journal of Web Semantics 3, 79–115 (2005)
Klyne, G., Carroll, J. (eds.): Resource Description Framework (RDF): Concepts and Abstract Syntax, W3C Recommendation (February 10, 2004), http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/
Levy, A.Y., Rousset, M.-C.: Combining Horn Rules and Description Logics in CARIN. Artificial Intelligence 104, 165–209 (1998)
Motik, B., Sattler, U., Studer, R.: Query Answering for OWL-DL with Rules. Journal of Web Semantics 3, 41–60 (2005)
Patel-Schneider, P.F., Hayes, P., Horrocks, I. (eds.): OWL Web Ontology Language Semantics and Abstract Syntax, W3C Recommendation (February 10, 2004), http://www.w3.org/TR/2004/REC-owl-semantics-20040210/
Rosati, R.: On the Decidability and Complexity of Integrating Ontologies and Rules. Journal of Web Semantics 3, 61–73 (2005)
RDF Data Access Working Group, W3C, http://www.w3.org/2001/sw/DataAccess/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
ter Horst, H.J. (2005). Combining RDF and Part of OWL with Rules: Semantics, Decidability, Complexity. In: Gil, Y., Motta, E., Benjamins, V.R., Musen, M.A. (eds) The Semantic Web – ISWC 2005. ISWC 2005. Lecture Notes in Computer Science, vol 3729. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11574620_48
Download citation
DOI: https://doi.org/10.1007/11574620_48
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29754-3
Online ISBN: 978-3-540-32082-1
eBook Packages: Computer ScienceComputer Science (R0)