article

Reasoning in Description Logics by a Reduction to Disjunctive Datalog

Authors:

Ullrich Hustadt,

Ulrike SattlerAuthors Info & Claims

Journal of Automated Reasoning, Volume 39, Issue 3

Pages 351 - 384

https://doi.org/10.1007/s10817-007-9080-3

Published: 01 October 2007 Publication History

Abstract

As applications of description logics proliferate, efficient reasoning with knowledge bases containing many assertions becomes ever more important. For such cases, we developed a novel reasoning algorithm that reduces a $\mathcal{SHIQ}$ knowledge base to a disjunctive datalog program while preserving the set of ground consequences. Queries can then be answered in the resulting program while reusing existing and practically proven optimization techniques of deductive databases, such as join-order optimizations or magic sets. Moreover, we use our algorithm to derive precise data complexity bounds: we show that $\mathcal{SHIQ}$ is data complete for NP, and we identify an expressive fragment of $\mathcal{SHIQ}$ with polynomial data complexity.

References

[1]

1. Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison Wesley, Reading, MA (1995).

[2]

2. Alsaç, G., Baral, C.: Reasoning in description logics using declarative logic programming. Technical report, Arizona State University, Arizona. http://www.public.asu.edu/~cbaral/papers/ descr-logic-aaai2.pdf (2002).

[3]

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

[4]

4. Baader, F., Nipkow, T.: Term Rewriting and All That. Cambridge University Press, MA (1998).

[5]

5. Baaz, M., Egly, U., Leitsch, A.: Normal form transformations. In: Robinson, A., Voronkov, A. (eds.) Handbook of Automated Reasoning, vol. I. Chapt. 5, pp. 273-333. Elsevier Science, Amsterdam (2001).

[6]

6. Bachmair, L., Ganzinger, H., Lynch, C., Snyder, W.: Basic paramodulation. Inf. Comput. 121 (2), 172-192 (1995).

Digital Library

[7]

7. Beeri, C., Ramakrishnan, R.: On the power of magic. In: Proceedings of the 6th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS '87), pp. 269-283. San Diego, CA, USA (1987).

Digital Library

[8]

8. Borgida, A.: On the relative expressiveness of description logics and predicate logics. Artif. Intell. 82 (1-2), 353-367 (1996).

Digital Library

[9]

9. Calvanese, D., Giacomo, G.D., Lembo, D., Lenzerini, M., Rosati, R.: Data complexity of query answering in description logics. In: Doherty, P., Mylopoulos, J., Welty, C.A. (eds.) Proceedings of the 10th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR 2006), pp. 260-270. Lake District, UK (2006).

[10]

10. Calvanese, D., Lenzerini, M., Nardi, D.: Description logics for conceptual data modeling. In: Chomicki, J., Saake, G. (eds.) Logics for Databases and Information Systems, Chapt. 8, pp. 229-263. Kluwer, Boston, MA (1998).

[11]

11. Chen, P.P.: The entity-relationship model - toward a unified view of data. ACM Trans. Database Syst. 1 (1), 9-36 (1976).

Digital Library

[12]

12. Cumbo, C., Faber, W., Greco, G., Leone, N.: Enhancing the magic-set method for disjunctive datalog programs. In: Demoen, B., Lifschitz, V. (eds.) Proceedings of the 20th Int. Conf. on Logic Programming (ICLP 2004), LNCS, vol. 3132, pp. 371-385. Saint-Malo, France (2004).

[13]

13. Dantsin, E., Eiter, T., Gottlob, G., Voronkov, A.: Complexity and expressive power of logic programming. ACM Comput. Surv. 33 (3), 374-425 (2001).

Digital Library

[14]

14. Eiter, T., Gottlob, G., Mannila, H.: Disjunctive datalog. ACM Trans. Database Syst. 22 (3), 364-418 (1997).

Digital Library

[15]

15. Fitting, M.: First-order logic and theorem proving. In: Texts in Computer Science, 2nd edn. Springer, Berlin Heidelberg New York (1996).

[16]

16. Grosof, B.N., Horrocks, I., Volz, R., Decker, S.: Description logic programs: combining logic programs with description logic. In: Proceedings of the 12th Int. World Wide Web Conference (WWW 2003), pp. 48-57. Budapest, Hungary (2003).

[17]

17. Haarslev, V., Möller, R.,: RACER system description. In: Goré, R., Leitsch, A., Nipkow, T. (eds.) Proceedings of the 1st Int. Joint Conf. on Automated Reasoning (IJCAR 2001), LNAI, vol. 2083, pp. 701-706. Siena, Italy (2001).

[18]

18. Haarslev, V., Möller, R., Turhan, A.-Y.: Exploiting pseudo models for TBox and ABox reasoning in expressive description logics. In: Goré, R., Leitsch, A., Nipkow, T. (eds.) Proceedings of the 1st Int. Joint Conf. on Automated Reasoning (IJCAR 2001), LNAI, vol. 2083, pp. 61-75. Siena, Italy (2001).

[19]

19. Heymans, S., Vermeir, D.: Integrating semantic web reasoning and answer set programming. In: Vos, M.D., Provetti, A. (eds.) Proceedings of the 2nd Int. Workshop on Answer Set Programming, Advances in Theory and Implementation (ASP'03), CEUR Workshop Proceedings, vol. 78, pp. 194-208. Messina, Italy (2003).

[20]

20. Horrocks, I., Patel-Schneider, P.F., van Harmelen, F.: From SHIQ and RDF to OWL: the making of a web ontology language. J. Web Sem. 1 (1), 7-26 (2003).

[21]

21. Horrocks, I., Sattler, U., Tobies, S.: Practical reasoning for very expressive description logics. Log. J. IGPL 8 (3), 239-263 (2000).

[22]

22. Hustadt, U., Motik, B., Sattler, U.: Reducing SHIQ - description logic to disjunctive datalog programs. In: Dubois, D., Welty, C.A., Williams, M.-A. (eds.) Proceedings of the 9th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR 2004), pp. 152-162. Whistler, Canada (2004).

[23]

23. Hustadt, U., Motik, B., Sattler, U.: A decomposition rule for decision procedures by resolution-based calculi. In: Baader, F., Voronkov, A. (eds.) Proceedings of the 11th Int. Conf. on Logic for Programming Artificial Intelligence and Reasoning (LPAR 2004), LNAI, vol. 3452, pp. 21-35. Montevideo, Uruguay (2005a).

[24]

24. Hustadt, U., Motik, B., Sattler, U.: Data complexity of reasoning in very expressive description logics. In: Proceedings of the 19th Int. Joint Conf. on Artificial Intelligence (IJCAI 2005), pp. 466-471. Edinburgh, UK (2005b).

[25]

25. Hustadt, U., Schmidt, R.A.: On the relation of resolution and tableaux proof systems for description logics. In: Thomas, D. (ed.) Proceedings of the 16th Int. Joint Conf. on Artificial Intelligence (IJCAI '99), pp. 110-115. Stockholm, Sweden (1999).

[26]

26. Kazakov, Y., de Nivelle, H.: A resolution decision procedure for the guarded fragment with transitive guards. In: Basin, D., Rusinowitch, M. (eds.) Proceedings of the 2nd Int. Joint Conf. on Automated Reasoning (IJCAR 2004), LNAI, vol. 3097, pp. 122-136. Cork, Ireland (2004).

[27]

27. Kazakov, Y., Motik, B.: A resolution-based decision procedure for SHOIQ . In: Furbach, U., Harrison, J., Shankar, N. (eds.) Proceedings of the 3rd Int. Joint Conf. on Automated Reasoning (IJCAR 2006), LNAI, vol. 4130, pp. 662-667. Seattle, WA (2006).

[28]

28. Motik, B.: Reasoning in description logics using resolution and deductive databases. Ph.D. thesis, Univesität Karlsruhe, Germany (2006).

[29]

29. Motik, B., Sattler, U.: A comparison of reasoning techniques for querying large description logic ABoxes. In: Hermann, M., Voronkov, A. (eds.) Proceedings of the 13th Int. Conf. on Logic for Programming Artificial Intelligence and Reasoning (LPAR 2006), pp. 227-241. Phnom Penh, Cambodia (2006), (accepted for publication).

[30]

30. Nebel, B.: Terminological cycles: semantics and computational properties. In: Sowa, J.F. (ed.) Principles of Semantic Networks: Explorations in the Representation of Knowledge, pp. 331-361. Morgan Kaufmann, San Mateo, CA (1991).

[31]

31. Nieuwenhuis, R., Rubio, A.: Theorem proving with ordering and equality constrained clauses. J. Symb. Comput. 19 (4), 312-351 (1995).

Digital Library

[32]

32. Nonnengart, A., Weidenbach, C.: Computing small clause normal forms. In: Robinson, A., Voronkov, A. (eds.) Handbook of Automated Reasoning, vol. I. Chapt. 6, pp. 335-367. Elsevier, Amsterdam (2001).

[33]

33. Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading, MA (1993).

[34]

34. Parsia, B., Sirin, E.: Pellet: an OWL-DL reasoner. Poster, In: Proceedings of the 3rd Int. Semantic Web Conference (ISWC 2004), Hiroshima, Japan, 7-11 November (2004).

[35]

35. Plaisted, D.A., Greenbaum, S.: A structure-preserving clause form translation. J. Symb. Comput. 2 (3), 293-304 (1996).

[36]

36. Schaerf, A.: Query answering in concept-based knowledge representation systems: algorithms, complexity, and semantic issues. Ph.D. thesis, Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza," Italy (1994).

[37]

37. Swift, T.: Deduction in ontologies via ASP. In: Lifschitz, V., Niemelä, I. (eds.) Proceedings of the 7th Int. Conf. on Logic Programming and Nonmonotonic Reasoning (LPNMR 2004), LNCS, vol. 2923, pp. 275-288. Fort Lauderdale, FL (2004).

[38]

38. Tobies, S.: Complexity results and practical algorithms for logics in knowledge representation. Ph.D. thesis, RWTH Aachen, Germany (2001).

[39]

39. Tsarkov, D., Horrocks, I.: FaCT++ description logic reasoner: system description. In: Proceedings of the 3rd Int. Joint Conf. on Automated Reasoning (IJCAR 2006), LNAI, vol. 4130, pp. 292-297. Seattle, WA (2006).

Cited By

Benedikt MBuron MGermano SKappelmann KMotik B(2024)Rewriting the Infinite Chase for Guarded TGDsACM Transactions on Database Systems10.1145/369641649:4(1-44)Online publication date: 18-Sep-2024
https://dl.acm.org/doi/10.1145/3696416
Lukumbuzya SOrtiz MŠimkus M(2024)Datalog rewritability and data complexity of ALCHOIQ with closed predicatesArtificial Intelligence10.1016/j.artint.2024.104099330:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.artint.2024.104099
Zheng SSchmidt R(2023)Saturation-Based Boolean Conjunctive Query Answering and Rewriting for the Guarded Quantification FragmentsJournal of Automated Reasoning10.1007/s10817-023-09687-x67:4Online publication date: 23-Nov-2023
https://dl.acm.org/doi/10.1007/s10817-023-09687-x
Show More Cited By

Index Terms

Reasoning in Description Logics by a Reduction to Disjunctive Datalog

Recommendations

Datalog rewritability of Disjunctive Datalog programs and non-Horn ontologies

We study the problem of rewriting a Disjunctive Datalog program into an equivalent plain Datalog program (i.e., one that entails the same facts for every dataset). We show that a Disjunctive Datalog program is Datalog rewritable if and only if it can be ...
Enhancing Disjunctive Datalog by Constraints

This paper presents an extension of Disjunctive Datalog (${\rm{DATALOG}}^{\vee,}{^\neg}$) by integrity constraints. These are of two types: strong, that is, classical integrity constraints and weak, that is, constraints that are satisfied if possible. ...
Disjunctive datalog

We consider disjunctive Datalog, a powerful database query language based on disjunctive logic programming. Briefly, disjunctive Datalog is a variant of Datalog where disjunctions may appear in the rule heads; advanced versions also allow for negation in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Automated Reasoning

Journal of Automated Reasoning Volume 39, Issue 3

October 2007

183 pages

ISSN:0168-7433

Issue’s Table of Contents

Copyright © Copyright © 2007 Springer Science+Business Media B.V.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 October 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

59
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Benedikt MBuron MGermano SKappelmann KMotik B(2024)Rewriting the Infinite Chase for Guarded TGDsACM Transactions on Database Systems10.1145/369641649:4(1-44)Online publication date: 18-Sep-2024
https://dl.acm.org/doi/10.1145/3696416
Lukumbuzya SOrtiz MŠimkus M(2024)Datalog rewritability and data complexity of ALCHOIQ with closed predicatesArtificial Intelligence10.1016/j.artint.2024.104099330:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.artint.2024.104099
Zheng SSchmidt R(2023)Saturation-Based Boolean Conjunctive Query Answering and Rewriting for the Guarded Quantification FragmentsJournal of Automated Reasoning10.1007/s10817-023-09687-x67:4Online publication date: 23-Nov-2023
https://dl.acm.org/doi/10.1007/s10817-023-09687-x
Benedikt MBuron MGermano SKappelmann KMotik B(2022)Rewriting the infinite chaseProceedings of the VLDB Endowment10.14778/3551793.355185115:11(3045-3057)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.14778/3551793.3551851
Trivela DStoilos GChortaras AStamou G(2020)Resolution-based rewriting for Horn- ontologiesKnowledge and Information Systems10.1007/s10115-019-01345-262:1(107-143)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1007/s10115-019-01345-2
Faber W(2020)An Introduction to Answer Set Programming and Some of Its ExtensionsReasoning Web. Declarative Artificial Intelligence10.1007/978-3-030-60067-9_6(149-185)Online publication date: 24-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-60067-9_6
Barceló PFeier CLutz CPieris ABouyer P(2019)When is ontology-mediated querying efficient?Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3470152.3470205(1-13)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.5555/3470152.3470205
Jung JPapacchini FWolter FZakharyaschev MBouyer P(2019)Model comparison games for horn description logicsProceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3470152.3470156(1-14)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.5555/3470152.3470156
Bate AMotik BGrau BCucala DSimančík FHorrocks I(2019)Consequence-based reasoning for description logics with disjunctions and number restrictionsJournal of Artificial Intelligence Research10.1613/jair.1.1125763:1(625-690)Online publication date: 17-Apr-2019
https://dl.acm.org/doi/10.1613/jair.1.11257
Kriegel F(2019)Joining Implications in Formal Contexts and Inductive Learning in a Horn Description LogicFormal Concept Analysis10.1007/978-3-030-21462-3_9(110-129)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-21462-3_9
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