Abstract
Consistent Query Answering (CQA) has by now been widely adopted as a principled approach for answering queries on inconsistent databases. The consistent answer to a query q on an inconsistent database \({\mathbf {db}}\) is the intersection of the answers to q on all repairs, where a repair is any consistent database that is maximally close to \({\mathbf {db}}\). Unfortunately, computing consistent answers under primary key constraints has already exponential data complexity for very simple conjunctive queries, which is completely impracticable.
In this paper, we propose a new framework for divulging an inconsistent database to end users, which adopts two postulates. The first postulate complies with CQA and states that inconsistencies should never be divulged to end users. Therefore, end users should only get consistent query answers. The second postulate states that the data complexity of user queries must remain tractable (i.e., in \({\mathbf {P}}\) or even in \({\mathbf {FO}}\)). User queries with exponential data complexity will be rejected. We investigate which consistent query answers can still be obtained under such access postulates.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
According to [6], marital stability is higher when the wife is 5+ years younger than her husband.
- 2.
\({\mathbf {r}}\models q(\mathbf {a})\) is defined in the standard way.
- 3.
Notice that is can be easily verified that \(\lfloor {\{\mathbf {z_{i}}\mid \exists \mathbf {y}_{i}B_{i}\}}\rfloor \equiv \{\mathbf {z_{i}}\mid \lfloor {\exists \mathbf {y}_{i}B_{i}}\rfloor \}\).
References
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Boston (1995)
Arenas, M., Bertossi, L.E., Chomicki, J.: Consistent query answers in inconsistent databases. In: PODS, pp. 68–79. ACM Press (1999)
Bertossi, L.E.: Database Repairing and Consistent Query Answering. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, San Rafael (2011)
Bertossi, L.E., Li, L.: Achieving data privacy through secrecy views and null-based virtual updates. IEEE Trans. Knowl. Data Eng. 25(5), 987–1000 (2013)
Bienvenu, M., Rosati, R.: Tractable approximations of consistent query answering for robust ontology-based data access. In: IJCAI. IJCAI/AAAI (2013)
Cao, N.V., Fragnire, E., Gauthier, J.-A., Sapin, M., Widmer, E.D.: Optimizing the marriage market: an application of the linear assignment model. Eur. J. Oper. Res. 202(2), 547–553 (2010)
Chomicki, J., Marcinkowski, J.: Minimal-change integrity maintenance using tuple deletions. Inf. Comput. 197(1–2), 90–121 (2005)
Dalvi, N.N., Ré, C., Suciu, D.: Probabilistic databases: diamonds in the dirt. Commun. ACM 52(7), 86–94 (2009)
Dalvi, N.N., Re, C., Suciu, D.: Queries and materialized views on probabilistic databases. J. Comput. Syst. Sci. 77(3), 473–490 (2011)
Fan, W., Geerts, F.: Foundations of Data Quality Management. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, San Rafael (2012)
Fuxman, A.D., Miller, R.J.: First-order query rewriting for inconsistent databases. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol. 3363, pp. 337–351. Springer, Heidelberg (2005)
Immerman, N.: Descriptive Complexity. Graduate Texts in Computer Science. Springer, New York (1999)
Koutris, P., Wijsen, J.: The data complexity of consistent query answering for self-join-free conjunctive queries under primary key constraints. In: PODS, pp. 17–29. ACM (2015)
Koutris, P., Wijsen, J.: A trichotomy in the data complexity of certain query answering for conjunctive queries. CoRR, abs/1501.07864 (2015)
Libkin, L.: Elements of Finite Model Theory. Springer, New York (2004)
Libkin, L.: SQL’s three-valued logic and certain answers. In: ICDT. LIPIcs, vol. 31, pp. 94–109. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)
Maslowski, D., Wijsen, J.: A dichotomy in the complexity of counting database repairs. J. Comput. Syst. Sci. 79(6), 958–983 (2013)
Maslowski, D., Wijsen, J.: Counting database repairs that satisfy conjunctive queries with self-joins. In: ICDT, pp. 155–164. OpenProceedings.org (2014)
Wijsen, J.: Making more out of an inconsistent database. In: Benczúr, A.A., Demetrovics, J., Gottlob, G. (eds.) ADBIS 2004. LNCS, vol. 3255, pp. 291–305. Springer, Heidelberg (2004)
Wijsen, J.: Charting the tractability frontier of certain conjunctive query answering. In: PODS, pp. 189–200. ACM (2013)
Wijsen, J.: A survey of the data complexity of consistent query answering under key constraints. In: Beierle, C., Meghini, C. (eds.) FoIKS 2014. LNCS, vol. 8367, pp. 62–78. Springer, Heidelberg (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Geerts, F., Pijcke, F., Wijsen, J. (2015). First-Order Under-Approximations of Consistent Query Answers. In: Beierle, C., Dekhtyar, A. (eds) Scalable Uncertainty Management. SUM 2015. Lecture Notes in Computer Science(), vol 9310. Springer, Cham. https://doi.org/10.1007/978-3-319-23540-0_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-23540-0_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23539-4
Online ISBN: 978-3-319-23540-0
eBook Packages: Computer ScienceComputer Science (R0)