Article

Combining RDF and part of OWL with rules: semantics, decidability, complexity

Author:

Herman J. ter HorstAuthors Info & Claims

ISWC'05: Proceedings of the 4th international conference on The Semantic Web

Pages 668 - 684

https://doi.org/10.1007/11574620_48

Published: 06 November 2005 Publication History

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.

References

[1]

F. Baader et al. (Eds.), The Description Logic Handbook, Cambridge, 2003.

Digital Library

[2]

T. Berners-Lee, S. Hawke, D. Connolly, Semantic Web Tutorial Using N3, May 2004, http://www.w3.org/2000/10/swap/doc/.

[3]

M. Cadoli, L. Palopoli, M. Lenzerini, Datalog and Description Logics: Expressive Power, Proceedings of the 6th International Workshop on Database Programming Languages (DBPL1997), pp. 281-298, 1997.

Digital Library

[4]

E. Dantsin, T. Eiter, G. Gottlob, A. Voronkov, Complexity and Expressive Power of Logic Programming, ACM Computing Surveys, 33 (2001) 374-425.

Digital Library

[5]

F.M. Donini, M. Lenzerini, D. Nardi, A. Schaerf, AL-log: Integrating Datalog and Description Logics, Journal of Intelligent Information Systems, 10 (1998) 227-252.

Digital Library

[6]

J. Grant, D. Beckett (Eds.), RDF Test Cases, W3C Recommendation, 10 February 2004, http://www.w3.org/TR/2004/REC-rdf-testcases-20040210/.

[7]

B. Grosof, I. Horrocks, R. Volz, S. Decker, Description Logic Programs: Combining Logic Programs with Description Logic, Proceedings of the 12th International Conference on the World Wide Web (WWW2003), pp. 48-57, 2003.

Digital Library

[8]

P. Hayes (Ed.), RDF Semantics, W3C Recommendation, 10 February 2004, http://www.w3.org/TR/2004/REC-rdf-mt-20040210/.

[9]

I. Horrocks, P.F. Patel-Schneider, Reducing OWL Entailment to Description Logic Satisfiability, Journal of Web Semantics 1 (2004) 345-357.

Digital Library

[10]

I. Horrocks, P.F. Patel-Schneider, S. Bechhofer, D. Tsarkov, OWL Rules: A Proposal and Prototype Implementation, J. Web Semantics 3 (2005) 23-40.

Digital Library

[11]

H.J. ter Horst, Extending the RDFS Entailment Lemma, Proceedings 3rd Int. Semantic Web Conference (ISWC2004), Springer LNCS 3298, pp. 77-91, 2004.

[12]

H.J. ter Horst, 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 (2005) 79-115.

Digital Library

[13]

G. Klyne, J. Carroll (Eds.), Resource Description Framework (RDF): Concepts and Abstract Syntax, W3C Recommendation, 10 February 2004, http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/.

[14]

A.Y. Levy, M.-C. Rousset, Combining Horn Rules and Description Logics in CARIN, Artificial Intelligence 104 (1998) 165-209.

Digital Library

[15]

B. Motik, U. Sattler, R. Studer, Query Answering for OWL-DL with Rules, Journal of Web Semantics 3 (2005) 41-60.

Digital Library

[16]

P.F. Patel-Schneider, P. Hayes, I. Horrocks (Eds.), OWL Web Ontology Language Semantics and Abstract Syntax, W3C Recommendation, 10 February 2004, http://www.w3.org/TR/2004/REC-owl-semantics-20040210/.

[17]

R. Rosati, On the Decidability and Complexity of Integrating Ontologies and Rules, Journal of Web Semantics 3 (2005) 61-73.

Digital Library

[18]

RDF Data Access Working Group, W3C, http://www.w3.org/2001/sw/DataAccess/

Cited By

Angele KAngele JSimsek UFensel D(2023)SemReasoner - A High-Performance Knowledge Graph Store and Rule-Based ReasonerThe Semantic Web10.1007/978-3-031-33455-9_34(574-590)Online publication date: 28-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-33455-9_34
Klusch MMeshram ASchuetze AHelwig N(2015)iCM-HydraulicProceedings of the 11th International Conference on Semantic Systems10.1145/2814864.2814865(81-88)Online publication date: 16-Sep-2015
https://dl.acm.org/doi/10.1145/2814864.2814865
Mutharaju RMateti PHitzler P(2015)Towards a Rule Based Distributed OWL Reasoning FrameworkRevised Selected Papers of the 12th International Experiences and Directions Workshop on Ontology Engineering - Volume 955710.1007/978-3-319-33245-1_9(87-92)Online publication date: 9-Oct-2015
https://dl.acm.org/doi/10.1007/978-3-319-33245-1_9
Show More Cited By

Index Terms

Combining RDF and part of OWL with rules: semantics, decidability, complexity
1. Theory of computation
  1. Logic

Recommendations

OWL rules: A proposal and prototype implementation

Although the OWL Web Ontology Language adds considerable expressive power to the Semantic Web it does have expressive limitations, particularly with respect to what can be said about properties. We present the Semantic Web Rule Language (SWRL), a Horn ...
Interpreting SWRL Rules in RDF Graphs

An unresolved issue in SWRL (the Semantic Web Rule Language) is whether the intended semantics of its RDF representation can be described as an extension of the W3C RDF semantics. In this paper we propose to make the model-theoretic semantics of SWRL ...
Combining OWL ontologies using E-Connections

The standardization of the Web Ontology Language (OWL) leaves (at least) two crucial issues for Web-based ontologies unsatisfactorily resolved, namely how to represent and reason with multiple distinct, but linked ontologies, and how to enable effective ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ISWC'05: Proceedings of the 4th international conference on The Semantic Web

November 2005

1004 pages

ISBN:3540297545

Editors:
Yolanda Gil
USC Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CA,
,
Enrico Motta
Knowledge Media Institute, The Open University, 4676 Admiralty Way, Marina del Rey, Milton Keynes, CA, UK
,
V. Richard Benjamins
Knowledge Media Institute, iSOCO, 4676 Admiralty Way, Marina del Rey, Milton Keynes, CA, Spain
,
Mark A. Musen
Stanford Center for Biomedical Informatics Research, Stanford University, 4676 Admiralty Way, Marina del Rey, Stanford, CA, US

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 06 November 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Angele KAngele JSimsek UFensel D(2023)SemReasoner - A High-Performance Knowledge Graph Store and Rule-Based ReasonerThe Semantic Web10.1007/978-3-031-33455-9_34(574-590)Online publication date: 28-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-33455-9_34
Klusch MMeshram ASchuetze AHelwig N(2015)iCM-HydraulicProceedings of the 11th International Conference on Semantic Systems10.1145/2814864.2814865(81-88)Online publication date: 16-Sep-2015
https://dl.acm.org/doi/10.1145/2814864.2814865
Mutharaju RMateti PHitzler P(2015)Towards a Rule Based Distributed OWL Reasoning FrameworkRevised Selected Papers of the 12th International Experiences and Directions Workshop on Ontology Engineering - Volume 955710.1007/978-3-319-33245-1_9(87-92)Online publication date: 9-Oct-2015
https://dl.acm.org/doi/10.1007/978-3-319-33245-1_9
Klusch MMeshram AKapahnke PSchuetze ACho YShin SKim SHung CHong J(2014)ICM-WindProceedings of the 29th Annual ACM Symposium on Applied Computing10.1145/2554850.2554928(308-315)Online publication date: 24-Mar-2014
https://dl.acm.org/doi/10.1145/2554850.2554928
Kumar VFensel AFröhlich PWeippl EIndrawan-Santiago MSteinbauer MKotsis GKhalil I(2013)Context Based Adaptation of Semantic Rules in Smart BuildingsProceedings of International Conference on Information Integration and Web-based Applications & Services10.1145/2539150.2539174(719-728)Online publication date: 2-Dec-2013
https://dl.acm.org/doi/10.1145/2539150.2539174
Hogan APan JPolleres ARen Y(2011)Scalable OWL 2 reasoning for linked dataProceedings of the 7th international conference on Reasoning web: semantic technologies for the web of data10.5555/2033313.2033318(250-325)Online publication date: 23-Aug-2011
https://dl.acm.org/doi/10.5555/2033313.2033318
Teymourian KPaschke A(2010)Enabling knowledge-based complex event processingProceedings of the 2010 EDBT/ICDT Workshops10.1145/1754239.1754281(1-7)Online publication date: 22-Mar-2010
https://dl.acm.org/doi/10.1145/1754239.1754281
Bry FFurche TLey CMarnette BLinse BSchaffert S(2010)Datalog relaunchedProceedings of the First international conference on Datalog Reloaded10.1007/978-3-642-24206-9_19(321-350)Online publication date: 16-Mar-2010
https://dl.acm.org/doi/10.1007/978-3-642-24206-9_19
Liang SFodor PWan HKifer MQuemada JLeón GMaarek YNejdl W(2009)OpenRuleBenchProceedings of the 18th international conference on World wide web10.1145/1526709.1526790(601-610)Online publication date: 20-Apr-2009
https://dl.acm.org/doi/10.1145/1526709.1526790
Fischer FUnel GBishop BFensel D(2009)Towards a scalable, pragmatic knowledge representation language for the webProceedings of the 7th international Andrei Ershov Memorial conference on Perspectives of Systems Informatics10.1007/978-3-642-11486-1_11(124-134)Online publication date: 15-Jun-2009
https://dl.acm.org/doi/10.1007/978-3-642-11486-1_11
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents