{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T17:30:52Z","timestamp":1782754252287,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540692690","type":"print"},{"value":"9783540692706","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11965893_13","type":"book-chapter","created":{"date-parts":[[2006,12,7]],"date-time":"2006-12-07T07:52:22Z","timestamp":1165477942000},"page":"179-193","source":"Crossref","is-referenced-by-count":49,"title":["Complexity of Consistent Query Answering in Databases Under Cardinality-Based and Incremental Repair Semantics"],"prefix":"10.1007","author":[{"given":"Andrei","family":"Lopatenko","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leopoldo","family":"Bertossi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1145\/303976.303983","volume-title":"Proc. ACM Symposium on Principles of Database Systems (PODS 1999)","author":"M. Arenas","year":"1999","unstructured":"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\u201379. ACM Press, New York (1999)"},{"issue":"4-5","key":"13_CR2","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1017\/S1471068403001832","volume":"3","author":"M. Arenas","year":"2003","unstructured":"Arenas, M., Bertossi, L., Chomicki, J.: Answer Sets for Consistent Query Answering in Inconsistent Databases. Theory and Practice of Logic Programming\u00a03(4-5), 393\u2013424 (2003)","journal-title":"Theory and Practice of Logic Programming"},{"key":"13_CR3","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/S0304-3975(02)00737-5","volume":"296","author":"M. Arenas","year":"2003","unstructured":"Arenas, M., Bertossi, L., Chomicki, J., He, X., Raghavan, V., Spinrad, J.: Scalar Aggregation in Inconsistent Databases. Theoretical Computer Science\u00a0296, 405\u2013434 (2003)","journal-title":"Theoretical Computer Science"},{"key":"13_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/11601524_17","volume-title":"Database Programming Languages","author":"L. Bertossi","year":"2005","unstructured":"Bertossi, L., Bravo, L., Franconi, E., Lopatenko, A.: Fixing Numerical Attributes under Integrity Constraints. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol.\u00a03774, pp. 262\u2013278. Springer, Heidelberg (2005)"},{"key":"13_CR5","first-page":"43","volume-title":"Logics for Emerging Applications of Databases","author":"L. Bertossi","year":"2003","unstructured":"Bertossi, L., Chomicki, J.: Query Answering in Inconsistent Databases. In: Logics for Emerging Applications of Databases, pp. 43\u201383. Springer, Heidelberg (2003)"},{"issue":"5","key":"13_CR6","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1109\/69.877512","volume":"12","author":"F. Buccafurri","year":"2000","unstructured":"Buccafurri, F., Leone, N., Rullo, P.: Enhancing Disjunctive Datalog by Constraints. IEEE Transactions on Knowledge and Data Engineering\u00a012(5), 845\u2013860 (2000)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"13_CR7","first-page":"260","volume-title":"Proc. ACM Symposium on Principles of Database Systems (PODS 2003)","author":"A. Cal\u00ec","year":"2003","unstructured":"Cal\u00ec, 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\u2013271. ACM Press, New York (2003)"},{"key":"13_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/3-540-46784-X_30","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. Chen","year":"1999","unstructured":"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.\u00a01665, pp. 313\u2013324. Springer, Heidelberg (1999)"},{"issue":"1-2","key":"13_CR9","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.ic.2004.04.007","volume":"197","author":"J. Chomicki","year":"2005","unstructured":"Chomicki, J., Marcinkowski, J.: Minimal-Change Integrity Maintenance using Tuple Deletions. Information and Computation\u00a0197(1-2), 90\u2013121 (2005)","journal-title":"Information and Computation"},{"key":"13_CR10","series-title":"Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, Heidelberg (1999)"},{"issue":"2-3","key":"13_CR11","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0004-3702(92)90018-S","volume":"57","author":"T. Eiter","year":"1992","unstructured":"Eiter, T., Gottlob, G.: On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals. Artificial Intelligence\u00a057(2-3), 227\u2013270 (1992)","journal-title":"Artificial Intelligence"},{"key":"13_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/11601524_18","volume-title":"Database Programming Languages","author":"S. Flesca","year":"2005","unstructured":"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.\u00a03774, pp. 279\u2013294. Springer, Heidelberg (2005)"},{"key":"13_CR13","series-title":"Texts in Theoretical Computer Science","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer, Heidelberg (2006)"},{"key":"13_CR14","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/3-540-45653-8_39","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"E. Franconi","year":"2001","unstructured":"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.\u00a02250, pp. 561\u2013578. Springer, Heidelberg (2001)"},{"key":"13_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-540-30570-5_23","volume-title":"Database Theory - ICDT 2005","author":"A. Fuxman","year":"2004","unstructured":"Fuxman, A., Miller, R.: First-Order Query Rewriting for Inconsistent Databases. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol.\u00a03363, pp. 337\u2013351. Springer, Heidelberg (2004)"},{"issue":"3","key":"13_CR16","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. Garey","year":"1976","unstructured":"Garey, M., Johnson, D., Stockmeyer, L.: Some Simplified NP-Complete Graph Problems. Theoretical Computer Science\u00a01(3), 237\u2013267 (1976)","journal-title":"Theoretical Computer Science"},{"key":"13_CR17","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF03037169","volume":"9","author":"M. Gelfond","year":"1991","unstructured":"Gelfond, M., Lifschitz, V.: Classical Negation in Logic Programs and Disjunctive Databases. New Generation Computing\u00a09, 365\u2013385 (1991)","journal-title":"New Generation Computing"},{"key":"13_CR18","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1145\/1099554.1099564","volume-title":"Proc. International Conference on Information and Knowledge Management (CIKM 2005)","author":"G. Greco","year":"2005","unstructured":"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\u201343. ACM Press, New York (2005)"},{"issue":"4","key":"13_CR19","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/637411.637428","volume":"31","author":"M. Grohe","year":"2002","unstructured":"Grohe, M.: Parameterized Complexity for the Data-base Theorist. SIGMOD Record\u00a031(4), 86\u201396 (2002)","journal-title":"SIGMOD Record"},{"key":"13_CR20","series-title":"Graduate Texts in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive Complexity. Graduate Texts in Computer Science. Springer, Heidelberg (1999)"},{"key":"13_CR21","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M. Krentel","year":"1988","unstructured":"Krentel, M.: The Complexity of Optimization Problems. J. Computer and Systems Sciences\u00a036, 490\u2013509 (1988)","journal-title":"J. Computer and Systems Sciences"},{"key":"13_CR22","unstructured":"Lopatenko, A., Bertossi, L.: Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Semantics. Corr Archiv paper cs.DB\/0604002"},{"issue":"1","key":"13_CR23","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0304-3975(94)90159-7","volume":"130","author":"P.B. Miltersen","year":"1994","unstructured":"Miltersen, P.B., Subramanian, S., Vitter, J.S., Tamassia, R.: Complexity Models for Incremental Computation. Theoretical Computer Science\u00a0130(1), 203\u2013236 (1994)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"13_CR24","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S1570-8667(03)00009-1","volume":"1","author":"R. Niedermeier","year":"2003","unstructured":"Niedermeier, R., Rossmanith, P.: An Efficient Fixed-Parameter Algorithm for 3-Hitting Set. Journal of Discrete Algorithms\u00a01(1), 89\u2013102 (2003)","journal-title":"Journal of Discrete Algorithms"},{"issue":"3","key":"13_CR25","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1006\/jcss.1999.1626","volume":"58","author":"C.H. Papadimitriou","year":"1999","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the Complexity of Database Queries. J. Comput. Syst. Sci.\u00a058(3), 407\u2013427 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR26","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"13_CR27","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1145\/237814.238005","volume-title":"Proc. 28th ACM Symposium on the Theory of Computing (STOC 1996)","author":"N. Robertson","year":"1996","unstructured":"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\u2013575. ACM Press, New York (1996)"},{"key":"13_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-540-31856-9_21","volume-title":"STACS 2005","author":"V. Weber","year":"2005","unstructured":"Weber, V., Schwentick, T.: Dynamic Complexity Theory Revisited. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 256\u2013268. Springer, Heidelberg (2005)"},{"key":"13_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/3-540-36285-1_25","volume-title":"Database Theory - ICDT 2003","author":"J. Wijsen","year":"2002","unstructured":"Wijsen, J.: Condensed Representation of Database Repairs for Consistent Query Answering. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol.\u00a02572, pp. 378\u2013393. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Database Theory \u2013 ICDT 2007"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11965893_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:23:21Z","timestamp":1619508201000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11965893_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540692690","9783540692706"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/11965893_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}