Abstract
Non-standard query mechanisms that work under inconsistency are required in some important description logic (DL)-based applications, including those involving an inconsistent DL knowledge base ( KB) whose intensional knowledge is consistent but is violated by its extensional knowledge. This paper proposes a weight-based semantics for querying such an inconsistent KB. This semantics defines an answer of a conjunctive query posed upon an inconsistent KB as a tuple of individuals whose substitution for the variables in the query head makes the query body entailed by any subbase of the KB consisting of the intensional knowledge and a weight-maximally consistent subset of the extensional knowledge. A novel computational method for this semantics is proposed, which works for extensionally reduced \({\mathcal {SHIQ}}\) KBs and conjunctive queries without non-distinguished variables. The method first compiles the given KB to a propositional program; then, for any given conjunctive query, it reduces the problem of computing all answers of the given query to a set of propositional satisfiability (SAT) problems with PB-constraints, which are then solved by SAT solvers. A decomposition-based framework for optimizing the method is also proposed. The feasibility of this method is demonstrated in our experiments.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Arenas M, Bertossi LE Chomicki J (1999) Consistent query answers in inconsistent databases. In: Proceedings of the 18th ACM symposium on principles of database systems (PODS), pp 68–79
Arenas M, Bertossi LE, Chomicki J (2003) Answer sets for consistent query answering in inconsistent databases. Theory Pract Logic Program 3(4–5): 393–424
Arieli O, Denecker M, NuffelenBV Bruynooghe M (2004) Coherent integration of databases by abductive logic programming. J Artif Intell Res 21: 245–286
Aspvall B, Plass MF, Tarjan RE (1979) A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inf Process Lett 8(3): 121–123
Baader, F, Calvanese, D, McGuinness, DL, Nardi, D, Patel-Schneider, PF (eds) (2003) The description logic handbook: theory, implementation, and applications. Cambridge University Press, Cambridge
Bailleux O, Boufkhad Y, Roussel O (2006) A translation of pseudo boolean constraints to SAT. J Satisf Boolean Model Comput 2: 191–200
Benferhat S, Cayrol C, Dubois D, Lang J, Prade H (1993) Inconsistency management and prioritized syntax-based entailment. In: Bajcsy R (eds) Proceedings of the 13th international joint conference on artificial intelligence (IJCAI), pp 640–647
Benferhat S, Dubois D, Prade H (1995) How to infer from inconsisent beliefs without revising? In: Proceedings of the 14th international joint conference on artificial intelligence (IJCAI), pp 1449–1457
Bertossi LE, Chomicki J (2003) Query answering in inconsistent databases. In: Chomicki J, Meyden R, Saake G (eds) Logics for emerging applications of databases. Springer, pp 43–83
Calvanese D, Giacomo G, Lembo D, Lenzerini M, Rosati R (2005) DL-Lite: tractable description logics for ontologies. In: Veloso M, Kambhampati S (eds) Proceedings of the 20th national conference on artificial intelligence (AAAI), pp 602–607
Calvanese D, Giacomo G, Lembo D, Lenzerini M, Rosati R (2007) Tractable reasoning and efficient query answering in description logics: the DL-Lite family. J Autom Reason 39(3): 385–429
Chai D, Kuehlmann A (2003) A fast pseudo-boolean constraint solver. In: Proceedings of the 40th design automation conference (DAC), pp 830–835
Chomicki J (2007) Consistent query answering: five easy pieces. In: Schwentick T, Suciu D (eds) Proceedings of the 11th international conference on database theory (ICDT), pp 1–17
Cimiano P (2006) Ontology learning and population from text algorithms evaluation and applications. Springer, Berlin
Cimiano P, Völker J (2005) Text2onto—a framework for ontology learning and data-driven change discovery. In: Montoyo A, Muñoz R, Métais E (eds) Proceedings of the 10th international conference on applications of natural language to information systems (NLDB), pp 227–238
de Saint-Cyr F, Lang J, Schiex T (1994) Penalty logic and its link with dempster-shafer theory. In: Mántaras R, Poole D (eds) Proceedings of the 10th annual conference on uncertainty in artificial intelligence (UAI), pp 204–211
Dolby J, Fokoue A, Kalyanpur A, Ma L, Schonberg E, Srinivas K, Sun X (2008) Scalable grounded conjunctive query evaluation over large and expressive knowledge bases. In: Sheth AP, Staab S, Dean M, Paolucci M, Maynard D, Finin TW, Thirunarayan K (eds) Proceedings of the 7th international semantic web conference (ISWC), pp 403–418
Du J, Shen Y (2008) Computing minimum cost diagnoses to repair populated DL-based ontologies. In: Huai J, Chen R, Hon H, Liu Y, Ma W, Tomkins A, Zhang X (eds) Proceedings of the 17th international world wide web conference (WWW), pp 575–584
Eén N, Sörensson N (2006) Translating pseudo-boolean constraints into SAT. J Satisf Boolean Model Comput 2: 1–26
Eiter T, Gottlob G (1995) The complexity of logic-based abduction. J ACM 42(1): 3–42
Eiter T, Gottlob G, Mannila H (1997) Disjunctive datalog. ACM Trans Database Syst 22(3): 364–418
Eiter T, Leone N, Mateis C, Pfeifer G, Scarcello F (1997) A deductive system for non-monotonic reasoning. In: Dix J, Furbach U, Nerode A (eds) Proceedings of the 4th international conference on logic programming and nonmonotonic reasoning (LPNMR), pp 364–375
Feldman R, Rosenfeld B, Fresko M (2006) TEG—a hybrid approach to information extraction. Knowl Inf Syst 9(1): 1–18
Fitting M (1996) First-order logic and automated theorem proving. Springer, Secaucus
Guo Y, Pan Z, Heflin J (2005) LUBM: a benchmark for OWL knowledge base systems. J Web Semant 3(2–3): 158–182
Haarslev V, Möller R (2001) Racer system description. In: Goré R, Leitsch A, Nipkow T (eds) Proceedings of the 1st international joint conference on automated reasoning (IJCAR), pp 701–706
Horrocks I, Patel-Schneider PF, van Harmelen F (2003) From \({\mathcal{SHIQ} }\) and RDF to OWL: the making of a web ontology language. J Web Semant 1(1): 7–26
Horrocks I, Sattler U, Tobies S (2000) Practical reasoning for very expressive description logics. Logic J IGPL 8(3): 239–263
Huang Z, van Harmelen F, ten Teije A (2005) Reasoning with inconsistent ontologies. In: Kaelbling LP, Saffiotti A (eds) Proceedings of the 19th international joint conference on artificial intelligence (IJCAI), pp 454–459
Hustadt U, Motik B, Sattler U (2004) Reducing \({\mathcal{SHIQ}^-}\) description logic to disjunctive datalog programs. In: Proceedings of the 9th international conference on principles of knowledge representation and reasoning (KR), pp 152–162
Hustadt U, Motik B, Sattler U (2007) Reasoning in description logics by a reduction to disjunctive datalog. J Autom Reason 39(3): 351–384
Kazakov Y, Motik B (2008) A resolution-based decision procedure for \({\mathcal{SHOIQ}}\). J Autom Reason 40(2–3): 89–116
Lembo D, Ruzzi M (2007) Consistent query answering over description logic ontologies. In: Marchiori M, Pan JZ, Marie C (eds) Proceedings of the 1st international conference on web reasoning and rule systems (RR), pp 194–208
Lopatenko A, Bertossi LE (2007) Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics. In: Schwentick T, Suciu D (eds) Proceedings of the 11th international conference on database theory (ICDT), pp 179–193
Ma L, Yang Y, Qiu Z, Xie G, Pan Y, Liu S (2006) Towards a complete OWL ontology benchmark. In: Sure Y, Domingue J (eds) Proceedings of the 3rd European semantic web conference (ESWC), pp 125–139
Ma Y, Hitzler P, Lin Z (2007) Algorithms for paraconsistent reasoning with OWL. In: Franconi E, Kifer M, May W (eds) Proceedings of the 4th European semantic web conference (ESWC), pp 399–413
McDowell L, Cafarella MJ (2008) Ontology-driven, unsupervised instance population. J Web Semant 6(3): 218–236
Meyer T, Lee K, Booth R (2005) Knowledge integration for description logics. In: Veloso M, Kambhampati S (eds) Proceedings of the 20th national conference on artificial intelligence (AAAI), pp 645–650
Odintsov SP, Wansing H (2003) Inconsistency-tolerant description logic: motivation and basic systems. Kluwer, Dordrecht, pp 301–335
Patel-Schneider PF, Hayes P, Horrocks I (eds) (2004) OWL web ontology language semantics and abstract syntax. W3C recommendation. http://www.w3.org/TR/owl-semantics/
Popov B, Kiryakov A, Kirilov A, Manov D, Ognyanoff D, Goranov M (2003) Kim—semantic annotation platform. In: Fensel D, Sycara KP, Mylopoulos J (eds) Proceedings of the 2nd international semantic web conference (ISWC), pp 834–849
Qi G, Ji Q, Pan JZ, Du J (2011) Extending description logics with uncertainty reasoning in possibilistic logic. Int J Intell Syst 26(4): 353–381
Qi G, Liu W, Bell D (2006) A revision-based approach to handling inconsistency in description logics. Artif Intell Rev 26(1–2): 115–128
Rao AS, Foo NY (1989) Minimal change and maximal coherence: a basis for belief revision and reasoning about actions. In: Sridharan NS (eds) Proceedings of the 11th international joint conference on artificial intelligence (IJCAI), pp 966–971
Sattler K, Geist I, Schallehn E (2005) Concept-based querying in mediator systems. VLDB J 14(1): 97–111
Shadbolt N, Berners-Lee T, Hall W (2006) The semantic web revisited. IEEE Intell Syst 21(3): 96–101
Shchekotykhin K, Jannach D, Friedrich G (2010) xCrawl: a high-recall crawling method for web mining. Knowl Inf Syst 25(2): 303–326
Sheini HM, Sakallah KA (2006) Pueblo: a hybrid pseudo-boolean SAT solver. J Satisf Boolean Model Comput 2: 157–181
Song M, Rudniy A (2010) Detecting duplicate biological entities using Markov random field-based edit distance. Knowl Inf Syst 25(2): 371–387
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Du, J., Qi, G. & Shen, YD. Weight-based consistent query answering over inconsistent \({\mathcal {SHIQ}}\) knowledge bases. Knowl Inf Syst 34, 335–371 (2013). https://doi.org/10.1007/s10115-012-0478-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10115-012-0478-9