×

zbMATH — the first resource for mathematics

Inconsistency-tolerant query answering: rationality properties and computational complexity analysis. (English) Zbl 06658153
Michael, Loizos (ed.) et al., Logics in artificial intelligence. 15th European conference, JELIA 2016, Larnaca, Cyprus, November 9–11, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-48757-1/pbk; 978-3-319-48758-8/ebook). Lecture Notes in Computer Science 10021. Lecture Notes in Artificial Intelligence, 64-80 (2016).
Summary: Generalising the state of the art, an inconsistency-tolerant semantics can be seen as a couple composed of a modifier operator and an inference strategy. In this paper we deepen the analysis of such general setting and focus on two aspects. First, we investigate the rationality properties of such semantics for existential rule knowledge bases. Second, we unfold the broad landscape of complexity results of inconsistency-tolerant semantics under a specific (yet expressive) subclass of existential rules.
For the entire collection see [Zbl 1350.68015].

MSC:
68T27 Logic in artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arenas, M., Bertossi, L.E., Chomicki, J.: Consistent query answers in inconsistent databases. In: Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 68–79 (1999) · Zbl 1079.68026 · doi:10.1145/303976.303983
[2] Baget, J.-F., Benferhat, S., Bouraoui, Z., Croitoru, M., Mugnier, M.-L., Papini, O., Rocher, S., Tabia, K.: A general modifier-based framework for inconsistency-tolerant query answering. In: Proceedings of the Fifteenth International Conference on Principles of Knowledge Representation and Reasoning, KR (2016) · Zbl 06658153
[3] Baget, J.-F., Leclère, M., Mugnier, M.-L., Salvat, E.: On rules with existential variables: Walking the decidability line. Artif. Intell. 175(9–10), 1620–1654 (2011) · Zbl 1225.68247 · doi:10.1016/j.artint.2011.03.002
[4] Benferhat, S., Bouraoui, Z., Croitoru, M., Papini, O., Tabia, K.: Non-objection inference for inconsistency-tolerant query answering. In: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (2016) · Zbl 06658153
[5] Benferhat, S., Cayrol, C., Dubois, D., Lang, J., Prade, H.: Inconsistency management and prioritized syntax-based entailment. In: Proceedings of the 13th International Joint Conference on Artificial Intelligence, pp. 640–647 (1993)
[6] Bienvenu, M.: On the complexity of consistent query answering in the presence of simple ontologies. In: Proceedings of the Twenty-Sixth Conference on Artificial Intelligence (2012)
[7] Bienvenu, M., Bourgaux, C., Goasdoué, F.: Querying inconsistent description logic knowledge bases under preferred repair semantics. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, pp. 996–1002 (2014)
[8] Calì, A., Gottlob, G., Pieris, A.: Towards more expressive ontology languages: the query answering problem. Artif. Intell. 193, 87–128 (2012) · Zbl 1270.68293 · doi:10.1016/j.artint.2012.08.002
[9] Calì, A., Gottlob, G., Lukasiewicz, T.: A general datalog-based framework for tractable query answering over ontologies. J. Web Sem. 14, 57–83 (2012) · doi:10.1016/j.websem.2012.03.001
[10] 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. 39(3), 385–429 (2007) · Zbl 1132.68725 · doi:10.1007/s10817-007-9078-x
[11] Casini, G., Straccia, U.: Rational closure for defeasible description logics. In: Janhunen, T., Niemelä, I. (eds.) JELIA 2010. LNCS (LNAI), vol. 6341, pp. 77–90. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-15675-5_9 · Zbl 1306.68187 · doi:10.1007/978-3-642-15675-5_9
[12] Gärdenfors, P., Makinson, D.: Nonmonotonic inference based on expectations. Artif. Intell. 65(2), 197–245 (1994) · Zbl 0803.68125 · doi:10.1016/0004-3702(94)90017-5
[13] Gill, J.: Computational complexity of probabilistic turing machines. SIAM J. Comput. 6(4), 675–695 (1977) · Zbl 0366.02024 · doi:10.1137/0206049
[14] Kraus, S., Lehmann, D.J., Magidor, M.: Nonmonotonic reasoning, preferential models and cumulative logics. Artif. Intell. 44(1–2), 167–207 (1990) · Zbl 0782.03012 · doi:10.1016/0004-3702(90)90101-5
[15] 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
[16] Lembo, D., Lenzerini, M., Rosati, R., Ruzzi, M., Savo, D.F.: Inconsistency-tolerant query answering in ontology-based data access. J. Web Sem. 33, 3–29 (2015) · doi:10.1016/j.websem.2015.04.002
[17] Lenzerini, M.: Ontology-based data management. In: Proceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management 2012, pp. 12–15 (2012)
[18] Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Linking data to ontologies. J. Data Semant. 10, 133–173 (2008) · Zbl 1132.68061
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.