×

The data complexity of ontology-mediated queries with closed predicates. (English) Zbl 1509.68258

Summary: We study the data complexity of ontology-mediated queries in which selected predicates can be closed (OMQCs), carrying out a non-uniform analysis of OMQCs in which the ontology is formulated in one of the lightweight description logics DL-Lite and \(\mathcal{EL}\) or in the expressive description logic \(\mathcal{ALCHI}\). We focus on separating tractable from non-tractable OMQCs. On the level of ontologies, we prove a dichotomy between FO-rewritable and coNP-complete for DL-Lite and between PTime and coNP-complete for \(\mathcal{EL}\). We also show that in both cases, the meta problem to decide tractability is in PTime. On the level of OMQCs, we show that there is no dichotomy (unless NP equals PTime) if both concept and role names can be closed. For the case where only concept names can be closed, we tightly link the complexity of OMQC evaluation to the complexity of surjective CSPs. We also identify a useful syntactic class of OMQCs based on DL-Lite\(_{\mathcal{R}}\) that are guaranteed to be FO-rewritable.

MSC:

68T30 Knowledge representation
68P15 Database theory
68Q25 Analysis of algorithms and problem complexity
68T27 Logic in artificial intelligence

Software:

Datalog
PDFBibTeX XMLCite
Full Text: arXiv

References:

[1] Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. · Zbl 0848.68031
[2] Shqiponja Ahmetaj, Magdalena Ortiz, and Mantas Simkus. Polynomial datalog rewritings for expressive description logics with closed predicates. In Proc. of IJCAI, pages 878-885, 2016. · Zbl 1476.68250
[3] Giovanni Amendola, Nicola Leone, Marco Manna, and Pierfrancesco Veltri. Enhancing existential rules by closed-world variables. In Proc. of IJCAI, pages 1676-1682, 2018.
[4] Marcelo Arenas, Pablo Barcel´o, Leonid Libkin, and Filip Murlak. Foundations of Data Exchange. Cambridge University Press, 2014. · Zbl 1216.68003
[5] Alessandro Artale, Diego Calvanese, Roman Kontchakov, and Michael Zakharyaschev. The DL-Lite family and relations. Journal of Artificial Intelligence Research, 36:1-69, 2009. · Zbl 1192.68657
[6] F. Baader, D. Calvanese, D. McGuiness, D. Nardi, and P. Patel-Schneider. The Description Logic Handbook: Theory, implementation and applications. Cambridge University Press, 2003. · Zbl 1058.68107
[7] Franz Baader, Sebastian Brandt, and Carsten Lutz. Pushing the EL envelope. In IJCAI, 2005.
[8] Franz Baader, Ian Horrocks, Carsten Lutz, and Ulrike Sattler. An Introduction to Description Logic. · Zbl 1373.68002
[9] Michael Benedikt and Pierre Bourhis. Pspace hardness of mixed world query answering for atomic queries under guarded tgds. Technical report, University of Oxford, 2018.
[10] Michael Benedikt, Pierre Bourhis, Balder ten Cate, and Gabriele Puppis. Querying visible and invisible information. In Proc. of LICS, pages 297-306, 2016. · Zbl 1394.68125
[11] Meghyn Bienvenu, Peter Hansen, Carsten Lutz, and Frank Wolter. First order-rewritability and containment of conjunctive queries in horn description logics. In Proc. of IJCAI, pages 965-971, 2016.
[12] Meghyn Bienvenu, Carsten Lutz, and Frank Wolter. First-order rewritability of atomic queries in horn description logics. In Proc. of IJCAI, pages 754-760, 2013.
[13] Meghyn Bienvenu and Magdalena Ortiz. Ontology-mediated query answering with data-tractable description logics. In Proc. of Reasoning Web, pages 218-307, 2015. · Zbl 1358.68086
[14] Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, and Frank Wolter. Ontology-based data access: A study through disjunctive datalog, CSP, and MMSNP. ACM Trans. Database Syst., 39(4):33, 2014. · Zbl 1474.68082
[15] Manuel Bodirsky, Jan K´ara, and Barnaby Martin. The complexity of surjective homomorphism problems– a survey. Discrete Applied Mathematics, 160(12):1680-1690, 2012. · Zbl 1246.05104
[16] Elena Botoeva, Boris Konev, Carsten Lutz, Vladislav Ryzhikov, Frank Wolter, and Michael Zakharyaschev. Inseparability and conservative extensions of description logic ontologies: A survey. In Proc. of Reasoning Web, pages 27-89, 2016. · Zbl 1358.68282
[17] Elena Botoeva, Roman Kontchakov, Vladislav Ryzhikov, Frank Wolter, and Michael Zakharyaschev. Games for query inseparability of description logic knowledge bases. Artif. Intell., 234:78-119, 2016. · Zbl 1351.68263
[18] Andrei A. Bulatov. A dichotomy theorem for nonuniform csps. In Proc. of FOCS, pages 319-330, 2017.
[19] Andrei A. Bulatov, Peter Jeavons, and Andrei A. Krokhin. Classifying the complexity of constraints using finite algebras. SIAM J. Comput., 34(3):720-742, 2005. · Zbl 1071.08002
[20] Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. Journal of · Zbl 1132.68725
[21] Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Data complexity of query answering in description logics. In KR, pages 260-270, 2006. · Zbl 1270.68294
[22] Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. EQL-Lite: Effective first-order query processing in description logics. In IJCAI, 2007. · Zbl 1132.68725
[23] Hubie Chen. An algebraic hardness criterion for surjective constraint satisfaction. Algebra Universalis, 72(4):393-401, 2014. · Zbl 1308.08001
[24] Francesco M. Donini, Daniele Nardi, and Riccardo Rosati. Description logics of minimal knowledge and negation as failure. ACM Transactions on Computational Logic, 3(2):177-225, 2002. · Zbl 1365.68403
[25] Thomas Eiter, Georg Gottlob, and Heikki Mannila. Disjunctive datalog. ACM Trans. Database Syst., 22(3):364-418, 1997.
[26] Tom´as Feder and Moshe Y. Vardi. Monotone monadic SNP and constraint satisfaction. In STOC, pages 612-622, 1993. · Zbl 1310.68086
[27] Cristina Feier, Antti Kuusisto, and Carsten Lutz. Rewritability in monadic disjunctive datalog, mmsnp, and expressive description logics (invited talk). In Proc. ICDT, pages 1:1-1:17, 2017. · Zbl 1402.68046
[28] Jan Foniok, Jaroslav Nesetril, and Claude Tardif. Generalised dualities and maximal finite antichains in the homomorphism order of relational structures. Eur. J. Comb., 29(4):881-899, 2008. · Zbl 1147.05037
[29] Enrico Franconi, Yazmin Ang´elica Ib´a˜nez-Garc´ıa, and ˙Inan¸c Seylan. Query answering with DBoxes is hard. Electronic Notes in Theoretical Computer Science, 278:71-84, 2011. · Zbl 1347.68321
[30] Birte Glimm and Markus Kr¨otzsch. SPARQL beyond subgraph matching. In ISWC, volume 6496 of LNCS, pages 241-256. Springer, 2010.
[31] Stephan Grimm and Boris Motik. Closed world reasoning in the semantic web through epistemic operators. In OWLED, 2005.
[32] Andr´e Hernich, Leonid Libkin, and Nicole Schweikardt. Closed world data exchange. ACM Trans. Database Syst., 36(2):14:1-14:40, 2011.
[33] Andr´e Hernich, Carsten Lutz, Fabio Papacchini, and Frank Wolter. Dichotomies in ontology-mediated querying with the guarded fragment. In Proc. of PODS, pages 185-199, 2017. · Zbl 1446.68056
[34] Ullrich Hustadt, Boris Motik, and Ulrike Sattler. Data complexity of reasoning in very expressive description logics. In Proc. of IJCAI, pages 466-471, 2005. · Zbl 1146.68456
[35] ˙Inan¸c Seylan, Enrico Franconi, and Jos de Bruijn. Effective query rewriting with ontologies over DBoxes. In IJCAI, 2009.
[36] Roman Kontchakov, Carsten Lutz, David Toman, Frank Wolter, and Michael Zakharyaschev. The combined approach to query answering in DL-Lite. In KR, 2010.
[37] Roman Kontchakov and Michael Zakharyaschev. An introduction to description logics and query rewriting. In Proc. of Reasoning Web, pages 195-244, 2014.
[38] Adila Krisnadhi and Carsten Lutz. Data complexity in the EL family of description logics. In Proc. LPAR, pages 333-347, 2007. · Zbl 1137.68593
[39] Andrei A. Krokhin. Tree dualities for constraint satisfaction. In CSL, pages 32-33, 2010. · Zbl 1287.68156
[40] Markus Kr¨otzsch, Frederick Maier, Adila Krisnadhi, and Pascal Hitzler. A better uncle for OWL: nominal schemas for integrating rules and ontologies. In Proc. of WWW, pages 645-654. ACM, 2011.
[41] Markus Kr¨otzsch and Sebastian Rudolph. Nominal schemas in description logics: Complexities clarified. In Proc. of KR. AAAI Press, 2014.
[42] Leonid Libkin and Cristina Sirangelo. Data exchange and schema mappings in open and closed worlds. J. Comput. Syst. Sci., 77(3):542-571, 2011. · Zbl 1215.68093
[43] Carsten Lutz, Inan¸c Seylan, and Frank Wolter. Ontology-mediated queries with closed predicates. In Proc. of IJCAI, pages 3120-3126. AAAI Press, 2015.
[44] Carsten Lutz, ˙Inan¸c Seylan, and Frank Wolter. Ontology-based data access with closed predicates is inherently intractable (sometimes). In Proc. of IJCAI, pages 1024-1030, 2013.
[45] Carsten Lutz and Frank Wolter. Deciding inseparability and conservative extensions in the description logic EL. Journal of Symbolic Computation, 45(2):194-228, 2010. · Zbl 1187.68572
[46] Carsten Lutz and Frank Wolter. The data complexity of description logic ontologies. Logical Methods in Computer Science, 13(4), 2017. · Zbl 1398.68517
[47] Anees Mehdi, Sebastian Rudolph, and Stephan Grimm. Epistemic querying of OWL knowledge bases. In ESWC, 2011.
[48] Boris Motik, Ian Horrocks, and Ulrike Sattler. Bridging the gap between OWL and relational databases. Journal of Web Semantics, 7(2):74-89, 2009.
[49] Boris Motik and Riccardo Rosati. Reconciling description logics and rules. Journal of the ACM, 57(5):1-62, 2010. · Zbl 1327.68257
[50] Nhung Ngo, Magdalena Ortiz, and Mantas Simkus. Closed predicates in description logics: Results on combined complexity. In Proc. of KR, pages 237-246, 2016.
[51] Magdalena Ortiz, Diego Calvanese, and Thomas Eiter. Data complexity of query answering in expressive description logics via tableaux. Journal of Automated Reasoning, 41(1):61-98, 2008. · Zbl 1154.68102
[52] Antonella Poggi, Domenico Lembo, Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Riccardo Rosati. Linking data to ontologies. J. Data Semantics, 10:133-173, 2008. · Zbl 1132.68061
[53] Raymond Reiter. What should a database know? Journal of Logic Programming, 14(1&2):127-153, 1992. · Zbl 0777.68035
[54] Andrea Schaerf. On the complexity of the instance checking problem in concept languages with existential quantification. Journal of Intelligent Information Systems, 2:265-278, 1993.
[55] Kunal Sengupta, Adila Alfa Krisnadhi, and Pascal Hitzler. Local closed world semantics: Grounded circumscription for OWL. In ISWC, 2011.
[56] Balder ten Cate, Enrico Franconi, and ˙Inan¸c Seylan. Beth definability in expressive description logics. Journal of Artificial Intelligence Research, 48:347-414, 2013. · Zbl 1442.68223
[57] Guohui Xiao, Diego Calvanese, Roman Kontchakov, Domenico Lembo, Antonella Poggi, Riccardo Rosati, and Michael Zakharyaschev. Ontology-based data access: A survey. In Proc. of IJCAI, pages 5511-5519, 2018.
[58] Dmitriy Zhuk. A proof of CSP dichotomy conjecture. In Proc. of FOCS, pages 331-342, 2017.
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.