×

zbMATH — the first resource for mathematics

Inconsistency-tolerant querying of description logic knowledge bases. (English) Zbl 1358.68285
Pan, Jeff Z. (ed.) et al., Reasoning web. Logical foundation of knowledge graph construction and query answering. 12th international summer school 2016, Aberdeen, UK, September 5–9, 2016. Tutorial lectures. Cham: Springer (ISBN 978-3-319-49492-0/pbk; 978-3-319-49493-7/ebook). Lecture Notes in Computer Science 9885, 156-202 (2017).
Summary: An important issue that arises when querying description logic (DL) knowledge bases is how to handle the case in which the knowledge base is inconsistent. Indeed, while it may be reasonable to assume that the TBox (ontology) has been properly debugged, the ABox (data) will typically be very large and subject to frequent modifications, both of which make errors likely. As standard DL semantics is useless in such circumstances (everything is entailed from a contradiction), several alternative inconsistency-tolerant semantics have been proposed with the aim of providing meaningful answers to queries in the presence of such data inconsistencies. In the first part of this chapter, we present and compare these inconsistency-tolerant semantics, which can be applied to any DL (or ontology language). The second half of the chapter summarizes what is known about the computational properties of these semantics and gives an overview of the main algorithmic techniques and existing systems, focusing on DLs of the DL-Lite family.
For the entire collection see [Zbl 1358.68016].
MSC:
68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence
68T27 Logic in artificial intelligence
68T30 Knowledge representation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bienvenu, M., Ortiz, M.: Ontology-mediated query answering with data-tractable description logics. In: Faber, W., Paschke, A. (eds.) Reasoning Web 2015. LNCS, vol. 9203, pp. 218–307. Springer, Heidelberg (2015). doi: 10.1007/978-3-319-21768-0_9 · Zbl 1358.68086 · doi:10.1007/978-3-319-21768-0_9
[2] 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 (2003) · Zbl 1058.68107
[3] OWL Working Group. OWL 2 Web Ontology Language: Document Overview. W3C Recommendation (2009). http://www.w3.org/TR/owl2-overview/
[4] Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: the DL-Lite family. J. Autom. Reason. (JAR) 39(3), 385–429 (2007) · Zbl 1132.68725 · doi:10.1007/s10817-007-9078-x
[5] Lembo, D., Lenzerini, M., Rosati, R., Ruzzi, M., Savo, D.F.: Inconsistency-tolerant semantics for description logics. In: Hitzler, P., Lukasiewicz, T. (eds.) RR 2010. LNCS, vol. 6333, pp. 103–117. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-15918-3_9 · Zbl 05804116 · doi:10.1007/978-3-642-15918-3_9
[6] Arenas, M., Bertossi, L.E., Chomicki, J.: Consistent query answers in inconsistent databases. In: Proceedings of the 18th Symposium on Principles of Database Systems (PODS), pp. 68–79 (1999) · Zbl 1079.68026 · doi:10.1145/303976.303983
[7] Arenas, M., Bertossi, L., Kifer, M.: Applications of annotated predicate calculus to querying inconsistent databases. In: Lloyd, J., et al. (eds.) CL 2000. LNCS (LNAI), vol. 1861, pp. 926–941. Springer, Heidelberg (2000). doi: 10.1007/3-540-44957-4_62 · Zbl 0983.68054 · doi:10.1007/3-540-44957-4_62
[8] Chomicki, J.: Consistent query answering: five easy pieces. In Proceedings of the 10th International Conference on Database Theory (ICDT), pp. 1–17 (2007)
[9] Bertossi, L.E.: Database Repairing and Consistent Query Answering: Synthesis Lectures on Data Management. Morgan & Claypool Publishers, San Rafael (2011)
[10] Bienvenu, M., Rosati, R.: Tractable approximations of consistent query answering for robust ontology-based data access. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI) (2013)
[11] Motik, B., Cuenca Grau, B., Horrocks, I., Wu, Z., Fokoue, A., Lutz, C.: OWL 2 Web Ontology Language Profiles. W3C Recommendation (2012). http://www.w3.org/TR/owl2-profiles/
[12] Immerman, N.: Nondeterministic space is closed under complementation. SIAM J. Comput. 17(5), 935–938 (1988) · Zbl 0668.68056 · doi:10.1137/0217058
[13] Szelepcsényi, R.: The method of forcing for nondeterministic automata. Bull. EATCS 33, 96–99 (1987) · Zbl 0664.68082
[14] Bienvenu, M.: On the complexity of consistent query answering in the presence of simple ontologies. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence (2012)
[15] Lukasiewicz, T., Martinez, M.V., Simari, G.I.: Inconsistency handling in datalog \[ +/- \] ontologies. In: Proceedings of the 20th European Conference on Artificial Intelligence (ECAI) (2012) · Zbl 1327.68280
[16] Bienvenu, M., Bourgaux, C., Goasdoué, F.: Querying inconsistent description logic knowledge bases under preferred repair semantics. In: Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI) (2014)
[17] Bourgaux,C.: Inconsistency handling in ontology-mediated query answering. Ph.D. thesis, University of Paris-Sud (2016)
[18] Baader, F., Brandt, S., Lutz, C.: Pushing the \[ \mathcal{EL} \] envelope. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI), pp. 364–369 (2005)
[19] Calvanese, D., Giacomo, G.D., Lembo, D., Lenzerini, M., Rosati, R.: Data complexity of query answering in description logics. In: Proceedings of the 10th International Conference on the Principles of Knowledge Representation and Reasoning (KR), pp. 260–270 (2006) · Zbl 1270.68294
[20] Rosati, R.: On conjunctive query answering in \[ \mathcal{EL} \] . In: Proceedings of the 20th International Workshop on Description Logics (DL) (2007)
[21] Krötzsch, M., Rudolph, S.: Conjunctive queries for \[ \mathcal{EL} \] with composition of roles. In: Proceedings of the 20th International Workshop on Description Logics (DL) (2007)
[22] Krisnadhi, A., Lutz, C.: Data complexity in the \[ \mathcal{EL} \] family of DLs. In: Proceedings of the 20th International Workshop on Description Logics (DL) (2007) · Zbl 1137.68593
[23] Rosati, R.: On the complexity of dealing with inconsistency in description logic ontologies. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI) (2011)
[24] Lukasiewicz, T., Martinez, M.V., Simari, G.I.: Complexity of inconsistency-tolerant query answering in datalog \[ +/- \] . In: Meersman, R., Panetto, H., Dillon, T., Eder, J., Bellahsene, Z., Ritter, N., Leenheer, P., Dou, D. (eds.) OTM 2013. LNCS, vol. 8185, pp. 488–500. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-41030-7_35 · Zbl 06360370 · doi:10.1007/978-3-642-41030-7_35
[25] Lukasiewicz, T., Martinez, M.V., Pieris, A., Simari, G.I.: From classical to consistent query answering under existential rules. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence, pp. 1546–1552 (2015)
[26] Eiter, T., Gottlob, G.: The complexity of logic-based abduction. J. ACM 42(1), 3–42 (1995) · Zbl 0886.68121 · doi:10.1145/200836.200838
[27] Baget, J., Benferhat, S., Bouraoui, Z., Croitoru, M., Mugnier, M., Papini, O., Rocher, S., Tabia, K.: A general modifier-based framework for inconsistency-tolerant query answering. In: Proceedings of the 15th International Conference on the Principles of Knowledge Representation and Reasoning (KR), pp. 513–516 (2016) · Zbl 06658153
[28] Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family and relations. J. Artif. Intell. Res. (JAIR) 36, 1–69 (2009) · Zbl 1192.68657
[29] Donini, F.M., Lenzerini, M., Nardi, D., Schaerf, A.: Deduction in concept languages: from subsumption to instance checking. J. Log. Comput. (JLC) 4(4), 423–452 (1994) · Zbl 0809.68109 · doi:10.1093/logcom/4.4.423
[30] Lembo, D., Lenzerini, M., Rosati, R., Ruzzi, M., Savo, D.F.: Query rewriting for inconsistent DL-Lite ontologies. In: Rudolph, S., Gutierrez, C. (eds.) RR 2011. LNCS, vol. 6902, pp. 155–169. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-23580-1_12 · Zbl 05949450 · doi:10.1007/978-3-642-23580-1_12
[31] Rosati, R., Ruzzi, M., Graziosi, M., Masotti, G.: Evaluation of techniques for inconsistency handling in OWL 2 QL ontologies. In: Cudré-Mauroux, P., et al. (eds.) ISWC 2012. LNCS, vol. 7650, pp. 337–349. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-35173-0_23 · Zbl 06267614 · doi:10.1007/978-3-642-35173-0_23
[32] Lembo, D., Lenzerini, M., Rosati, R., Ruzzi, M., Savo, D.F.: Inconsistency-tolerant query answering in ontology-based data access. J. Web Semant. (JWS) 33, 3–29 (2015) · doi:10.1016/j.websem.2015.04.002
[33] Du, J., Qi, G., Shen, Y.-D.: Weight-based consistent query answering over inconsistent \[ \mathcal{SHIQ} \] knowledge bases. Knowl. Inf. Syst. 34(2), 335–371 (2013) · doi:10.1007/s10115-012-0478-9
[34] Fuxman, A.D., Miller, R.J.: First-order query rewriting for inconsistent databases. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol. 3363, pp. 337–351. Springer, Heidelberg (2004). doi: 10.1007/978-3-540-30570-5_23 · Zbl 1112.68367 · doi:10.1007/978-3-540-30570-5_23
[35] Fuxman, A., Fazli, E., Miller, R.J.: Conquer: efficient management of inconsistent databases. In: Proceedings of the 31st ACM SIGMOD International Conference on Management of Data, pp. 155–166 (2005) · doi:10.1145/1066157.1066176
[36] Chomicki, J., Marcinkowski, J., Staworko, S.: Computing consistent query answers using conflict hypergraphs. In: Proceedings of the 13th International Conference on Information and Knowledge Management (CIKM), pp. 417–426 (2004) · doi:10.1145/1031171.1031254
[37] Chomicki, J., Marcinkowski, J., Staworko, S.: Hippo: a system for computing consistent answers to a class of SQL queries. In: Bertino, E., Christodoulakis, S., Plexousakis, D., Christophides, V., Koubarakis, M., Böhm, K., Ferrari, E. (eds.) EDBT 2004. LNCS, vol. 2992, pp. 841–844. Springer, Heidelberg (2004). doi: 10.1007/978-3-540-24741-8_53 · doi:10.1007/978-3-540-24741-8_53
[38] Marileo, M.C., Bertossi, L.E.: The consistency extractor system: Answer set programs for consistent query answering in databases. Data Knowl. Eng. 69(6), 545–572 (2010) · Zbl 05841601 · doi:10.1016/j.datak.2010.01.005
[39] Kolaitis, P.G., Pema, E., Tan, W.-C.: Efficient querying of inconsistent databases with binary integer programming. Proc. VLDB Endow. (PVLDB) 6(6), 397–408 (2013) · doi:10.14778/2536336.2536341
[40] Gottlob, G.: NP trees and Carnap’s modal logic. J. ACM 42(2), 421–457 (1995) · Zbl 0886.68069 · doi:10.1145/201019.201031
[41] Wagner, K.W.: More complicated questions about maxima and minima, and some closures of NP. Theoret. Comput. Sci. 51, 53–80 (1987) · Zbl 0653.03027 · doi:10.1016/0304-3975(87)90049-1
[42] Eiter, T., Gottlob, G.: The complexity class \[ \Theta ^P_2 \] : Recent results and applications in AI and modal logic. In: Chlebus, B.S., Czaja, L. (eds.) FCT 1997. LNCS, vol. 1279, pp. 1–18. Springer, Heidelberg (1997). doi: 10.1007/BFb0036168 · doi:10.1007/BFb0036168
[43] Kontchakov, R., Lutz, C., Toman, D., Wolter, F., Zakharyaschev, M.: The combined approach to query answering in DL-Lite. In: Proceedings of the 12th International Conference on the Principles of Knowledge Representation and Reasoning (KR) (2010)
[44] Bienvenu, M., Bourgaux, C., Goasdoué, F.: Explaining inconsistency-tolerant query answering over description logic knowledge bases. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI) (2016)
[45] Bienvenu, M., Bourgaux, C., Goasdoué, F.: Query-driven repairing of inconsistent dllite knowledge bases. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI) (2016)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.