Lexicographic Repair Under Querying Prioritised DL-Lite Knowledge Bases

(Telli Abdelmoutia , Hamdi Ghassen and Omri Mohamed Nazih )

---

Abstract

This article discusses the issue of inconsistency in responses from various DL-Lite knowledge bases. This inconsistency problem is at the origin of several sources of assertions with different levels of reliability. The various solutions proposed in the literature that have to do with retrieving an exhaustive and coherent list of responses are not satisfactory from the point of view of reliability and performance. The solution that we present to solve this problem is articulated around two phases: the first phase consists of interrogating the different knowledge bases to retrieve all of the possible answers, which may be inconsistent and/or contradictory, and the second phase consists in repairing these inconsistencies and/or contradictions. To do this, we propose an approach based on three algorithms that we developed in this framework: a first algorithm for non-defeat repair, a second algorithm for lexicographic repair and a third algorithm for non-defeat repair based on lexicography of possible inconsistent responses. The experimental study carried out on the different data collections, as well as the analysis of the results obtained, confirm the performance of our approach as well as its efficiency in regards to productivity and complexity in terms of execution time.

KEYWORDS
Description logics, conjunctive query, answer profile, inconsistent information

PDF

References

Arenas, M., Bertossi, L. and Chomicki, J. (1999). Consistent query answers in inconsistent databases. In: Proceedings of the Eighteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Philadelphia, Pennsylvania, 31/05–02/06/1999. (pp. 68-79)
Artale, A., Calvanese, D., Kontchakov, R. and  Zakharyaschev, M. (2009). The DL-Lite family and relations. Journal of Artificial Intelligence Research, 36(1), 1–69. 
Baget, J.F., Benferhat, S., Bouraoui, Z., Croitoru, M., Mugnier, M.L., Papini, O., Rocher, S. and Tabia, K. (2016). 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'16), Cape Town, South Africa, 04–25/04/2016.
Baral, C., Kraus, S. and Minker, J. (1991). Combining multiple knowledge bases. IEEE Transactions on Knowledge and Data Engineering, 3(2), 208–20.
Baral, C., Kraus, S., Minker, J. and Subrahmanian, V.S. (1972). Combining knowledge bases consisting of first-order analysis. Comput. Intell. 8(1), 45–71.
Benferhat, S., Bouraoui, Z. and Tabia, K. (2015). How to select one preferred assertional-based repair from Inconsistent and prioritised DL-lite knowledge bases? In: 24th International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina, 25/07–01/08/2015.
Benferhat, S., Bouraoui, Z., Croitoru, M., Papini, O. and Tabia, K. (2016). Non-objection inference for inconsistency-tolerant query answering. In: International Joint Conference on Artificial Intelligence, New York, United States, 09–15/07/2016.
Benferhat, S., Cayrol, C., Dubois, D., Lang, J. and Prade, H. (1993). Inconsistency management and prioritised syntax-based entailment. In: International Joint Conference on Artificial Intelligence, Chambery, France, 28/08–03/09/1993.
Benferhat, S., Dubois, D. and Prade, H. (1992). Representing default rules in possibilistic logic. In: Proc. of the 3rd Inter. Conf. on Principles of Knowledge Representation and Reasoning (KR'92), Cambridge, MA, USA, 09–25/10/1992.
Benferhat, S., Dubois, D. and Prade, H. (1995). How to infer from inconsistent beliefs without revising? In: International Joint Conference on Artificial Intelligence, Montreal, Quebec, Canada, 05–20/08/1995.
Benferhat, S., Dubois, D. and Prade, H. (1997). Some syntactic approaches to the handling of inconsistent knowledge bases: A comparative study part 1: The flat case. Studia Logica, 58(1), 17–45.
Bertossi, L. (2011). Database repairing and consistent query answering. Synthesis Lectures on Data Management, 3(5), 1–121. 
Bienvenu, M. (2012). On the complexity of consistent query answering in the presence of simple ontologies. In: Twenty-Sixth AAAI Conference on Artificial Intelligence, Toronto, Ontario, Canada, 06–22/07/2012.
Bienvenu, M. and Rosati, R. (2013). Tractable approximations of consistent query answering for robust ontology-based data access. In: Twenty-Third International Joint Conference on Artificial Intelligence, Beijing, China, 03–09/08/2013. 
Bienvenu, M., Bourgaux, C. and Goasdoué, F. (2014). Querying inconsistent description logic knowledge bases under preferred repair semantics. In: AAAI Conference on Artificial Intelligence, Québec, Canada, 27–31/07/2014.
Bienvenu, M., Bourgaux, C. and Goasdoué, F. (2016). Query-driven repairing of inconsistent DL-Lite knowledge bases. In: International Joint Conference on Artificial Intelligence, New York, United States, 09–15/07/2016.
Bienvenu, M., Bourgaux, C. and Goasdoué, F. (2019). Computing and explaining query answers over inconsistent DL-Lite knowledge bases. Journal of Artificial Intelligence Research, 64(n/a), 563–644.
Boughammoura, R. and Omri, M.N. (2017). Querying deep web data bases without accessing to data. In: 13th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD), Guilin, China, 29–30/09/2017.
Boughammoura, R., Hlaoua, L. and Omri, M.N. (2015). G-form: A collaborative design approach to regard deep web form as galaxy of concepts. In, International Conference on Cooperative Design, Visualization and Engineering, Mallorca, Spain, 3–20/09/2015.
Boughammoura, R., Omri, M.N. and Hlaoua, L. (2012). Information retrieval from deep web based on visual query interpretation. International Journal of Information Retrieval Research (IJIRR), 2(4), 45–59.
Brewka, G. (1989). Preferred subtheories: An extended logical framework for default reasoning. In: International Joint Conference on Artificial Intelligence, Detroit, MI, USA, 05–20/08/1989.
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M. and Rosati, R. (2005). DL-Lite: Tractable description logics for ontologies. In: AAAI Conference on Artificial Intelligence, Pittsburgh, Pennsylvania, 09–13/07/2005.
Chomicki, J. (2007). Consistent query answering: Five easy pieces. In: International Conference on Database Theory, Barcelona, Spain, 02–10/01/2007.
Dixit, A.A. (2019). CAvSAT: A system for query answering over inconsistent databases. In: Proceedings of the 2019 International Conference on Management of Data, Amsterdam, The Netherlands, 30/05–05/06/2019.
Du, J., Qi, G. and Shen, Y.D. (2013). Weight-based consistent query answering over inconsistent SHIQ knowledge bases. Knowledge and Information Systems, 34(2), 335–71.
Hamdi, G., Omri, M.N., Benferhat, S., Bouraoui, Z. and Papini, O. (2020). Query answering dl-lite knowledge bases from hidden datasets. Annals of Mathematics and Artificial Intelligence. DOI: 10.1007/s10472-020-09714-2
Hamdi, G., Telli, A. and Omri, M.N., (2020). Querying of several DL-Lite knowledge bases from various information sources-based polynomial response unification approach. Journal of King Saud University-Computer and Information Sciences. DOI: 10.1016/j.jksuci.2020.06.002
Lembo, D., Lenzerini, M., Rosati, R., Ruzzi, M. and Savo, D. F. (2010). Inconsistency-tolerant semantics for description logics. In: International Conference on Web Reasoning and Rule Systems, Bressanone, Italy, 23–24/09/2010.
Lenzerini, M. (2011, October 24–28). Ontology-based data management. In: Proceedings of the 20th ACM International Conference On Information And Knowledge Management, Glasgow, Scotland, UK.
Lukasiewicz, T., Martinez, M.V. and Simari, G.I. (2012). Inconsistency handling in datalog+/-ontologies. In: Proceedings of the 20th European Conference on Artificial Intelligence, Montpellier, France, 27–31/08/2012.
Lukasiewicz, T., Martinez, M. V., Pieris, A. and Simari, G. I. (2015). From classical to consistent query answering under existential rules. In: Proceedings of the AAAI Conference on Artificial Intelligence, Austin Texas, USA, 25–30/01/2015.
Lutz, C., Seylan, I., Toman, D. and Wolter, F. (2013). The combined approach to OBDA: Taming role hierarchies using filters. In: International Semantic Web Conference, Sydney, Australia, 21–25/10/2013.
Martinez, M.V., Parisi, F., Pugliese, A., Simari, G.I. and Subrahmanian, V.S. (2008). Inconsistency management policies. In: Principles of Knowledge Representation and Reasoning, Sydney, Australia, 16–19/09/2008.
Nebel, B. (1994). Base revision operations and schemes: Semantics, representation, and complexity. In:  11th European Conference on Artificial Intelligence, Amsterdam, Netherlands, 8–12/08/1994.
Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M. and Rosati, R. (2008). Linking data to ontologies. Journal on Data Semantics X, 10(n/a), 133–73. 
Rescher, N. and Manor, R. (1970). On inference from inconsistent premisses. Theory and Decision, 1(2), 179–217. 
Staworko, S., Chomicki, J. and Marcinkowski, J. (2012). Prioritised repairing and consistent query answering in relational databases. Annals of Mathematics and Artificial Intelligence, 64(2-3), 209–46.
Telli, A., Benferhat, S., Bourahla, M., Bouraoui, Z. and Tabia, K. (2017). Polynomial algorithms for computing a single preferred assertional-based repair. KI-Künstliche Intelligenz, 31(1), 15–30.
Trivela, D., Stoilos, G. and Vassalos, V. (2019). Query rewriting for DL ontologies under the ICAR semantics. In: International Joint Conference on Rules and Reasoning, Macao, China, 10–16/08/2019.