Consistent query answering in databases

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.

REFERENCES

• 1: Marcelo Arenas , Leopoldo Bertossi , Jan Chomicki, Consistent query answers in inconsistent databases, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.68-79, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303983]
• 2: Marcelo Arenas , Leopoldo E. Bertossi , Jan Chomicki, Scalar Aggregation in FD-Inconsistent Databases, Proceedings of the 8th International Conference on Database Theory, p.39-53, January 04-06, 2001
• 3: Marcelo Arenas , Leopoldo Bertossi , Jan Chomicki , Xin He , Vijay Raghavan , Jeremy Spinrad, Scalar aggregation in inconsistent databases, Theoretical Computer Science, v.296 n.3, p.405-434, 14 March 2003 [doi>10.1016/S0304-3975(02)00737-5]
• 4: Marcelo Arenas , Leopoldo Bertossi , Jan Chomicki, Answer sets for consistent query answering in inconsistent databases, Theory and Practice of Logic Programming, v.3 n.4, p.393-424, July 2003 [doi>10.1017/S1471068403001832]
• 5: Pablo Barceló , Leopoldo E. Bertossi, Logic Programs for Querying Inconsistent Databases, Proceedings of the 5th International Symposium on Practical Aspects of Declarative Languages, p.208-222, January 13-14, 2003
• 6: Barcelo, P., Bertossi, L. and Bravo, L. Characterizing and Computing Semantically Correct Answers from Databases with Annotated Logic and Answer Sets. In Semantics of Databases, Springer LNCS 2582, 2003, pp. 1--27.
• 7: Leopoldo E. Bertossi , Jan Chomicki , Alvaro Cortés , Claudio Gutiérrez, Consistent Answers from Integrated Data Sources, Proceedings of the 5th International Conference on Flexible Query Answering Systems, p.71-85, October 27-29, 2002
• 8: Bertossi, L. and Bravo, L. Consistent Query Answers in Virtual Data Integration Systems. In Inconsistency Tolerance, Springer LNCS 3300, 2004, pp. 42--83.
• 9: Bertossi, L. and Bravo, L. Query Answering in Peer-to-Peer Data Exchange Systems. Proc. EDBT International Workshop on Peer-to-Peer Computing & DataBases (P2P&DB 04), Springer LNCS 3268, 2004, pp. 478--485.
• 10: Bertossi, L., Bravo, L., Franconi, E. and Lopatenko, A. Fixing Numerical Attributes under Integrity Constraints. Proc. International Symposium on Database Programming Languages (DBPL 05), Springer LNCS 3774, 2005, pp. 262--278.
• 11: Leopoldo Bertossi , Jan Chomicki , Parke Godfrey , Phokion G. Kolaitis , Alex Thomo , Calisto Zuzarte, Exchange, integration, and consistency of data: report on the ARISE/NISR workshop, ACM SIGMOD Record, v.34 n.3, September 2005 [doi>10.1145/1084805.1084825]
• 12: Bertossi, L. and Chomicki, J. Query Answering in Inconsistent Databases. In Logics for Emerging Applications of Databases. Springer, 2003, pp. 43--83.
• 13: Bravo, L. and Bertossi, L. Logic Programs for Consistently Querying Data Integration Systems. Proc. International Joint Conference in Artificial Intelligence (IJ-CAI 03), Morgan Kauffmann Publishers, 2003, pp. 10--15.
• 14: Bravo, L. and Bertossi, L. Disjunctive Deductive Databases for Computing Certain and Consistent Answers to Queries from Mediated Data Integration Systems. Journal of Applied Logic, 2005, 3(2):329--367.
• 15: Bravo, L. and Bertossi, L. Semantically Correct Query Answers in the Presence of Null Values. Proc. EDBT International Workshop on Inconsistency and Incompleteness in Databases (IIDB 06). To appear in Springer LNCS. Technical Report arXiv:cs.DB/0604076 v1. Posted April 19, 2006.
• 16: Andrea Calì , Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, Data Integration under Integrity Constraints, Proceedings of the 14th International Conference on Advanced Information Systems Engineering, p.262-279, May 27-31, 2002
• 17: Cali, A., Calvanese, D., De Giacomo, G. and Lenzerini, M. On the Role of Integrity Constraints in Data Integration. IEEE Data Engineering Bulletin, 2002, 25(3): 39--45.
• 18: Andrea Calì , Domenico Lembo , Riccardo Rosati, On the decidability and complexity of query answering over inconsistent and incomplete databases, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.260-271, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773179]
• 19: Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M. and Rosati, R. Inconsistency Tolerance in P2P Data Integration: An Epistemic Logic Approach. Proc. International Symposium on Database Programming Languages (DBPL 05), Springer LNCS 3774, 2005, pp. 90--105.
• 20: Monica Caniupan , Leopoldo Bertossi, Optimizing Repair Programs for Consistent Query Answering, Proceedings of the XXV International Conference on The Chilean Computer Science Society, p.3, November 07-11, 2005
• 21: Alexander Celle , Leopoldo E. Bertossi, Querying Inconsistent Databases: Algorithms and Implementation, Proceedings of the First International Conference on Computational Logic, p.942-956, July 01, 2000
• 22: Jan Chomicki , Jerzy Marcinkowski , Slawomir Staworko, Computing consistent query answers using conflict hypergraphs, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031254]
• 23: Jan Chomicki , Jerzy Marcinkowski, Minimal-change integrity maintenance using tuple deletions, Information and Computation, v.197 n.1/2, p.90-121, February 25, 2005/March 15, 2005 [doi>10.1016/j.ic.2004.04.007]
• 24: Evgeny Dantsin , Thomas Eiter , Georg Gottlob , Andrei Voronkov, Complexity and expressive power of logic programming, ACM Computing Surveys (CSUR), v.33 n.3, p.374-425, September 2001 [doi>10.1145/502807.502810]
• 25: Downey, R. G. and Fellows, M. R. Parameterized Complexity. Springer, Monographs in Computer Science, 1999.
• 26: Duschka, O., Genesereth, M. and Levy, A. Recursive Query Plans for Data Integration. Journal of Logic Programming, 2000, 43(1):49--73.
• 27: Eiter, T., Fink, M., Greco, G. and Lembo, D. Efficient Evaluation of Logic Programs for Querying Data Integration Systems. Proc. International Conference on Logic Programming (ICLP 03), Springer LNCS 2916, 2003, pp. 163--177. 2916, 2003.
• 28: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data Exchange: Semantics and Query Answering, Proceedings of the 9th International Conference on Database Theory, p.207-224, January 08-10, 2003
• 29: Flesca, S., Furfaro, F. Parisi, F. Consistent Query Answers on Numerical Databases under Aggregate Constraints. Proc. International Symposium on Database Programming Languages (DBPL 05), Springer LNCS 3774, 2005, pp. 279--294.
• 30: J. Flum , M. Grohe, Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 31: Enrico Franconi , Antonio Laureti Palma , Nicola Leone , Simona Perri , Francesco Scarcello, Census Data Repair: a Challenging Application of Disjunctive Logic Programming, Proceedings of the Artificial Intelligence on Logic for Programming, p.561-578, December 03-07, 2001
• 32: Fuxman, A. and Miller, R. First-Order Query Rewriting for Inconsistent Databases. Proc. International Conference on Database Theory (ICDT 05), Springer LNCS 3363, 2004, pp. 337--351.
• 33: Ariel Fuxman , Elham Fazli , Renée J. Miller, ConQuer: efficient management of inconsistent databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066176]
• 34: Gelfond, M. and Lifschitz, V. Classical Negation in Logic Programs and Disjunctive Databases. New Generation Computing, 1991, 9:365--385.
• 35: Gianluigi Greco , Sergio Greco , Ester Zumpano, A Logical Framework for Querying and Repairing Inconsistent Databases, IEEE Transactions on Knowledge and Data Engineering, v.15 n.6, p.1389-1408, November 2003 [doi>10.1109/TKDE.2003.1245280]
• 36: Fosca Giannotti , Sergio Greco , Domenico Saccà , Carlo Zaniolo, Programming with non-determinism in deductive databases, Annals of Mathematics and Artificial Intelligence, v.19 n.1-2, p.97-125, 1997 [doi>10.1023/A:1018999404360]
• 37: Luca Grieco , Domenico Lembo , Riccardo Rosati , Marco Ruzzi, Consistent query answering under key and exclusion dependencies: algorithms and experiments, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099742]
• 38: Martin Grohe, Parameterized complexity for the database theorist, ACM SIGMOD Record, v.31 n.4, December 2002 [doi>10.1145/637411.637428]
• 39: Halevy, A., Ives, Z., Suciu, D. and Tatarinov, I. Schema Mediation in Peer Data Management Systems. Proc. Intenational Conference on Data Engineering (ICDE 03), IEEE Computer Society Press, 2003, pp. 505--518.
• 40: Immerman, N. Descriptive Complexity. Graduate Texts in Computer Science. Springer, 1999.
• 41: Phokion G. Kolaitis, Schema mappings, data exchange, and metadata management, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065176]
• 42: Lembo, D., Lenzerini, M. and Rosati, R. Source Inconsistency and Incompleteness in Data Integration. In Proc. International Workshop Knowledge Representation meets Databases (KRDB 02), CEUR Electronic Workshop Proceedings, 2002.
• 43: Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543644]
• 44: Lopatenko, A. and Bertossi, L. Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Semantics. Technical Report arXiv:cs.DB/0604002 v1. Posted April 2, 2006.
• 45: Peter Bro Miltersen , Sairam Subramanian , Jeffrey Scott Vitter , Roberto Tamassia, Complexity models for incremental computation, Theoretical Computer Science, v.130 n.1, p.203-236, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90159-7]
• 46: Rolf Niedermeier , Peter Rossmanith, An efficient fixed-parameter algorithm for 3-hitting set, Journal of Discrete Algorithms, v.1 n.1, p.89-102, February 2003 [doi>10.1016/S1570-8667(03)00009-1]
• 47: Weber, V. and Schwentick, T. Dynamic Complexity Theory Revisited. Proc. Annual Symposium on Theoretical Aspects of Computer Science (STACS 05), Springer LNCS 3404, 2005, pp. 256--268.
• 48: Jef Wijsen, Condensed Representation of Database Repairs for Consistent Query Answering, Proceedings of the 9th International Conference on Database Theory, p.378-393, January 08-10, 2003

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Answer/reason extraction

General Terms:
Algorithms, Design, Performance