[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Polynomial rewritings from expressive Description Logics with closed predicates to variants of Datalog

Published: 01 March 2020 Publication History

Abstract

In many scenarios, complete and incomplete information coexist. For this reason, the knowledge representation and database communities have long shown interest in simultaneously supporting the closed- and the open-world views when reasoning about logic theories. Here we consider the setting of querying possibly incomplete data using logic theories, formalized as the evaluation of an ontology-mediated query (OMQ) that pairs a query with a theory, sometimes called an ontology, expressing background knowledge. This can be further enriched by specifying a set of closed predicates from the theory that are to be interpreted under the closed-world assumption, while the rest are interpreted with the open-world view. In this way we can retrieve more precise answers to queries by leveraging the partial completeness of the data.
The central goal of this paper is to understand the relative expressiveness of ontology-mediated query languages in which the ontology part is written in the expressive Description Logic (DL) ALCHOI and includes a set of closed predicates. We consider a restricted class of conjunctive queries. Our main result is to show that every query in this non-monotonic query language can be translated in polynomial time into Datalog with negation as failure under the stable model semantics. To overcome the challenge that Datalog has no direct means to express the existential quantification present in ALCHOI, we define a two-player game that characterizes the satisfaction of the ontology, and design a Datalog query that can decide the existence of a winning strategy for the game. If there are no closed predicates—in the case of querying an ALCHOI knowledge base—our translation yields a positive disjunctive Datalog program of polynomial size. To the best of our knowledge, unlike previous translations for related fragments with expressive (non-Horn) DLs, these are the first polynomial time translations.

References

[1]
Shqiponja Ahmetaj, Magdalena Ortiz, Mantas Šimkus, Polynomial datalog rewritings for expressive description logics with closed predicates, in: IJCAI, IJCAI/AAAI Press, 2016, pp. 878–885.
[2]
Shqiponja Ahmetaj, Magdalena Ortiz, Mantas Šimkus, Polynomial disjunctive datalog rewritings of instance queries in expressive description logics, in: Proc. of DL 2016, 2016.
[3]
Shqiponja Ahmetaj, Magdalena Ortiz, Mantas Šimkus, Rewriting guarded existential rules into small datalog programs, in: ICDT, in: LIPIcs, vol. 98, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, pp. 4:1–4:24.
[4]
Franz Baader, Diego Calvanese, Deborah McGuinness, Daniele Nardi, Peter Patel-Schneider (Eds.), The Description Logic Handbook: Theory, Implementation, and Applications, second edition, Cambridge University Press, 2007.
[5]
Labinot Bajraktari, Magdalena Ortiz, Mantas Šimkus, Combining rules and ontologies into clopen knowledge bases, in: AAAI, 2018, pp. 1728–1735. https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16991.
[6]
Vince Bárány, Michael Benedikt, Balder ten Cate, Rewriting guarded negation queries, in: Proc. of MFCS' 13, ACM, 2013, pp. 98–110.
[7]
Michael Benedikt, Pierre Bourhis, PSPACE hardness of mixed world query answering for atomic queries under guarded TGDS, Technical report University of Oxford, 2018, http://www.cs.ox.ac.uk/people/michael.benedikt/pspace.pdf.
[8]
Michael Benedikt, Pierre Bourhis, Balder ten Cate, Gabriele Puppis, Querying visible and invisible information, in: LICS, ACM, 2016, pp. 297–306.
[9]
Michael Benedikt, Bernardo Cuenca Grau, Egor V. Kostylev, Source information disclosure in ontology-based data integration, in: AAAI, AAAI Press, 2017, pp. 1056–1062.
[10]
Meghyn Bienvenu, Magdalena Ortiz, Ontology-mediated query answering with data-tractable description logics, in: Reasoning Web, in: Lecture Notes in Computer Science, vol. 9203, Springer, 2015, pp. 218–307.
[11]
Meghyn Bienvenu, Diego Calvanese, Magdalena Ortiz, Mantas Šimkus, Nested regular path queries in description logics, in: KR, AAAI Press, 2014.
[12]
Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, Frank Wolter, Ontology-based data access: a study through disjunctive datalog, CSP, and MMSNP, ACM Trans. Database Syst. 39 (4) (2014) 33:1–33:44.
[13]
Andrea Calì, Georg Gottlob, Thomas Lukasiewicz, A general datalog-based framework for tractable query answering over ontologies, in: PODS, ACM, 2009, pp. 77–86.
[14]
Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati, Tractable reasoning and efficient query answering in description logics: the DL-Lite family, J. Autom. Reason. 39 (3) (2007) 385–429.
[15]
Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati, Data complexity of query answering in description logics, Artif. Intell. 195 (2013) 335–360.
[16]
Diego Calvanese, Thomas Eiter, Magdalena Ortiz, Answering regular path queries in expressive Description Logics via alternating tree-automata, Inf. Comput. 237 (2014) 12–55.
[17]
Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov, Complexity and expressive power of logic programming, ACM Comput. Surv. 33 (3) (2001) 374–425.
[18]
Ting Deng, Wenfei Fan, Floris Geerts, Capturing missing tuples and missing values, ACM Trans. Database Syst. 41 (2) (2016) 10:1–10:47.
[19]
Thomas Eiter, Georg Gottlob, Heikki Mannila, Disjunctive datalog, ACM Trans. Database Syst. 22 (3) (1997) 364–418.
[20]
Thomas Eiter, Giovambattista Ianni, Thomas Lukasiewicz, Roman Schindlauer, Hans Tompits, Combining answer set programming with description logics for the Semantic Web, Artif. Intell. 172 (12–13) (2008) 1495–1539,.
[21]
Thomas Eiter, Magdalena Ortiz, Mantas Simkus, Trung-Kien Tran, Guohui Xiao, Query rewriting for Horn-SHIQ plus rules, in: AAAI, AAAI Press, 2012.
[22]
Thomas Eiter, Magdalena Ortiz, Mantas Šimkus, Conjunctive query answering in the description logic SH using knots, J. Comput. Syst. Sci. 78 (1) (2012) 47–85.
[23]
Wenfei Fan, Floris Geerts, Relative information completeness, ACM Trans. Database Syst. 35 (4) (2010) 27:1–27:44.
[24]
Enrico Franconi, Yazmin Angélica Ibáñez-García, Inanç Seylan, Query answering with DBoxes is hard, Electron. Notes Theor. Comput. Sci. 278 (2011) 71–84.
[25]
Michael Gelfond, Vladimir Lifschitz, The stable model semantics for logic programming, in: Proc. of ICLP/SLP 1988, MIT Press, 1988.
[26]
Georg Gottlob, Thomas Schwentick, Rewriting ontological queries into small nonrecursive datalog programs, in: KR, AAAI Press, 2012.
[27]
Georg Gottlob, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Thomas Schwentick, Michael Zakharyaschev, The price of query rewriting in ontology-based data access, Artif. Intell. 213 (2014) 42–59.
[28]
Georg Gottlob, Marco Manna, Andreas Pieris, Polynomial combined rewritings for existential rules, in: KR, AAAI Press, 2014.
[29]
Georg Gottlob, Sebastian Rudolph, Mantas Šimkus, Expressiveness of guarded existential rule languages, in: PODS, ACM, 2014, pp. 27–38.
[30]
Georg Gottlob, Marco Manna, Andreas Pieris, Polynomial rewritings for linear existential rules, in: IJCAI, AAAI Press, 2015, pp. 2992–2998.
[31]
I. Horrocks, U. Sattler, S. Tessaris, S. Tobies, Query containment using a DLR ABox, LTCS-Report LTCS-99-15, LuFG Theoretical Computer Science RWTH Aachen, Germany, 1999, See http://www-lti.informatik.rwth-aachen.de/Forschung/Reports.html.
[32]
Ian Horrocks, Peter F. Patel-Schneider, KR and reasoning on the Semantic Web: OWL, in: Handbook of Semantic Web Technologies, Springer, 2011, pp. 365–398.
[33]
Ullrich Hustadt, Boris Motik, Ulrike Sattler, Reasoning in description logics by a reduction to disjunctive datalog, J. Autom. Reason. 39 (3) (2007) 351–384.
[34]
Mark Kaminski, Yavor Nenov, Bernardo Cuenca Grau, Datalog rewritability of Disjunctive Datalog programs and non-Horn ontologies, Artif. Intell. 236 (2016) 90–118.
[35]
Roman Kontchakov, Carsten Lutz, David Toman, Frank Wolter, Michael Zakharyaschev, The combined approach to ontology-based data access, in: IJCAI, IJCAI/AAAI, 2011, pp. 2656–2661.
[36]
Thomas Lukasiewicz, A novel combination of answer set programming with description logics for the semantic web, IEEE Trans. Knowl. Data Eng. 22 (11) (2010) 1577–1592,.
[37]
Carsten Lutz, The complexity of conjunctive query answering in expressive description logics, in: Automated Reasoning, 4th International Joint Conference, IJCAR, 2008, pp. 179–193.
[38]
Carsten Lutz, Inanç Seylan, Frank Wolter, Ontology-based data access with closed predicates is inherently intractable (sometimes), in: IJCAI, IJCAI/AAAI, 2013, pp. 1024–1030.
[39]
Carsten Lutz, Inanç Seylan, Frank Wolter, Ontology-mediated queries with closed predicates, in: IJCAI, AAAI Press, 2015, pp. 3120–3126.
[40]
Boris Motik, Riccardo Rosati, Reconciling description logics and rules, J. ACM 57 (5) (2010) 30:1–30:62,.
[41]
Boris Motik, Ulrike Sattler, Rudi Studer, Query answering for OWL-DL with rules, J. Web Semant. 3 (1) (2005) 41–60.
[42]
Nhung Ngo, Magdalena Ortiz, Mantas Simkus, Closed predicates in Description Logics: results on combined complexity, in: KR, 2016, pp. 237–246. http://www.aaai.org/ocs/index.php/KR/KR16/paper/view/12906.
[43]
Magdalena Ortiz, Sebastian Rudolph, Mantas Šimkus, Worst-case optimal reasoning for the Horn-DL fragments of OWL 1 and 2, in: KR, AAAI Press, 2010.
[44]
Héctor Pérez-Urbina, Boris Motik, Ian Horrocks, Tractable query answering and rewriting under description logic constraints, J. Appl. Log. 8 (2) (2010) 186–209.
[45]
Simon Razniewski, Werner Nutt, Databases under the partial closed-world assumption: a survey, in: Grundlagen von Datenbanken, in: CEUR Workshop Proceedings, vol. 1313, 2014, pp. 59–64.
[46]
Riccardo Rosati, DL+log: tight integration of description logics and disjunctive datalog, in: Patrick Doherty, John Mylopoulos, Christopher A. Welty (Eds.), Proceedings, Tenth International Conference on Principles of Knowledge Representation and Reasoning, Lake District of the United Kingdom, June 2–5, 2006, AAAI Press, ISBN 978-1-57735-271-6, 2006, pp. 68–78. http://www.aaai.org/Library/KR/2006/kr06-010.php.
[47]
Andrea Schaerf, Reasoning with individuals in concept languages, Data Knowl. Eng. 13 (2) (1994) 141–176,.
[48]
Klaus Schild, A correspondence theory for terminological logics: preliminary, report 1991, pp. 466–471.
[49]
Inanç Seylan, Enrico Franconi, Jos de Bruijn, Effective query rewriting with ontologies over DBoxes, in: Proc. of IJCAI 2009, 2009.
[50]
Frantisek Simancik, Yevgeny Kazakov, Ian Horrocks, Consequence-based reasoning beyond horn ontologies, in: IJCAI, IJCAI/AAAI, 2011, pp. 1093–1098.
[51]
Despoina Trivela, Giorgos Stoilos, Alexandros Chortaras, Giorgos B. Stamou, Optimising resolution-based rewriting algorithms for OWL ontologies, J. Web Semant. 33 (2015) 30–49.
[52]
Mihalis Yannakakis, Algorithms for acyclic database schemes, in: Proceedings of the Seventh International Conference on Very Large Data Bases - Volume 7, VLDB '81, VLDB Endowment, 1981, pp. 82–94. http://dl.acm.org/citation.cfm?id=1286831.1286840.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Artificial Intelligence
Artificial Intelligence  Volume 280, Issue C
Mar 2020
159 pages

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 March 2020

Author Tags

  1. Description Logics
  2. Datalog
  3. Closed predicates
  4. Ontology-mediated query answering
  5. Query rewriting
  6. Succinctness
  7. Relative expressiveness

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 26 Dec 2024

Other Metrics

Citations

Cited By

View all

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media