An Operational Approach to Consistent Query Answering

ABSTRACT

Consistent query answering (CQA) aims to find meaningful answers to queries when databases are inconsistent, i.e., do not conform to their specifications. Such answers must be certainly true in all repairs, which are consistent databases whose difference from the inconsistent one is minimal, according to some measure. This task is often computationally intractable, and much of CQA research concentrated on finding islands of tractability. Nevertheless, there are many relevant queries for which no efficient solutions exist, which is reflected by the limited practical applicability of the CQA approach. To remedy this, one needs to devise a new CQA framework that provides explicit guarantees on the quality of query answers. However, the standard notions of repair and certain answers are too coarse to permit more elaborate schemes of query answering. Our goal is to provide a new framework for CQA based on revised definitions of repairs and query answering that opens up the possibility of efficient approximate query answering with explicit guarantees. The key idea is to replace the current declarative definition of a repair with an operational one, which explains how a repair is constructed, and how likely it is that a consistent instance is a repair. This allows us to define how certain we are that a tuple should be in the answer. Using this approach, we study the complexity of both exact and approximate CQA. Even though some of the problems remain hard, for many common classes of constraints we can provide meaningful answers in reasonable time, for queries going far beyond the standard CQA approach.

References

1. Serge Abiteboul, T.-H. Hubert Chan, Evgeny Kharlamov, Werner Nutt, and Pierre Senellart. 2011. Capturing continuous data and answering aggregate queries in probabilistic XML. ACM Trans. Database Syst. Vol. 36, 4 (2011), 25:1--25:45.
2. Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. 1999. Consistent Query Answers in Inconsistent Databases PODS. 68--79.
3. Marcelo Arenas, Leopoldo E. Bertossi, Jan Chomicki, Xin He, Vijay Raghavan, and Jeremy P. Spinrad. 2003. Scalar aggregation in inconsistent databases. Theor. Comput. Sci. Vol. 296, 3 (2003), 405--434.
4. Sanjeev Aror and Boaz Barak. 2009. Computational Complexity: A Modern Approach. Cambridge University Press.
5. Leopoldo E. Bertossi. 2011. Database Repairing and Consistent Query Answering. Morgan & Claypool Publishers.
6. Leopoldo E. Bertossi and Loreto Bravo. 2017. Consistency and trust in peer data exchange systems. TPLP Vol. 17, 2 (2017), 148--204.
7. Leopoldo E. Bertossi and Lechen Li. 2013. Achieving Data Privacy through Secrecy Views and Null-Based Virtual Updates. IEEE Trans. Knowl. Data Eng. Vol. 25, 5 (2013), 987--1000.
8. Meghyn Bienvenu. 2012. On the Complexity of Consistent Query Answering in the Presence of Simple Ontologies AAAI.
9. Meghyn Bienvenu and Riccardo Rosati. 2013. Tractable Approximations of Consistent Query Answering for Robust Ontology-based Data Access. In IJCAI. 775--781.
10. Andrea Cal`ı, Domenico Lembo, and Riccardo Rosati. 2003. Query rewriting and answering under constraints in data integration systems IJCAI. 16--21.
11. Luciano Caroprese, Sergio Greco, and Ester Zumpano. 2009. Active Integrity Constraints for Database Consistency Maintenance. IEEE Trans. Knowl. Data Eng. Vol. 21, 7 (2009), 1042--1058.
12. Jan Chomicki and Jerzy Marcinkowski. 2005. Minimal-change integrity maintenance using tuple deletions. Inf. Comput. Vol. 197, 1--2 (2005), 90--121.
13. Jens Claußen, Alfons Kemper, Guido Moerkotte, Klaus Peithner, and Michael Steinbrunn. 2000. Optimization and Evaluation of Disjunctive Queries. IEEE Trans. Knowl. Data Eng. Vol. 12, 2 (2000), 238--260.
14. Nilesh N. Dalvi and Dan Suciu. 2007. Efficient query evaluation on probabilistic databases. VLDB J. Vol. 16, 4 (2007), 523--544.
15. Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. 2004. Tackling Inconsistencies in Data Integration through Source Preferences IQIS. 27--34.
16. Xin Luna Dong, Laure Berti-Équille, and Divesh Srivastava. 2013. Data Fusion: Resolving Conflicts from Multiple Sources WAIM. 64--76.
17. Thomas Eiter, Michael Fink, Gianluigi Greco, and Domenico Lembo. 2008. Repair localization for query answering from inconsistent databases. ACM Trans. Database Syst. Vol. 33, 2 (2008), 10:1--10:51.
18. Ronald Fagin, Benny Kimelfeld, and Phokion G. Kolaitis. 2015. Dichotomies in the Complexity of Preferred Repairs PODS. 3--15.
19. Gaëlle Fontaine. 2015. Why Is It Hard to Obtain a Dichotomy for Consistent Query Answering? ACM Trans. Comput. Log. Vol. 16, 1 (2015), 7:1--7:24.
20. Ariel Fuxman, Elham Fazli, and Renée J. Miller. 2005. ConQuer: Efficient Management of Inconsistent Databases SIGMOD. 155--166.
21. Ariel Fuxman and Renée J. Miller. 2007. First-order query rewriting for inconsistent databases. J. Comput. Syst. Sci. Vol. 73, 4 (2007), 610--635.
22. Floris Geerts, Fabian Pijcke, and Jef Wijsen. 2015. First-Order Under-Approximations of Consistent Query Answers SUM. 354--367.
23. Sergio Greco and Cristian Molinaro. 2012. Probabilistic query answering over inconsistent databases. Ann. Math. Artif. Intell. Vol. 64, 2--3 (2012), 185--207.
24. Wassily Hoeffding. 1963. Probability Inequalities for Sums of Bounded Random Variables. J. Amer. Statist. Assoc. Vol. 58, 301 (1963), 13--30.
25. Mark Jerrum. 2003. Counting, Sampling and Integrating: Algorithms and Complexity. Birkhauser Basel.
26. Richard M. Karp and Richard J. Lipton. 1980. Some Connections between Nonuniform and Uniform Complexity Classes STOC. 302--309.
27. John Kemeny and J. Laurie Snell. 1983. Finite Markov Chains. Springer.
28. Paraschos Koutris and Dan Suciu. 2014. A Dichotomy on the Complexity of Consistent Query Answering for Atoms with Simple Keys ICDT. 165--176.
29. Paraschos Koutris and Jef Wijsen. 2015. The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints. In PODS. 17--29.
30. Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio Savo. 2015. Inconsistency-tolerant query answering in ontology-based data access. J. Web Sem. Vol. 33 (2015), 3--29.
31. Nicola Leone et al.. 2005. The INFOMIX system for advanced integration of incomplete and inconsistent data SIGMOD. 915--917.
32. Xiang Lian, Lei Chen, and Shaoxu Song. 2010. Consistent Query Answers in Inconsistent Probabilistic Databases SIGMOD. 303--314.
33. Leonid Libkin. 2014. Incomplete data: what went wrong, and how to fix it PODS. 1--13.
34. Thomas Lukasiewicz, Maria Vanina Martinez, Andreas Pieris, and Gerardo I. Simari. 2015. From Classical to Consistent Query Answering under Existential Rules AAAI. 1546--1552.
35. Carsten Lutz and Frank Wolter. 2015. On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems. In ICDT. 363--379.
36. Slawek Staworko, Jan Chomicki, and Jerzy Marcinkowski. 2012. Prioritized repairing and consistent query answering in relational databases. Ann. Math. Artif. Intell. Vol. 64, 2--3 (2012), 209--246.
37. Seinosuke Toda and Osamu Watanabe. 1992. Polynomial Time 1-Turing Reductions from #PH to #P. Theor. Comput. Sci. Vol. 100, 1 (1992), 205--221.
38. Vijai Vazirani. 2001. Approximation Algorithms. Springer.
39. Jef Wijsen. 2005. Database Repairing Using Updates. ACM Trans. Database Syst. Vol. 30, 3 (Sept.. 2005), 722--768.
40. Jef Wijsen. 2014. A Survey of the Data Complexity of Consistent Query Answering under Key Constraints FoIKS. 62--78.
41. Xiaoxin Yin, Jiawei Han, and Philip S. Yu. 2008. Truth Discovery with Multiple Conflicting Information Providers on the Web. IEEE Trans. on Knowl. and Data Eng. Vol. 20, 6 (2008), 796--808.

Index Terms

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Incomplete, inconsistent, and uncertain databases