Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
KI - Künstliche Intelligenz
Published in: KI - Künstliche Intelligenz 1/2017

23-01-2017 | Technical Contribution

Polynomial Algorithms for Computing a Single Preferred Assertional-Based Repair

Authors: Abdelmoutia Telli, Salem Benferhat, Mustapha Bourahla, Zied Bouraoui, Karim Tabia

Published in: KI - Künstliche Intelligenz | Issue 1/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper investigates different approaches for handling inconsistent DL-Lite knowledge bases in the case where the assertional base is prioritized and inconsistent with the terminological base. The inconsistency problem often happens when the assertions are provided by multiple conflicting sources having different reliability levels. We propose different inference strategies based on the selection of one consistent assertional base, called a preferred repair. For each strategy, a polynomial algorithm for computing the associated single preferred repair is proposed. Selecting a unique repair is important since it allows an efficient handling of queries. We provide experimental studies showing (from a computational point of view) the benefits of selecting one repair when reasoning under inconsistency in lightweight knowledge bases.
previous article Many Facets of Reasoning Under Uncertainty, Inconsistency, Vagueness, and Preferences: A Brief Survey
next article On the Compliance of Rationality Postulates for Inconsistency Measures: A More or Less Complete Picture

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

KI - Künstliche Intelligenz

The Scientific journal "KI – Künstliche Intelligenz" is the official journal of the division for artificial intelligence within the "Gesellschaft für Informatik e.V." (GI) – the German Informatics Society - with constributions from troughout the field of artificial intelligence.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Show more products
Footnotes
1
Positive inclusion axioms are of the form \(B_1\sqsubseteq B_2.\)
 
Literature
1.
Arenas M, Bertossi EL, Chomicki J (1999) Consistent query answers in inconsistent databases. In: Proceedings of the eighteenth ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems, Philadelphia, Pennsylvania, USA, pp 68–79, 1999
2.
Artale A, Calvanese D, Kontchakov R, Zakharyaschev M (2009) The DL-Lite family and relations. J Artif Intell Res (JAIR) 36:1–69MathSciNetMATH
3.
Baral C, Kraus S, Minker J, Subrahmanian VS (1992) Combining knowledge bases consisting of first-order analysis. Comput Intell 8:45–71CrossRef
4.
5.
Benferhat S, Bouraoui Z, Papini O, Würbel E (2014) A prioritized assertional-based revision for DL-Lite knowledge bases. In: European conference on logics in artificial intelligence, volume 8761 of LNCS, pp 442–456. Springer, 2014
6.
Benferhat S, Bouraoui Z, Tabia K (2015) How to select one preferred assertional-based repair from inconsistent and prioritized DL-Lite knowledge bases? In: Yang Q, Wooldridge M (eds) Proceedings of the twenty-fourth international joint conference on artificial intelligence IJCAI 2015, Buenos Aires, Argentina, July 25–31, 2015, pp 1450–1456. AAAI Press, 2015
7.
Benferhat S, Cayrol C, Dubois D, Lang J, Prade H (1993) Inconsistency management and prioritized syntax-based entailment. In: International joint conference on artificial intelligence, pp 640–647. Morgan Kaufmann, 1993
8.
Benferhat S, Didier D, Henri P (1997) Some syntactic approaches to the handling of inconsistent knowledge bases: a comparative study part 1: The flat case. Studia Logica 58(1):17–45MathSciNetCrossRefMATH
9.
Benferhat S, Dubois D, Prade H (1992) Representing default rules in possibilistic logic. In: Knowledge representation and reasoning, pp 673–684. Morgan Kaufmann, 1992
10.
Benferhat S, Dubois D, Prade H (1995) How to infer from inconsistent beliefs without revising? In: International joint conference on artificial intelligence, pp 1449–1457. Morgan Kaufmann, 1995
11.
Benferhat S, Dubois D, Prade H (1998) Some syntactic approaches to the handling of inconsistent knowledge bases: a comparative study. Part 2: the prioritized case, volume 24, pp 473–511. Physica-Verlag, Heidelberg, 1998
12.
Bertossi LE (2011) Database repairing and consistent query answering. Synthesis lectures on data management. Morgan & Claypool Publishers, San Rafael
13.
Bienvenu M (2012) On the complexity of consistent query answering in the presence of simple ontologies. In: Proceedings of the twenty-sixth AAAI conference on artificial intelligence, 2012
14.
Bienvenu M, Bourgaux C, Goasdoué F (2014) Querying inconsistent description logic knowledge bases under preferred repair semantics. In: AAAI, pp 996–1002, 2014
15.
Bienvenu M, Rosati R (2013) Tractable approximations of consistent query answering for robust ontology-based data access. In: International joint conference on artificial intelligence. IJCAI/AAAI, 2013
16.
Brewka G (1989) Preferred subtheories: an extended logical framework for default reasoning. In: Sridharan NS (ed) International joint conference on artificial intelligence, pp 1043–1048. Morgan Kaufmann, 1989
17.
Calvanese D, De 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–429MathSciNetCrossRefMATH
18.
Calvanese D, Kharlamov E, Nutt W, Zheleznyakov D (2010) Evolution of DL-Lite knowledge bases. Int Semant Web Conf 1:112–128
19.
Chomicki J (2007) Consistent query answering: five easy pieces. In: Database theory—ICDT 2007, volume 4353 of lecture notes in computer science, pp 1–17. Springer, 2007
20.
Didier D, Lang J, Henri P (1994) Possibilistic logic. In: Volume 3 of handbook on logic in artificial intelligence and logic programming, pp 439–513. Oxford University press, 1994
21.
Du J, Qi G, Shen Y (2013) Weight-based consistent query answering over inconsistent SHIQ knowledge bases. Knowl Inform Syst 34(2):335–371CrossRef
22.
23.
24.
Lembo D, Lenzerini M, Rosati R, Ruzzi M, Fabio Savo D (2010) Inconsistency-tolerant semantics for description logics. In: Hitzler P, Lukasiewicz T (eds) RR, volume 6333 of LNCS, pp 103–117. Springer, 2010
25.
Lembo D, Lenzerini M, Rosati R, Ruzzi M, Fabio Savo D (2015) Inconsistency-tolerant query answering in ontology-based data access. J Web Semant 33:3–29CrossRef
26.
Lenzerini M (2012) Ontology-based data management. In: Proceedings of the 6th Alberto Mendelzon international workshop on foundations of data management 2012, pp 12–15, 2012
27.
Lukasiewicz T, Vanina Martinez M, Pieris A, Simari GI (2015) From classical to consistent query answering under existential rules. In: Proceedings of the twenty-ninth AAAI conference on artificial intelligence 2015, pp 1546–1552, 2015
28.
Lukasiewicz T, Vanina Martinez M, Simari GI (2012) Inconsistency handling in datalog+/\(-\) ontologies. In: 20th European conference on artificial intelligence ECAI, 2012, pp 558–563, 2012
29.
Lutz C, Seylan I, Toman D, Wolter F (2013) The combined approach to OBDA: taming role hierarchies using filters. In: The semantic web—ISWC, volume 8218 of lecture notes in computer science, pp 314–330. Springer, 2013
30.
Martinez MV, Parisi F, Pugliese A, Simari GI, Subrahmanian VS (2008)Inconsistency management policies. In: Knowledge representation and reasoning, pp 367–377. AAAI Press, 2008
31.
Nebel B (1994) Base revision operations and schemes: semantics, representation and complexity. In: European conference on artificial intelligence, pp 341–345, 1994
32.
Nicholas R, Ruth M (1970) On inference from inconsistent premisses. Theory Decis 1(2):179–217CrossRef
33.
Poggi A, Lembo D, Calvanese D, De Giacomo G, Lenzerini M, Rosati R (2008) Linking data to ontologies. J Data Semant 10:133–173MATH
34.
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–381CrossRefMATH
35.
Staworko S, Chomicki J, Marcinkowski J (2012) Prioritized repairing and consistent query answering in relational databases. Ann Math Artif Intell 64(2–3):209–246MathSciNetCrossRefMATH
Metadata
Title
Polynomial Algorithms for Computing a Single Preferred Assertional-Based Repair
Authors
Abdelmoutia Telli
Salem Benferhat
Mustapha Bourahla
Zied Bouraoui
Karim Tabia
Publication date
23-01-2017
Publisher
Springer Berlin Heidelberg
Published in
KI - Künstliche Intelligenz / Issue 1/2017
Print ISSN: 0933-1875
Electronic ISSN: 1610-1987
DOI
https://doi.org/10.1007/s13218-016-0466-4

Other articles of this Issue 1/2017

KI - Künstliche Intelligenz 1/2017 Go to the issue

Technical Contribution

Reasoning about Imprecise Beliefs in Multi-Agent Systems with PDT Logic

Technical Contribution

BDI Logics for BDI Architectures: Old Problems, New Perspectives

Technical Contribution

Analyzing a Bipolar Decision Structure Through Qualitative Decision Theory

Research Project

The Tweety Library Collection for Logical Aspects of Artificial Intelligence and Knowledge Representation

Survey

Many Facets of Reasoning Under Uncertainty, Inconsistency, Vagueness, and Preferences: A Brief Survey

Interview

Quo vadis, AI?

Premium Partner

    Image Credits