×

Scalar aggregation in inconsistent databases. (English) Zbl 1045.68049

Summary: We consider here scalar aggregation queries in databases that may violate a given set of functional dependencies. We define consistent answers to such queries to be greatest-lowest/least-upper bounds on the value of the scalar function across all (minimal) repairs of the database. We show how to compute such answers. We provide a complete characterization of the computational complexity of this problem. We also show how tractability can be improved in several special cases (one involves a novel application of Boyce-Codd normal form) and present a practical hybrid query evaluation method.

MSC:

68P15 Database theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abiteboul, S.; Hull, R.; Vianu, V., Foundations of Databases (1995), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0848.68031
[2] S. Agarwal, A.M. Keller, G. Wiederhold, K. Saraswat, Flexible relation: an approach for integrating data from multiple, possibly inconsistent databases, in: IEEE Internat. Conf. on Data Engineering, Taipei, Taiwan, 1995.; S. Agarwal, A.M. Keller, G. Wiederhold, K. Saraswat, Flexible relation: an approach for integrating data from multiple, possibly inconsistent databases, in: IEEE Internat. Conf. on Data Engineering, Taipei, Taiwan, 1995.
[3] M. Arenas, L. Bertossi, J. Chomicki, Consistent query answers in inconsistent databases, in: ACM Symp. on Principles of Database Systems, Philadelphia, PA, 1999, pp. 68-79.; M. Arenas, L. Bertossi, J. Chomicki, Consistent query answers in inconsistent databases, in: ACM Symp. on Principles of Database Systems, Philadelphia, PA, 1999, pp. 68-79. · Zbl 1079.68026
[4] Arenas, M.; Bertossi, L.; Chomicki, J., Specifying and querying database repairs using logic programs with exceptions, (Internat. Conf. on Flexible Query Answering Systems (2000), Springer: Springer Berlin), 27-41
[5] Arenas, M.; Bertossi, L.; Chomicki, J., Scalar aggregation in FD-inconsistent databases, (Internat. Conf. on Database Theory, Lecture Notes in Computer Science, Vol. 1973 (2001), Springer: Springer Berlin), 39-53 · Zbl 1047.68560
[6] Baral, C.; Kraus, S.; Minker, J.; Subrahmanian, V. S., Combining knowledge bases consisting of first-order theories, Comput. Intell., 8, 45-71 (1992)
[7] Bry, F., Query answering in information systems with integrity constraints, (IFIP WG 11.5 Working Conf. on Integrity and Control in Information Systems (1997), Chapman & Hall: Chapman & Hall London)
[8] Chandra, A. K.; Harel, D., Computable queries for relational databases, J. Comput. System Sci., 21, 156-178 (1980) · Zbl 0456.68128
[9] Chen, A. L.P.; Chiu, J-S.; Tseng, F. S.C., Evaluating aggregate operations over imprecise data, IEEE Trans. Philadelphia, PA, Knowledge Data Engrg., 8, 2, 273-284 (1996)
[10] S. Cohen, W. Nutt, A. Serebrenik, Rewriting aggregate queries using views, in: Proc. ACM PODS’99, 1999, pp. 155-166.; S. Cohen, W. Nutt, A. Serebrenik, Rewriting aggregate queries using views, in: Proc. ACM PODS’99, 1999, pp. 155-166.
[11] S. Cohen, W. Nutt, A. Serebrenik, Algorithms for rewriting aggregate queries using views, in: Proc. Symp. on Advances in Databases and Information Systems, ADBIS-DASFAA’ 2000, Prague, September, 2000, pp. 65-78.; S. Cohen, W. Nutt, A. Serebrenik, Algorithms for rewriting aggregate queries using views, in: Proc. Symp. on Advances in Databases and Information Systems, ADBIS-DASFAA’ 2000, Prague, September, 2000, pp. 65-78.
[12] L.G. De Michiel, Performing database operations over mismatched domains, Ph.D. Thesis, Stanford University, 1989.; L.G. De Michiel, Performing database operations over mismatched domains, Ph.D. Thesis, Stanford University, 1989.
[13] P.M. Dung, Integrating data from possibly inconsistent databases, in: Internat. Conf. on Cooperative Information Systems, Brussels, Belgium, 1996.; P.M. Dung, Integrating data from possibly inconsistent databases, in: Internat. Conf. on Cooperative Information Systems, Brussels, Belgium, 1996.
[14] Garey, M. R.; Johnson, D. S., Computers and IntractabilityA Guide to the Theory of NP Completeness (1979), Freeman: Freeman New York
[15] Giannotti, F.; Greco, S.; Sacca, D.; Zaniolo, C., Programming with non-determinism in deductive databases, Ann. Math. Artificial Intell., 19, 3-4, 97-125 (1997) · Zbl 0880.68030
[16] Giannotti, F.; Pedreschi, D., Datalog with non-deterministic choice computes NDB-PTIME, J. Logic Programming, 35, 75-101 (1998) · Zbl 0905.68031
[17] Greco, G.; Greco, S.; Zumpano, E., A logic programming approach to the integration, repairing and querying of inconsistent databases, (Codognet, P., Internat. Conf. on Logic Programming, Lecture Notes in Computer Science, Vol. 2237 (2001), Springer: Springer Berlin), 348-364 · Zbl 1053.68564
[18] Greco, S.; Sacca, D.; Zaniolo, C., Datalog queries with stratified negation and choicefrom \(P\) to \(D^P\), (Gottlob, G.; Vardi, M. Y., Internat. Conf. on Database Theory (1995), Springer: Springer Berlin), 82-96
[19] Hochbaum, D. S., Approximating covering and packing problemsset cover, vertex cover, independent set, and related problems, (Hochbaum, D. S., Approximation Algorithms for NP-Hard Problems (1997), PWS Publishing Co: PWS Publishing Co MA)
[20] Hopcroft, J. E.; Karp, R. M., An \(O(n^{5/2})\) algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, 225-231 (1973) · Zbl 0266.05114
[21] Imieliński, T.; Lipski, W., Incomplete information in relational databases, J. ACM, 31, 4, 761-791 (1984) · Zbl 0632.68094
[22] T. Imieliński, S. Naqvi, K. Vadaparty, Incomplete objects—a data model for design and planning applications, in: J. Cliff, R. King (Eds.), ACM SIGMOD Internat. Conf. on Management of Data, Denver, Colorado, May 1991, pp. 288-297.; T. Imieliński, S. Naqvi, K. Vadaparty, Incomplete objects—a data model for design and planning applications, in: J. Cliff, R. King (Eds.), ACM SIGMOD Internat. Conf. on Management of Data, Denver, Colorado, May 1991, pp. 288-297.
[23] Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart and Winston: Holt, Rinehart and Winston New York · Zbl 0358.68059
[24] Levy, A. Y.; Mumick, I. S., Reasoning with aggregation constraints, (Proc. EDBT (1996), Avignon: Avignon France), 514-534
[25] Lin, J.; Mendelzon, A. O., Merging databases under constraints, Internat. J. Cooperative Inform. Syst., 7, 1, 55-76 (1996)
[26] Minty, G. J., On maximal independent sets of vertices in claw-free graphs, J. Combin. Theory B, 28, 284-304 (1980) · Zbl 0434.05043
[27] Ross, K. A.; Srivastava, D.; Stuckey, P. J.; Sudarshan, S., Foundations of aggregation constraints, Theoret. Comput. Sci., 193, 1-2, 149-179 (1998) · Zbl 0896.68047
[28] Sbihi, M., Algorithme de Recherche d’un Stable de Cardinalité Maximum dans un Graphe sans Étoile, Discrete Math., 29, 53-76 (1980) · Zbl 0444.05049
[29] D. Srivastava, S. Dar, H.V. Jagadish, A.Y. Levy, Answering queries with aggregation using views, in: Proc. VLDB’96, Bombay, India, 1996, pp. 318-329.; D. Srivastava, S. Dar, H.V. Jagadish, A.Y. Levy, Answering queries with aggregation using views, in: Proc. VLDB’96, Bombay, India, 1996, pp. 318-329.
[30] van der Meyden, R., Logical approaches to incomplete information: a survey, (Chomicki, J.; Saake, G., Logics for Databases and Information Systems, Chap. 10 (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Boston) · Zbl 0903.68064
[31] M.Y. Vardi, The complexity of relational query languages, in: ACM Symp. on Theory of Computing, San Francisco, CA, 1982, pp. 137-146.; M.Y. Vardi, The complexity of relational query languages, in: ACM Symp. on Theory of Computing, San Francisco, CA, 1982, pp. 137-146.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.