zbMATH — the first resource for mathematics

Prioritized repairing and consistent query answering in relational databases. (English) Zbl 1250.68099
Summary: A consistent query answer in an inconsistent database is an answer obtained in every (minimal) repair. The repairs are obtained by resolving all conflicts in all possible ways. Often, however, the user is able to provide a preference on how conflicts should be resolved. We investigate here the framework of preferred consistent query answers, in which user preferences are used to narrow down the set of repairs to a set of preferred repairs. We axiomatize desirable properties of preferred repairs. We present three different families of preferred repairs and study their mutual relationships. Finally, we investigate the complexity of preferred repairing and computing preferred consistent query answers.

68P15 Database theory
Full Text: DOI
[1] Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley (1995) · Zbl 0848.68031
[2] Afrati, F., Kolaitis, P.: Repair checking in inconsistent databases: algorithms and complexity. In: International Conference on Database Theory (ICDT), pp. 31–41. ACM (2009)
[3] Andritsos, P., Fuxman, A., Miller, R.J.: Clean answers over dirty databases: a probabilistic approach. In: International Conference on Data Engineering (ICDE), p. 30 (2006)
[4] Arenas, M., Bertossi, L., Chomicki, J.: Consistent query answers in inconsistent databases. In: ACM Symposium on Principles of Database Systems (PODS), pp. 68–79 (1999) · Zbl 1079.68026
[5] Arenas, M., Bertossi, L., Chomicki, J., He, X., Raghavan, V., Spinrad, J.: Scalar aggregation in inconsistent databases. Theoret. Comput. Sci. 296(3), 405–434 (2003) · Zbl 1045.68049 · doi:10.1016/S0304-3975(02)00737-5
[6] Bertossi, L.: Consistent query answering in databases. SIGMOD Record 35(2), 68–76 (2006) · Zbl 05445024 · doi:10.1145/1147376.1147391
[7] Bertossi, L., Chomicki, J.: Query answering in inconsistent databases. In: Chomicki, J., van der Meyden, R., Saake, G. (eds.) Logics for Emerging Applications of Databases, pp. 43–83. Springer (2003) · Zbl 1079.68026
[8] Bertossi, L.: Database repairing and consistent query answering. Synthesis Lectures on Data Management 3(5), 1–121 (2011) · Zbl 1238.68004 · doi:10.2200/S00379ED1V01Y201108DTM020
[9] Brewka, G.: Preferred subtheories: An extended logical framework for default reasoning. In: International Joint Conference on Artificial Intelligence (IJCAI), pp. 1043–1048 (1989) · Zbl 0713.68053
[10] Caroprese, L., Greco, S., Zumpano, E.: Active integrity constraints for database consistency maintenance. IEEE Trans. Knowl. Data Eng. 21(7), 1042–1058 (2009) · doi:10.1109/TKDE.2008.226
[11] Chomicki, J.: Preference formulas in relational queries. ACM T. Database Syst. 28(4), 427–466 (2003) · Zbl 05457011 · doi:10.1145/958942.958946
[12] Chomicki, J.: Consistent query answering: five easy pieces. In: International Conference on Database Theory (ICDT), pp. 1–17 (2007)
[13] Chomicki, J., Marcinkowski, J.: Minimal-change integrity maintenance using tuple deletions. Inform. Comput. 197(1–2), 90–121 (2005) · Zbl 1075.68022 · doi:10.1016/j.ic.2004.04.007
[14] Chomicki, J., Marcinkowski, J.: On the computational complexity of minimal-change integrity maintenance in relational databases. In: Bertossi, L., Hunter, A., Schaub, T., (eds.) Inconsistency Tolerance, pp. 119–150. LNCS 3300. Springer (2005) · Zbl 1111.68030
[15] Chomicki, J., Marcinkowski, J., Staworko, S.: Computing consistent query answers using conflict hypergraphs. In: International Conference on Information and Knowledge Management (CIKM), pp. 417–426. ACM Press (2004)
[16] Fagin, R., Ullman, J.D., Vardi, M.Y.: On the semantics of updates in databases. In: ACM Symposium on Principles of Database Systems (PODS), pp. 352–356 (1983)
[17] Fan, W.: Dependencies revisited for improving data quality. In: ACM Symposium on Principles of Database Systems (PODS), pp. pages 159–170 (2008)
[18] Fuxman, A., Kolaitis, P., Miller, R., Tan, W.-C.: Peer data exchange. ACM T. Database Syst. 31(4), 1454–1498 (2006) · doi:10.1145/1189769.1189778
[19] Gatterbauer, W., Suciu, D.: Data conflict resolution using trust mappings. In: ACM SIGMOD International Conference on Management of Data, pp. 219–230 (2010)
[20] Greco, G., Lembo, D.: Data integration with preferences among sources. In: International Conference on Conceptual Modeling (ER), pp. 231–244. Springer (2004)
[21] Greco, S., Sirangelo, C., Trubitsyna, I., Zumpano, E.: Feasibility conditions and preference criteria in quering and repairing inconsistent databases. In: International Conference on Database and Expert Systems Applications (DEXA), pp. 44–55 (2004)
[22] Grosof, B.N.: Prioritized conflict handling for logic programs. In: International Logic Programming Symposium, pp. 197–211 (1997)
[23] Halpern, J.Y.: Defining relative likehood in partially-ordered preferential structures. J. Artificial Intelligence Res. 7, 1–24 (1997) · Zbl 0895.03010
[24] Koltun, V., Papadimitriou, C.: Approximately dominating representatives. Theoret. Comput. Sci. 371(3), 148–154 (2007) · Zbl 1108.68042 · doi:10.1016/j.tcs.2006.11.003
[25] Martinez, M.V., Parisi, F., Pugliese, A., Simari, G.I., Subrahmanian, V.S.: Inconsistency management policies. In: International Conference on Principles of Knowledge Representation and Reasoning (KR), pp. 367–377 (2008)
[26] Motro, A., Anokhin, P., Acar, A.C.: Utility-based resolution of data inconsistencies. In: International Workshop on Information Quality in Information Systems (IQIS), pp. 35–43. ACM (2004)
[27] Sakama, C., Inoue, K.: Prioritized logic programming and its application to commonsense reasoning. Artif. Intell. 123, 185–222 (2000) · Zbl 0952.68020 · doi:10.1016/S0004-3702(00)00054-0
[28] Staworko, S., Chomicki, J.: Consistent query answers in the presence of universal constraints. Inform. Syst. 35(1), 1–22 (2010) · Zbl 05695910 · doi:10.1016/j.is.2009.03.004
[29] Staworko, S., Chomicki, J., Marcinkowski, J.: Preference-driven querying of inconsistent relational databases. In: EDBT Workshops (IIDB), pp. 318–335. Springer (2006)
[30] D. Van Nieuwenborgh and D. Vermeir. Preferred answer sets for ordered logic programs. In: European Conference on Logics for Artificial Intelligence (JELIA), pp. 432–443. LNCS 2424. Springer (2002) · Zbl 1013.68062
[31] Vardi, M.Y.: The complexity of relational query languages. In: ACM Symposium on Theory of Computing (STOC), pp. 137–146 (1982)
[32] Wijsen, J.: Database repairing using updates. ACM T. Database Syst. 30(3), 722–768 (2005) · Zbl 05457080 · doi:10.1145/1093382.1093385
[33] Wijsen, J.: On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases. In: ACM Symposium on Principles of Database Systems (PODS), pp. 179–190 (2010)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.