×

Polynomial rewritings from expressive description logics with closed predicates to variants of Datalog. (English) Zbl 1476.68250

Summary: 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) \( \mathcal{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 \(\mathcal{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 \(\mathcal{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.

MSC:

68T27 Logic in artificial intelligence
68N17 Logic programming
68P15 Database theory
68T30 Knowledge representation

Software:

Datalog
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

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