More Web Proxy on the site http://driver.im/

article

On the decidability and complexity of integrating ontologies and rules

Author:

Riccardo RosatiAuthors Info & Claims

Web Semantics: Science, Services and Agents on the World Wide Web, Volume 3, Issue 1

Pages 61 - 73

https://doi.org/10.1016/j.websem.2005.05.002

Published: 01 July 2005 Publication History

Abstract

We define the formal framework of r-hybrid knowledge bases (KBs) integrating ontologies and rules. A r-hybrid KB has a structural component (ontology) and a rule component. Such a framework is very general, in the sense that: (i) the construction is parametric with respect to the logic used to specify the structural component; (ii) the rule component is very expressive, since it consists of a Datalog^@?^@? program, i.e., a Datalog program with negation as failure and disjunction, (iii) the rule component is constrained in its interaction with the structural component according to a safeness condition: such a safe interaction between rules and structural KB captures (and is a generalization of) several previous proposals. As a consequence, we are able to show that such a framework of r-hybrid KBs comprises many systems proposed for combining rules and Description Logics. Then, we study reasoning in r-hybrid KBs. We provide a general algorithm for reasoning in r-hybrid KBs, and prove that, under very general conditions, decidability of reasoning is preserved when we add safe Datalog^@?^@? rules to a KB: in other words, if reasoning in the logic L used to specify the structural component T is decidable, then reasoning in the extension of T with safe Datalog^@?^@? rules is still decidable. We also show that an analogous property holds for the complexity of reasoning in r-hybrid KBs. Our decidability and complexity results generalize in a broad sense previous results obtained in recent research on this topic. In particular, we prove that reasoning in r-hybrid KBs whose structural component is specified in the Web Ontology Language OWL-DL is decidable.

References

[1]

G. Antoniou. A nonmonotonic rule system using ontologies, in: Proceedings of the First International

[2]

Antoniou, G., Nonmonotonic rule systems on top of ontology layers. In: Proceedings of the 2002 International Semantic Web Conference (ISWC 2002), pp. 394-398.

[3]

Antoniou, G., Bikakis, A. and Wagner, G., A system for nonmonotonic rules on the web. In: Proceedings of the Third International Workshop on Rules and Rule Markup Languages for the Semantic Web (RuleML 2004), pp. 23-36.

[4]

Areces, C., Blackburn, P., Martinez Hernandez, B. and Marx, M., Handling boolean ABoxes. In: Proceedings of the 2003 Description Logic Workshop (DL 2003),

[5]

In: Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.F. (Eds.), The Description Logic Handbook: Theory, Implementation and Applications, Cambridge University Press.

[6]

Cadoli, M., Palopoli, L. and Lenzerini, M., Datalog and description logics: expressive power. In: Proceedings of the Sixth International Workshop on Database Programming Languages (DBPL'97),

[7]

D. Calvanese, R. Rosati. Answering recursive queries under keys and foreign keys is undecidable, in: Proceedings of the Tenth International Workshop on Knowledge Representation meets Databases (KRDB 2003), CEUR Electronic Workshop Proceedings, http://ceur-ws.org/Vol-79/, 2003.

[8]

Donini, F.M., Lenzerini, M., Nardi, D., Nutt, W. and Schaerf, A., An epistemic operator for description logics. Artif. Intell. v100 i1-2. 225-274.

[9]

Donini, F.M., Lenzerini, M., Nardi, D. and Schaerf, A., AL-log: Integrating Datalog and description logics. J. Intell. Inform. Syst. v10 i3. 227-252.

[10]

Donini, F.M., Nardi, D. and Rosati, R., Description logics of minimal knowledge and negation as failure. ACM Trans. Comput. Logic. v3 i2. 177-225.

[11]

Eiter, T., Gottlob, G. and Mannilla, H., Disjunctive Datalog. ACM Trans. Database Syst. v22 i3. 364-418.

[12]

Eiter, T., Leone, N., Mateis, C., Pfeifer, G. and Scarcello, F., The KR system dlv: Progress report, comparison and benchmarks. In: Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR'98), pp. 636-647.

[13]

Eiter, T., Lukasiewicz, T., Schindlauer, R. and Tompits, H., Combining answer set programming with description logics for the semantic web. In: Proceedings of the Ninth International Conference on Principles of Knowledge Representation and Reasoning (KR 2004), pp. 141-151.

Digital Library

[14]

Eiter, T., Lukasiewicz, T., Schindlauer, R. and Tompits, H., Well-founded semantics for description logic programs in the semantic web. In: Proceedings of the Third International Workshop on Rules and Rule Markup Languages for the Semantic Web (RuleML 2004), pp. 81-97.

[15]

Frisch, A.M. and Cohn, A.G., Thoughts and afterthoughts on the 1988 workshop on principles of hybrid reasoning. AI Magaz. v12. 77-83.

[16]

Gelfond, M. and Lifschitz, V., Classical negation in logic programs and disjunctive databases. New Generat. Comput. v9. 365-385.

[17]

Grosof, B.N., Horrocks, I., Volz, R. and Decker, S., Description logic programs: combining logic programs with description logic. In: Proceedings of the 12th international conference on World Wide Web (WWW 2003), pp. 48-57.

[18]

Heymans, S., Nieuwenborgh, D.V. and Vermeir, D., Semantic web reasoning with conceptual logic programs. In: Proceedings of the Third International Workshop on Rules and Rule Markup Languages for the Semantic Web (RuleML 2004), pp. 113-127.

[19]

Heymans, S. and Vermeir, D., Integrating description logics and answer set programming. In: Proceedings of the 2003 International Workshop on Principles and Practice of Semantic Web Reasoning (PPSWR 2003), pp. 146-159.

[20]

Horrocks, I. and Patel-Schneider, P.F., Reducing OWL entailment to Description Logic satisfiability. In: Proceedings of the 2003 International Semantic Web Conference (ISWC 2003), pp. 17-29.

[21]

Horrocks, I. and Patel-Schneider, P.F., A proposal for an OWL rules language. In: Proceedings of the 13th international conference on World Wide Web (WWW 2004), pp. 723-731.

[22]

Horrocks, I., Patel-Schneider, P.F. and van Harmelen, F., From SHIQ and RDF to OWL: the making of a web ontology language. J. Web Semant. v1 i1. 7-26.

[23]

Levesque, H.J., All I know: a study in autoepistemic logic. Artif. Intell. v42. 263-310.

[24]

Levy, A.Y., Rajaraman, A. and Ordille, J.J., Query answering algorithms for information agents. In: Proceedings of the 13th National Conference on Artificial Intelligence (AAAI'96), pp. 40-47.

[25]

Levy, A.Y. and Rousset, M.-C., CARIN: A representation language combining Horn rules and description logics. In: Proceedings of the 12th European Conference on Artificial Intelligence (ECAI'96), pp. 323-327.

[26]

Levy, A.Y. and Rousset, M.-C., The limits on combining recursive Horn rules with description logics. In: Proceedings of the 13th National Conference on Artificial Intelligence (AAAI'96), pp. 577-584.

[27]

Levy, A.Y. and Rousset, M.-C., Combining Horn rules and description logics in CARIN. Artif. Intell. v104 i1-2. 165-209.

[28]

Lifschitz, V., Minimal belief and negation as failure. Artif. Intell. v70. 53-72.

[29]

MacGregor, R., Inside the LOOM description classifier. SIGART Bull. v2 i3. 88-92.

[30]

Mei, J., Liu, S., Yue, A. and Lin, Z., An extension to OWL with general rules. In: Proceedings of the Third International Workshop on Rules and Rule Markup Languages for the Semantic Web (RuleML 2004), pp. 155-169.

[31]

Motik, B., Sattler, U. and Studer, R., Query answering for OWL-DL with rules. In: Proceedings of the 2004 International Semantic Web Conference (ISWC 2004), pp. 549-563.

Digital Library

[32]

P.F. Patel-Schneider, P.J. Hayes, I. Horrocks, F. van Harmelen. OWL web ontology language; semantics and abstract syntax. W3C candidate recommendation, http://www.w3.org/tr/owl-semantics, November 2002.

[33]

Patel-Schneider, P.F., McGuiness, D.L., Brachman, R.J., Resnick, L.A. and Borgida, A., The CLASSIC knowledge representation system: guiding principles and implementation rational. SIGART Bull. v2 i3. 108-113.

[34]

R. Rosati. Towards expressive KR systems integrating Datalog and description logics: preliminary report, in: Proceedings of the 1999 Description Logic Workshop (DL'99), pp. 160-164, CEUR Electronic Workshop Proceedings, http://ceur-ws.org/Vol-22/, 1999.

[35]

S. Tobies, Complexity Results and Practical Algorithms for Logics in Knowledge Representation, PhD thesis, LuFG Theoretical Computer Science, RWTH-Aachen, Germany, 2001.

[36]

Yen, J., Neches, R. and MacGregor, R., CLASP: integrating term subsumption systems and production systems. IEEE Trans. Knowl. Data Eng. v3 i1. 25-31.

Cited By

Danash FZiebelin DHong JLanperne MPark JCerny TShahriar H(2023)Translating FOL-theories into SROIQ-TboxesProceedings of the 38th ACM/SIGAPP Symposium on Applied Computing10.1145/3555776.3577870(1003-1006)Online publication date: 27-Mar-2023
https://dl.acm.org/doi/10.1145/3555776.3577870
Bajraktari LOrtiz MŠimkus MMcIlraith SWeinberger K(2018)Combining rules and ontologies into clopen knowledge basesProceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence10.5555/3504035.3504246(1728-1735)Online publication date: 2-Feb-2018
https://dl.acm.org/doi/10.5555/3504035.3504246
Amendola GLeone NManna MVeltri P(2018)Enhancing existential rules by closed-world variablesProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304889.3304892(1676-1682)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304889.3304892
Show More Cited By

On the decidability and complexity of integrating ontologies and rules

Recommendations

Combining answer set programming with description logics for the Semantic Web

We propose a combination of logic programming under the answer set semantics with the description logics SHIF(D) and SHOIN(D), which underly the Web ontology languages OWL Lite and OWL DL, respectively. To this end, we introduce description logic ...
Query-Driven Procedures for Hybrid MKNF Knowledge Bases

Hybrid MKNF knowledge bases are one of the most prominent tightly integrated combinations of open-world ontology languages with closed-world (nonmonotonic) rule paradigms. Based on the logic of minimal knowledge and negation as failure (MKNF), the ...
Description logic programs: combining logic programs with description logic
WWW '03: Proceedings of the 12th international conference on World Wide Web

We show how to interoperate, semantically and inferentially, between the leading Semantic Web approaches to rules (RuleML Logic Programs) and ontologies (OWL/DAML+OIL Description Logic) via analyzing their expressive intersection. To do so, we define a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Web Semantics: Science, Services and Agents on the World Wide Web

Web Semantics: Science, Services and Agents on the World Wide Web Volume 3, Issue 1

July, 2005

72 pages

ISSN:1570-8268

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2005.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 July 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

63
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Danash FZiebelin DHong JLanperne MPark JCerny TShahriar H(2023)Translating FOL-theories into SROIQ-TboxesProceedings of the 38th ACM/SIGAPP Symposium on Applied Computing10.1145/3555776.3577870(1003-1006)Online publication date: 27-Mar-2023
https://dl.acm.org/doi/10.1145/3555776.3577870
Bajraktari LOrtiz MŠimkus MMcIlraith SWeinberger K(2018)Combining rules and ontologies into clopen knowledge basesProceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence10.5555/3504035.3504246(1728-1735)Online publication date: 2-Feb-2018
https://dl.acm.org/doi/10.5555/3504035.3504246
Amendola GLeone NManna MVeltri P(2018)Enhancing existential rules by closed-world variablesProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304889.3304892(1676-1682)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304889.3304892
Sun LLi FHu X(2016)An Ontology-based Model for Typical-context Awareness in the Oil Products Distribution SystemProcedia Computer Science10.1016/j.procs.2016.08.15896:C(1156-1165)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.procs.2016.08.158
Pileggi S(2016)Probabilistic SemanticsProcedia Computer Science10.1016/j.procs.2016.05.47280:C(1834-1845)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1016/j.procs.2016.05.472
Analyti ADamásio CAntoniou G(2015)Extended RDFAnnals of Mathematics and Artificial Intelligence10.1007/s10472-015-9451-075:3-4(267-334)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1007/s10472-015-9451-0
Wang YEiter TYou JYuan LShen Y(2013)Eliminating nonmonotonic DL-Atoms in description logic programsProceedings of the 7th international conference on Web Reasoning and Rule Systems10.1007/978-3-642-39666-3_13(168-182)Online publication date: 27-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39666-3_13
Kaneiwa KNguyen POssowski SLecca P(2012)Sorted hyper-predicate knowledge bases for ontologies and rulesProceedings of the 27th Annual ACM Symposium on Applied Computing10.1145/2245276.2245339(312-319)Online publication date: 26-Mar-2012
https://dl.acm.org/doi/10.1145/2245276.2245339
Xiao GEiter T(2011)Inline evaluation of hybrid knowledge bases PhD descriptionProceedings of the 5th international conference on Web reasoning and rule systems10.5555/2036949.2036977(300-305)Online publication date: 29-Aug-2011
https://dl.acm.org/doi/10.5555/2036949.2036977
Krisnadhi AMaier FHitzler P(2011)OWL and rulesProceedings of the 7th international conference on Reasoning web: semantic technologies for the web of data10.5555/2033313.2033320(382-415)Online publication date: 23-Aug-2011
https://dl.acm.org/doi/10.5555/2033313.2033320
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents