×

Inconsistency-tolerant query answering: rationality properties and computational complexity analysis. (English) Zbl 1483.68393

Michael, Loizos (ed.) et al., Logics in artificial intelligence. 15th European conference, JELIA 2016, Larnaca, Cyprus, November 9–11, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10021, 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:

68T30 Knowledge representation
68Q25 Analysis of algorithms and problem complexity
68T27 Logic in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI Link

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 1483.68393
[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 1483.68393
[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. 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.