Abstract
A database D may be inconsistent wrt a given set IC of integrity constraints. Consistent Query Answering (CQA) is the problem of computing from D the answers to a query that are consistent wrt IC. Consistent answers are invariant under all the repairs of D, i.e. the consistent instances that minimally depart from D. Three classes of repair have been considered in the literature: those that minimize set-theoretically the set of tuples in the symmetric difference; those that minimize the changes of attribute values, and those that minimize the cardinality of the set of tuples in the symmetric difference. The latter class has not been systematically investigated. In this paper we obtain algorithmic and complexity theoretic results for CQA under this cardinality-based repair semantics. We do this in the usual, static setting, but also in a dynamic framework where a consistent database is affected by a sequence of updates, which may make it inconsistent. We also establish comparative results with the other two kinds of repairs in the dynamic case.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arenas, M., Bertossi, L., Chomicki, J.: Consistent Query Answers in Inconsistent Databases. In: Proc. ACM Symposium on Principles of Database Systems (PODS 1999), pp. 68–79. ACM Press, New York (1999)
Arenas, M., Bertossi, L., Chomicki, J.: Answer Sets for Consistent Query Answering in Inconsistent Databases. Theory and Practice of Logic Programming 3(4-5), 393–424 (2003)
Arenas, M., Bertossi, L., Chomicki, J., He, X., Raghavan, V., Spinrad, J.: Scalar Aggregation in Inconsistent Databases. Theoretical Computer Science 296, 405–434 (2003)
Bertossi, L., Bravo, L., Franconi, E., Lopatenko, A.: Fixing Numerical Attributes under Integrity Constraints. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol. 3774, pp. 262–278. Springer, Heidelberg (2005)
Bertossi, L., Chomicki, J.: Query Answering in Inconsistent Databases. In: Logics for Emerging Applications of Databases, pp. 43–83. Springer, Heidelberg (2003)
Buccafurri, F., Leone, N., Rullo, P.: Enhancing Disjunctive Datalog by Constraints. IEEE Transactions on Knowledge and Data Engineering 12(5), 845–860 (2000)
Calì, A., Lembo, D., Rosati, R.: Complexity of Query Answering over Inconsistent and Incomplete Databases. In: Proc. ACM Symposium on Principles of Database Systems (PODS 2003), pp. 260–271. ACM Press, New York (2003)
Chen, J., Kanj, I., Jia, W.: Vertex Cover: Further Observations and Further Improvements. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol. 1665, pp. 313–324. Springer, Heidelberg (1999)
Chomicki, J., Marcinkowski, J.: Minimal-Change Integrity Maintenance using Tuple Deletions. Information and Computation 197(1-2), 90–121 (2005)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, Heidelberg (1999)
Eiter, T., Gottlob, G.: On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals. Artificial Intelligence 57(2-3), 227–270 (1992)
Flesca, S., Furfaro, F., Parisi, F.: Consistent Query Answers on Numerical Databases under Aggregate Constraints. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol. 3774, pp. 279–294. Springer, Heidelberg (2005)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer, Heidelberg (2006)
Franconi, E., Laureti Palma, A., Leone, N., Perri, S., Scarcello, F.: Census Data Repair: a Challenging Application of Disjunctive Logic Programming. In: Nieuwenhuis, R., Voronkov, A. (eds.) LPAR 2001. LNCS (LNAI), vol. 2250, pp. 561–578. Springer, Heidelberg (2001)
Fuxman, A., Miller, R.: First-Order Query Rewriting for Inconsistent Databases. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol. 3363, pp. 337–351. Springer, Heidelberg (2004)
Garey, M., Johnson, D., Stockmeyer, L.: Some Simplified NP-Complete Graph Problems. Theoretical Computer Science 1(3), 237–267 (1976)
Gelfond, M., Lifschitz, V.: Classical Negation in Logic Programs and Disjunctive Databases. New Generation Computing 9, 365–385 (1991)
Greco, G., Scarcello, F.: On the Complexity of Computing Peer Agreements for Consistent Query Answering in Peer-to-Peer Data Integration Systems. In: Proc. International Conference on Information and Knowledge Management (CIKM 2005), pp. 36–43. ACM Press, New York (2005)
Grohe, M.: Parameterized Complexity for the Data-base Theorist. SIGMOD Record 31(4), 86–96 (2002)
Immerman, N.: Descriptive Complexity. Graduate Texts in Computer Science. Springer, Heidelberg (1999)
Krentel, M.: The Complexity of Optimization Problems. J. Computer and Systems Sciences 36, 490–509 (1988)
Lopatenko, A., Bertossi, L.: Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Semantics. Corr Archiv paper cs.DB/0604002
Miltersen, P.B., Subramanian, S., Vitter, J.S., Tamassia, R.: Complexity Models for Incremental Computation. Theoretical Computer Science 130(1), 203–236 (1994)
Niedermeier, R., Rossmanith, P.: An Efficient Fixed-Parameter Algorithm for 3-Hitting Set. Journal of Discrete Algorithms 1(1), 89–102 (2003)
Papadimitriou, C.H., Yannakakis, M.: On the Complexity of Database Queries. J. Comput. Syst. Sci. 58(3), 407–427 (1999)
Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)
Robertson, N., Sanders, D.P., Seymour, P., Thomas, R.: Eficiently Four-Coloring Planar Graphs. In: Proc. 28th ACM Symposium on the Theory of Computing (STOC 1996), pp. 571–575. ACM Press, New York (1996)
Weber, V., Schwentick, T.: Dynamic Complexity Theory Revisited. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 256–268. Springer, Heidelberg (2005)
Wijsen, J.: Condensed Representation of Database Repairs for Consistent Query Answering. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol. 2572, pp. 378–393. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lopatenko, A., Bertossi, L. (2006). Complexity of Consistent Query Answering in Databases Under Cardinality-Based and Incremental Repair Semantics. In: Schwentick, T., Suciu, D. (eds) Database Theory – ICDT 2007. ICDT 2007. Lecture Notes in Computer Science, vol 4353. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11965893_13
Download citation
DOI: https://doi.org/10.1007/11965893_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69269-0
Online ISBN: 978-3-540-69270-6
eBook Packages: Computer ScienceComputer Science (R0)