Consistent query answering in databases
ACM SIGMOD RecordPublished 1 June 2006
Leopoldo Bertossi
Citations201
SJR quartileQ2
SJR score0.69
SNIP0.92
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
For several reasons databases may become inconsistent with respect to a given set of integrity constraints (ICs): (a) The DBMS have no mechanism to maintain certain classes of ICs. (b) New constraints are imposed on preexisting, legacy data. (c) The ICs are soft, user, or informational constraints that are considered at query time, but without being necessarily enforced. (d) Data from different and autonomous sources are being integrated, in particular in mediator-based approaches.
Keywords
Computer Science
Electronic Notes in Theoretical Computer ScienceParameterized Complexity
2,884 Citations2002Michael R. Fellows
Texts and monographs in computer scienceParameterized Complexity
2,505 Citations1999Rodney G. Downey, Michael R. Fellows
An approach to complexity theory which offers a means of analysing algorithms in terms of their tractability, and introduces readers to new classes of algorithms which may be analysed more precisely than was the case until now.
Data integration
2,463 Citations2002Maurizio Lenzerini
The tutorial is focused on some of the theoretical issues that are relevant for data integration: modeling a data integration application, processing queries in data integration, dealing with inconsistent data sources, and reasoning on queries.
New Generation ComputingClassical negation in logic programs and disjunctive databases
2,313 Citations1991Michael Gelfond, Vladimir Lifschitz
It is shown that some facts of commonsense knowledge can be represented by logic programs and disjunctive databases more easily when classical negation is available.
Parameterized Complexity Theory
1,897 Citations2006Jörg Flum, Martin Grohe
Theoretical Computer ScienceData exchange: semantics and query answering
1,203 Citations2004Ronald Fagin, Phokion G. Kolaitis +2 more
BMC Pregnancy and ChildbirthParameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)
1,111 Citations2006J. Flum, Martin Grohe
Consistent query answers in inconsistent databases
883 Citations1999Marcelo Arenas, Leopoldo Bertossi +1 more
The problem of the logical characterization of the notion of consistent answer in a relational database that may violate given integrity constraints is considered and its soundness and completeness are proved.
ACM Computing SurveysComplexity and expressive power of logic programming
753 Citations2001Evgeny Dantsin, Thomas Eiter +2 more
Schema mediation in peer data management systems
438 Citations2004Alon Halevy, Zachary G. Ives +2 more
This work proposes the use of a decentralized, easily extensible data management architecture in which any user can contribute new data, schema information, or even mappings between other peer's schemas, and describes a flexible language for mediating between peer schemas.
Information and ComputationMinimal-change integrity maintenance using tuple deletions
343 Citations2005Jan Chomicki, Jerzy Marcinkowski
This work addresses the problem of minimal-change integrity maintenance in the context of integrity constraints in relational databases, and considers denial constraints, general functional and inclusion dependencies, as well as key and foreign key constraints.
On the decidability and complexity of query answering over inconsistent and incomplete databases
295 Citations2003Andrea Calı̀, Domenico Lembo +1 more
This paper identifies the maximal class of inclusion dependencies under which query answering is decidable in the presence of key dependencies and establishes decidability and complexity results for query answering under different assumptions on data.
Schema mappings, data exchange, and metadata management
282 Citations2005Phokion G. Kolaitis
The main aim in this paper is to present an overview of recent advances in data exchange and metadata management, where the schema mappings are between relational schemas.
Information SystemsData integration under integrity constraints
247 Citations2003Andrea Calı̀, Diego Calvanese +2 more
ConQuer
204 Citations2005Ariel Fuxman, Elham Fazli +1 more
It is shown that the overhead is not onerous, and the consistent query answers can often be computed within twice the time required to obtain the answers to the original (non-rewritten) query.
Theory and Practice of Logic ProgrammingAnswer sets for consistent query answering in inconsistent databases
199 Citations2003Marcelo Arenas, Leopoldo Bertossi +1 more
The Journal of Logic ProgrammingRecursive query plans for data integration
197 Citations2000Oliver M. Duschka, Michael Genesereth +1 more
The novel class of recursive query answering plans is described, which enables us to settle three open problems and describes an algorithm for finding a query plan that produces the maximal set of answers from the sources for arbitrary recursive queries.
IEEE Transactions on Knowledge and Data EngineeringA logical framework for querying and repairing inconsistent databases
191 Citations2003Gianluigi Greco, Sergio Greco +1 more
This paper proposes a general logic framework for computing repairs and consistent answers over inconsistent databases and proposes a technique based on the rewriting of constraints into (prioritized) extended disjunctive rules with two different forms of negation (negation as failure and classical negation).
Journal of Discrete AlgorithmsAn efficient fixed-parameter algorithm for 3-Hitting Set
157 Citations2003Rolf Niedermeier, Peter Rossmanith
An O(2.270k + n) time algorithm is given for 3-Hitting Set, which is efficient for small values of k, a typical occurrence in some applications.
Theoretical Computer ScienceScalar aggregation in inconsistent databases
144 Citations2003Marcelo Arenas, Leopoldo Bertossi +4 more
This work provides a complete characterization of the computational complexity of scalar aggregation queries in databases that may violate a given set of functional dependencies and shows how tractability can be improved in several special cases.
Query Answering in Inconsistent Databases
130 Citations2004Leopoldo Bertossi, Jan Chomicki
This chapter summarizes the research on querying inconsistent databases and describes different approaches to the issue of computing consistent query answers: query transformation, logic programming, inference in annotated logics, and specialized algorithms.
Logics for Emerging Applications of Databases
127 Citations2004Jan Chomicki, Ron van der Meyden +1 more
This book provides a state-of-the-art overview of research on the application of logic-based methods to information systems, covering highly topical and emerging fields: XML programming and querying, intelligent agents, workflow modeling and verification, data integration, temporal and dynamic information, data mining, authorization, and security.
Lecture notes in computer scienceComplexity of Consistent Query Answering in Databases Under Cardinality-Based and Incremental Repair Semantics
114 Citations2006Andrei Lopatenko, Leopoldo Bertossi
Algorithmic and complexity theoretic results for CQA under this cardinality-based repair semantics are obtained in the usual, static setting, but also in a dynamic framework where a consistent database is affected by a sequence of updates, which may make it inconsistent.
Logic programs for consistently querying data integration systems
107 Citations2003Loreto Bravo, Leopoldo Bertossi
This work solves the problem of obtaining answers to queries posed to a mediated integration system under the local-as-view paradigm that are consistent wrt to certain global integrity constraints.
Theoretical Computer ScienceComplexity models for incremental computation
105 Citations1994Peter Bro Miltersen, Sairam Subramanian +2 more
This work defines complexity classes that capture the intuitive notion of incremental efficiency and study their relation to existing complexity classes and shows that problems that have small sequential space complexity also have small incremental time complexity.
Information SystemsThe complexity and approximation of fixing numerical attributes in databases under integrity constraints
101 Citations2008Leopoldo Bertossi, Loreto Bravo +2 more
A quantitative definition of database repair is introduced, and the complexity of several decision and optimization problems are investigated, including deciding the existence of repairs within a given distance to the original instance and CQA: deciding consistency of answers to simple and aggregate conjunctive queries under different semantics.
Lecture notes in computer scienceCensus Data Repair: A Challenging Application of Disjunctive Logic Programming
100 Citations2001Enrico Franconi, Antonio Laureti Palma +3 more
A correct modular encoding of the problem in the disjunctive logic programming language D LPw, supported by the DLV system, is shown and it turns out that DLPw is very well-suited for this goal.
Computing consistent query answers using conflict hypergraphs
94 Citations2004Jan Chomicki, Jerzy Marcinkowski +1 more
A practical framework for computing consistent query answers for large, possibly inconsistent relational databases is presented and it can effectively (and efficiently) extract indefinite disjunctive information from an inconsistent database.
Lecture notes in computer scienceCondensed Representation of Database Repairs for Consistent Query Answering
91 Citations2002Jef Wijsen
The problem of query answering in the presence of inconsistency relative to this refined repair notion is solved and there exists a condensed representation of all repairs that permits computing trustable query answers.
Lecture notes in computer scienceFirst-Order Query Rewriting for Inconsistent Databases
88 Citations2004Ariel Fuxman, Renée J. Miller
Lecture notes in computer scienceLogic Programs for Querying Inconsistent Databases
67 Citations2002Pablo Barceló, Leopoldo Bertossi
This paper shows how to write repair programs for universal and referential ICs; their correctness is established and how to run them on top of the DLV system is established.
Lecture notes in computer scienceEfficient Evaluation of Logic Programs for Querying Data Integration Systems
61 Citations2003Thomas Eiter, Michael Fink +2 more
Techniques which make user query answering by logic programs effective are investigated, including pruning and localization methods for the data which need to be processed in a deductive system, and a technique for the recombination of the results on a relational database engine.
Information SystemsInconsistency tolerance in P2P data integration: An epistemic logic approach
61 Citations2008Diego Calvanese, Giuseppe De Giacomo +3 more
ACM SIGMOD RecordParameterized complexity for the database theorist
58 Citations2002Martin Grohe
This short paper is a gentle introduction to the theory of parameterized complexity theory, focusing on the results most relevant for database theory.
Lecture notes in computer scienceConsistent Answers from Integrated Data Sources
54 Citations2002Leopoldo Bertossi, Jan Chomicki +2 more
In this paper, the notion of consistent answer to a global query in the context of the local-as-view approach to data integration is characterized and a methodology for generating query plans for retrieving consistent answers to global queries is introduced.
Lecture notes in computer scienceConsistent Query Answers in Virtual Data Integration Systems
50 Citations2005Leopoldo Bertossi, Loreto Bravo
This chapter considers the problem of defining and computing those answers that are consistent wrt the global ICs when global queries are posed to virtual data integration systems whose sources are specified following the local-as-view approach.
Lecture notes in computer scienceSemantically Correct Query Answers in the Presence of Null Values
48 Citations2006Loreto Bravo, Leopoldo Bertossi
A precise semantics for IC satisfaction in a database with null values is proposed that is compatible with the way null values are treated in commercial database management systems and a precise notion of repair is introduced that privileges the introduction of null values when repairing foreign key constraints.
Lecture notes in computer scienceQuery Answering in Peer-to-Peer Data Exchange Systems
48 Citations2004Leopoldo Bertossi, Loreto Bravo
A semantics for peer consistent answers under exchange constraints and trust relationships is introduced and some techniques for obtaining those answers are presented.
Lecture notes in computer scienceScalar Aggregation in FD-Inconsistent Databases
47 Citations2001Marcelo Arenas, Leopoldo Bertossi +1 more
This work shows how to compute consistent answers to scalar aggregation queries in databases that may violate a given set of functional dependencies and provides a complete characterization of the computational complexity of this problem.
Lecture notes in computer scienceInconsistency Tolerance in P2P Data Integration: An Epistemic Logic Approach
44 Citations2005Diego Calvanese, Giuseppe De Giacomo +3 more
A nonmonotonic extension of logic is defined that is able to reason on the beliefs of peers under both local and P2P inconsistency tolerance, and it is shown that, under reasonable assumptions on peer schemas, query answering is decidable, and is coNP-complete with respect to data complexity.
Consistent query answering under key and exclusion dependencies
42 Citations2005Luca Grieco, Domenico Lembo +2 more
It is proved that even in the presence of only exclusion dependencies the problem is coNP-hard in data complexity, and a general method for consistent answering of conjunctive queries under key and exclusion dependencies is defined, based on the rewriting of the query in Datalog with negation.
Lecture notes in computer scienceComplexity and Approximation of Fixing Numerical Attributes in Databases Under Integrity Constraints
41 Citations2005Leopoldo Bertossi, Loreto Bravo +2 more
A quantitative definition of database fix is introduced, and the complexity of several decision and optimization problems, including DFP, DFP-hardness, but a good approximation algorithm for a relevant special case; and intractability but good approximation for CQA for aggregate queries for one database atom denials (plus built-ins).
Annals of Mathematics and Artificial IntelligenceProgramming with non-determinism in deductive databases
41 Citations1997Fosca Giannotti, Sergio Greco +2 more
This paper provides a reasoned introduction to effective programming with non-deterministic constructs in database languages to the theory of data complexity and the expressibility hierarchy of query languages.
Lecture notes in computer scienceConsistent Query Answers on Numerical Databases Under Aggregate Constraints
40 Citations2005Sergio Flesca, Filippo Furfaro +1 more
The problem of extracting consistent information from relational databases violating integrity constraints on numerical data is addressed and the characterization of several data-complexity issues related to repairing data and computing consistent query answers is provided.
Lecture notes in computer scienceQuerying Inconsistent Databases: Algorithms and Implementation
40 Citations2000Alexander Celle, Leopoldo Bertossi
The implementation of the algorithm in XSB presented here takes advantage of the functionalities of XSB, as a logic programming language with tabling facilities, and the possibility of coupling it to relational database systems.
Journal of Applied LogicDeductive databases for computing certain and consistent answers from mediated data integration systems
25 Citations2004Loreto Bravo, Leopoldo Bertossi
This paper addresses the problem of retrieving certain and consistent answers to queries posed to a mediated data integration system under the local-as-view paradigm with open sources and conjunctive and disjunctive view definitions by implementing a cautious stable model semantics on top of a normal deductive database.
BIROn (Birkbeck, University of London)On the Role of Integrity Constraints in Data Integration.
16 Citations2002Andrea Calı̀, Diego Calvanese +2 more
This work discusses the issue of dealing with integrity constraints over the global schema in data integration and presents a data integration system developed by taking into account such issues.
Optimizing Repair Programs for Consistent Query Answering
12 Citations2006Mónica Caniupán, Leopoldo Bertossi
This paper makes repair programs more compact by eliminating redundant rules and unnecessary programs denial constraints, and analyzes the implementation in DLV of queries with aggregate functions.
Lecture notes in computer scienceDynamic Complexity Theory Revisited
10 Citations2005Volker Weber, Thomas Schwentick
Fixing Numerical Attributes Under Integrity Constraints
9 Citations2005Leopoldo Bertossi, Loreto Bravo +2 more
This work studies the problem of repairing databases by fixing numerical data at the attribute level, and investigates the computational complexity of different problems, such as the existence and verification of fixes, and deciding consistency of answers to conjunctive aggregate queries.
ACM SIGMOD RecordExchange, integration, and consistency of data
6 Citations2005Leopoldo Bertossi, Jan Chomicki +4 more
The "ARISE/NISR Workshop on Exchange and Integration of Data" was held at the IBM Center for Advanced Studies, Toronto Lab.
Lecture notes in computer scienceHandling Inconsistencies in Data Warehouses
6 Citations2004Mónica Caniupán
Preliminary results about the effects of the violation of partitioning constraints in homogeneous dimension instances over aggregation queries, and in particular over the summarizability property (SUMM) of the DWs are presented.