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
Published in:
A Crash Course on Generalized Possibilistic Logic Read chapter Read first chapter

2018 | OriginalPaper | Chapter

Measuring and Computing Database Inconsistency via Repairs

Author : Leopoldo Bertossi

Published in: Scalable Uncertainty Management

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

We propose a generic numerical measure of inconsistency of a database with respect to a set of integrity constraints. It is based on an abstract repair semantics. A particular inconsistency measure associated to cardinality-repairs is investigated; and we show that it can be computed via answer-set programs.

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

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

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
previous chapter Representation of Multiple Agent Preferences
next chapter Scalable Bounding of Predictive Uncertainty in Regression Problems with SLAC
Footnotes
1
Abstract distances between two point-sets are investigated in [8], with their computational properties. Our setting is a particular case.
 
2
For INDs repairs based only on tuple deletions can be considered [6].
 
3
Other possible measures for single FDs and relationships between them can be found in [11].
 
4
For certain forms of prioritized repairs, such as endogenous repairs, the normalization coefficient |D| might be unnecessarily large. In this particular case, it might be better to use \(|D^n|\).
 
5
This approach was followed in [1] to compute maximum responsibility degrees of database tuples as causes for violations of DCs, appealing to a causality-repair connection [3].
 
6
Certain (or skeptical) reasoning with repair programs for DCs with weak constraints is \(\varDelta ^P_2({ log}(n))\)-complete in data complexity, i.e. in the size of the database [7, 12].
 
Literature
1.
Bertossi, L.: Characterizing and computing causes for query answers in databases from database repairs and repair programs. Corr Arxiv cs.DB/1712.01001 (2018). Proc. FoIKs. LNCS, vol. 10833, pp. 55–76. Springer (2018)
2.
Bertossi, L.: Database Repairing and Consistent Query Answering. Synthesis Lectures on Data Management. Morgan & Claypool, San Rafael (2011)
3.
Bertossi, L., Salimi, B.: From causes for database queries to repairs and model-based diagnosis and back. Theory Comput. Syst. 61(1), 191–232 (2017)MathSciNetCrossRef
4.
5.
Brewka, G., Eiter, T., Truszczynski, M.: Answer set programming at a glance. Commun. ACM 54(12), 93–103 (2011)CrossRef
6.
Chomicki, J., Marcinkowski, J.: Minimal-change integrity maintenance using tuple deletions. Inf. Comput. 197(1–2), 90–121 (2005)MathSciNetCrossRef
7.
Caniupan-Marileo, M., Bertossi, L.: The consistency extractor system: answer set programs for consistent query answering in databases. Data Knowl. Eng. 69(6), 545–572 (2010)CrossRef
8.
9.
Grant, J., Martinez, M.V. (eds.): Measuring Inconsistency in Information. College Publications, Los Angeles (2018)MATH
10.
Grant, J., Hunter, A.: Analysing inconsistent information using distance-based measures. Int. J. Approx. Reason. 89, 3–26 (2017)MathSciNetCrossRef
11.
Kivinen, J., Mannila, H.: Approximate inference of functional dependencies from relations. Theor. Comput. Sci. 149, 129–l49 (1995)MathSciNetCrossRef
12.
Leone, N., et al.: The DLV system for knowledge representation and reasoning. ACM Trans. Comput. Logic. 7(3), 499–562 (2006)MathSciNetCrossRef
13.
Meliou, A., Gatterbauer, W., Moore, K.F., Suciu, D.: The complexity of causality and responsibility for query answers and non-answers. Proc. VLDB 4, 34–41 (2010)CrossRef
14.
Rajamaran, A., Ullman, J.: Mining of Masssive Datasets. Cambridge University Press, Cambridge (2012)
15.
Staworko, S., Chomicki, J., Marcinkowski, J.: Prioritized repairing and consistent query answering in relational databases. Ann. Math. Artif. Intell. 64(2–3), 209–246 (2012)MathSciNetCrossRef
16.
Thimm, M.: On the compliance of rationality postulates for inconsistency measures: a more or less complete picture. Künstliche Intell. 31(1), 31–39 (2017)CrossRef
Metadata
Title
Measuring and Computing Database Inconsistency via Repairs
Author
Leopoldo Bertossi
Copyright Year
2018
Book
Scalable Uncertainty Management

Print ISBN: 978-3-030-00460-6

Electronic ISBN: 978-3-030-00461-3

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-030-00461-3_26

Premium Partner

    Image Credits