Abstract
Uncertainty is modeled by a multibase (db,μ) where db is a database with zero or more primary key violations, and μ associates a multiplicity (a positive integer) to each fact of db. In data integration, the multiplicity of a fact g can indicate the number of data sources in which g was found. In planning databases, facts with the same primary key value are alternatives for each other, and the multiplicity of a fact g can denote the number of people in favor of g.
A repair of db is obtained by selecting a maximal number of facts without ever selecting two distinct facts of the same relation that agree on their primary key. Every repair has a support count, which is the product of the multiplicities of its facts.
For a fixed Boolean query q, we define σ CERTAINTY(q) as the following counting problem: Given a multibase (db,μ), determine the weighted number of repairs of db that satisfy q. Here, every repair is weighted by its support count. We illustrate the practical significance of this problem by means of examples.
For conjunctive queries q without self-join, we provide a syntactic characterization of the class of queries q such that σ CERTAINTY(q) is in P; for queries not in this class, σ CERTAINTY(q) is \(\sharp\) P-hard (and hence highly intractable).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)
Arenas, M., Bertossi, L.E., Chomicki, J.: Consistent query answers in inconsistent databases. In: PODS, pp. 68–79. ACM Press, New York (1999)
Arenas, M., Bertossi, L.E., Chomicki, J., He, X., Raghavan, V., Spinrad, J.: Scalar aggregation in inconsistent databases. Theor. Comput. Sci. 296(3), 405–434 (2003)
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)
Dalvi, N.N., Suciu, D.: Management of probabilistic data: foundations and challenges. In: Libkin, L. (ed.) PODS, pp. 1–12. ACM, New York (2007)
Fan, W., Geerts, F., Wijsen, J.: Determining the currency of data. In: Lenzerini, M., Schwentick, T. (eds.) PODS, pp. 71–82. ACM, New York (2011)
Fuxman, A., Miller, R.J.: First-order query rewriting for inconsistent databases. J. Comput. Syst. Sci. 73(4), 610–635 (2007)
Greco, S., Molinaro, C.: Approximate probabilistic query answering over inconsistent databases. In: Li, Q., Spaccapietra, S., Yu, E.S.K., Olivé, A. (eds.) ER 2008. LNCS, vol. 5231, pp. 311–325. Springer, Heidelberg (2008)
Maslowski, D., Wijsen, J.: On counting database repairs. In: Proceedings of the 4th International Workshop on Logic in Databases, LID 2011, pp. 15–22. ACM, New York (2011), http://doi.acm.org/10.1145/1966357.1966361
Pema, E., Kolaitis, P.G., Tan, W.C.: On the tractability and intractability of consistent conjunctive query answering. In: Proceedings of the 2011 Joint EDBT/ICDT Ph.D. Workshop, PhD 2011, pp. 38–44. ACM, New York (2011), http://doi.acm.org/10.1145/1966874.1966881
Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865–877 (1991)
Wijsen, J.: On the consistent rewriting of conjunctive queries under primary key constraints. Inf. Syst. 34(7), 578–601 (2009)
Wijsen, J.: On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases. In: Paredaens, J., Gucht, D.V. (eds.) PODS, pp. 179–190. ACM, New York (2010)
Wijsen, J.: A remark on the complexity of consistent conjunctive query answering under primary key violations. Inf. Process. Lett. 110(21), 950–955 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Maslowski, D., Wijsen, J. (2011). Uncertainty That Counts. In: Christiansen, H., De Tré, G., Yazici, A., Zadrozny, S., Andreasen, T., Larsen, H.L. (eds) Flexible Query Answering Systems. FQAS 2011. Lecture Notes in Computer Science(), vol 7022. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24764-4_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-24764-4_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24763-7
Online ISBN: 978-3-642-24764-4
eBook Packages: Computer ScienceComputer Science (R0)