zbMATH — the first resource for mathematics

Magic Sets and their application to data integration. (English) Zbl 1115.68047
Summary: Recently, effective methods model query-answering in data integration systems and inconsistent databases in terms of cautious reasoning over Datalog\(^{\neg}\) programs under the stable model semantics. Since this task is computationally expensive (co-NP-complete), there is a clear need of suitable techniques for query optimization, in order to make such methods feasible for data-intensive applications.
We propose a generalization of the well-known Magic Sets technique to Datalog\(^{\neg}\) programs with (possibly unstratified) negation under the stable model semantics. Our technique produces a new program whose evaluation is more efficient (due to a smaller instantiation) in general, while preserving full query-equivalence for both brave and cautious reasoning, provided that the original program is consistent. Soundness under cautious reasoning is always guaranteed, even if the original program is inconsistent.
In order to formally prove the correctness of our Magic Sets transformation, we introduce a novel notion of modularity for Datalog\(^{\neg}\) under the stable model semantics, which is more suitable for query answering than previous module definitions. We prove that a query on such a module can be evaluated independently from the rest of the program, while preserving soundness under cautious reasoning. Importantly, for consistent programs, both soundness and completeness are guaranteed for brave reasoning and cautious reasoning.
Our Magic Sets optimization constitutes an effective method for enhancing the performance of data integration systems in which query-answering is carried out by means of cautious reasoning over Datalog\(^{\neg}\) programs. In fact, results of experiments in the EU project INFOMIX, show that Magic Sets are fundamental for the scalability of the system.

68N17 Logic programming
Full Text: DOI
[1] Ullman, J.D., Principles of database and knowledge base systems, (1989), Computer Science Press
[2] Gelfond, M.; Lifschitz, V., The stable model semantics for logic programming, (), 1070-1080
[3] Bidoit, N.; Froidevaux, C., Negation by default and unstratifiable logic programs, Theoret. comput. sci., 78, 85-112, (1991) · Zbl 0716.68075
[4] Dantsin, E.; Eiter, T.; Gottlob, G.; Voronkov, A., Complexity and expressive power of logic programming, ACM comput. surveys, 33, 3, 374-425, (2001)
[5] Leone, N.; Pfeifer, G.; Faber, W.; Eiter, T.; Gottlob, G.; Perri, S.; Scarcello, F., The DLV system for knowledge representation and reasoning, ACM trans. comput. log., 7, 3, 499-562, (2006) · Zbl 1367.68308
[6] I. Niemelä, P. Simons, T. Syrjänen, Smodels: A system for answer set programming, in: C. Baral, M. Truszczyński (Eds.), Proceedings of the 8th International Workshop on Non-Monotonic Reasoning, NMR 2000, Breckenridge, Colorado, USA, 2000
[7] Arenas, M.; Bertossi, L.E.; Chomicki, J., Specifying and querying database repairs using logic programs with exceptions, (), 27-41
[8] Greco, G.; Greco, S.; Zumpano, E., A logic programming approach to the integration, repairing and querying of inconsistent databases, (), 348-364 · Zbl 1053.68564
[9] P. Barceló, L. Bertossi, Repairing databases with annotated predicate logic, in: Proc. the 10th Int. Workshop on Non-Monotonic Reasoning, NMR 2002, 2002, pp. 160-170
[10] A. Calì, D. Lembo, R. Rosati, Query rewriting and answering under constraints in data integration systems, in: Proc. of the 18th Int. Joint Conf. on Artificial Intelligence, IJCAI 2003, 2003, pp. 16-21
[11] L. Bravo, L. Bertossi, Logic programming for consistently querying data integration systems, in: Proc. of the 18th Int. Joint Conf. on Artificial Intelligence, IJCAI 2003, 2003, pp. 10-15
[12] Chomicki, J.; Marcinkowski, J., Minimal-change integrity maintenance using tuple deletions, Inform. and comput., 197, 1-2, 90-121, (2005) · Zbl 1075.68022
[13] Schlipf, J., The expressive powers of logic programming semantics, J. comput. system sci., 51, 1, 64-86, (1995), abstract in: Proc. PODS ’90, pp. 196-204 · Zbl 0831.68012
[14] F. Bancilhon, D. Maier, Y. Sagiv, J.D. Ullman, Magic Sets and other strange ways to implement logic programs, in: Proc. Int. Symposium on Principles of Database Systems, 1986, pp. 1-16
[15] Beeri, C.; Ramakrishnan, R., On the power of magic, J. logic program., 10, 1-4, 255-259, (1991) · Zbl 0722.68018
[16] Mumick, I.S.; Finkelstein, S.J.; Pirahesh, H.; Ramakrishnan, R., Magic is relevant, in: Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, 1990, pp. 247-258, URL:
[17] Lifschitz, V.; Turner, H., Splitting a logic program, (), 23-37
[18] Eiter, T.; Gottlob, G.; Mannila, H., Disjunctive Datalog, ACM trans. database systems, 22, 3, 364-418, (1997)
[19] Gelfond, M.; Lifschitz, V., Classical negation in logic programs and disjunctive databases, New generation computing, 9, 365-385, (1991) · Zbl 0735.68012
[20] M. Lenzerini, Data integration: A theoretical perspective, in: Proc. of the 21st ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODS 2002, 2002, pp. 233-246
[21] L. Bertossi, J. Chomicki, A. Cortes, C. Gutierrez, Consistent answers from integrated data sources, in: Proc. of the 6th Int. Conf. on Flexible Query Answering Systems, FQAS 2002, 2002, pp. 71-85
[22] Bertossi, L.; Chomicki, J., Query answering in inconsistent databases, (), 43-83, (Chapter 2)
[23] Chomicki, J.; Marcinkowski, J.; Staworko, S., Hippo: A system for computing consistent answers to a class of SQL queries, (), 841-844
[24] Chomicki, J.; Marcinkowski, J.; Staworko, S., Computing consistent query answers using conflict hypergraphs, (), 417-426
[25] A. Fuxman, E. Fazli, R.J. Miller, Conquer: Efficient management of inconsistent databases, in: SIGMOD Conference, 2005
[26] Fuxman, A.; Miller, R.J., First-order query rewriting for inconsistent databases, (), 337-351 · Zbl 1112.68367
[27] Arenas, M.; Bertossi, L.; Chomicki, J., Scalar aggregation in FD-inconsistent databases, (), 39-53 · Zbl 1047.68560
[28] Chomicki, J.; Marcinkowski, J., Minimal-change integrity maintenance using tuple deletions, Inform. and comput., 197, 90-121, (2005) · Zbl 1075.68022
[29] Arenas, M.; Bertossi, L.E.; Chomicki, J., Consistent query answers in inconsistent databases, (), 68-79
[30] Dung, P.M., On the relations between stable and well-founded semantics of logic programs, Theoret. comput. sci., 105, 1, 7-25, (1992) · Zbl 0774.68028
[31] Ullman, J.D., Principles of database and knowledge base systems, vol. 2, (1989), Computer Science Press
[32] Abiteboul, S.; Hull, R.; Vianu, V., Foundations of databases, (1995), Addison-Wesley
[33] Arkin, E.M.; Papadimitriou, C.H.; Yannakakis, M., Modularity of cycles and paths in graphs, J. ACM, 38, 2, 255-274, (1991) · Zbl 0799.68146
[34] Johnson, D.S., A catalog of complexity classes, (), (Chapter 2) · Zbl 0900.68246
[35] M.Y. Vardi, Complexity of relational query languages, in: Proceedings of the 14th Symposium on Theory of Computation, STOC, 1982, pp. 137-146
[36] A. Calì, D. Lembo, R. Rosati, On the decidability and complexity of query answering over inconsistent and incomplete databases, in: Proc. of the 22st ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODS 2003, 2003, pp. 260-271
[37] INFOMIX Project Team, Demo scenario, (June 2004), Tech. Rep. INFOMIX S7-1, INFOMIX Project Consortium, available at
[38] Calì, A.; Calvanese, D.; De Giacomo, G.; Lenzerini, M., Data integration under integrity constraints, Inform. syst., 29, 2, 147-163, (2004)
[39] D. Lembo, M. Lenzerini, R. Rosati, Methods and techniques for query rewriting, Tech. Rep. D5.2, Infomix Consortium, October 2003
[40] D. Lembo, Dealing with inconsistency and incompleteness in data integration, PhD thesis, Università di Roma “La Sapienza,” 2004
[41] Stuckey, P.J.; Sudarshan, S., Compiling query constraints, (), 56-67
[42] Ross, K.A., Modular stratification and magic sets for Datalog programs with negation, J. ACM, 41, 6, 1216-1266, (1994) · Zbl 0830.68028
[43] Kemp, D.B.; Srivastava, D.; Stuckey, P.J., Bottom-up evaluation and query optimization of well-founded models, Theoret. comput. sci., 146, 145-184, (1995) · Zbl 0873.68032
[44] Seshadri, P.; Hellerstein, J.M.; Pirahesh, H.; Leung, T.Y.C.; Ramakrishnan, R.; Srivastava, D.; Stuckey, P.J.; Sudarshan, S., Cost-based optimization for magic: algebra and implementation, (), 435-446
[45] Behrend, A., Soft stratification for magic set based query evaluation in deductive databases, (), 102-110
[46] Greco, S., Binding propagation techniques for the optimization of bound disjunctive queries, IEEE trans. knowledge and data engineering, 15, 2, 368-385, (2003)
[47] Cumbo, C.; Faber, W.; Greco, G., Enhancing the magic-set method for disjunctive Datalog programs, (), 371-385 · Zbl 1104.68371
[48] G. Greco, S. Greco, I. Trubitsyna, E. Zumpano, Optimization of bound disjunctive queries with constraints, theory and practice of logic programming · Zbl 1085.68019
[49] T. Eiter, M. Fink, G. Greco, D. Lembo, Efficient evaluation of logic programs for querying data integration systems, in: Proc. of the 19th Int. Conf. on Logic Programming, ICLP ’03, 2003, pp. 163-177 · Zbl 1204.68080
[50] Fagin, R.; Kolaitis, P.; Miller, R.J.; Popa, L., Data exchange: semantics and query answering, Special issue for selected papers from the 2003 international conference on database theory, Theoret. comput. sci., 336, 89-124, (2005) · Zbl 1080.68019
[51] Fagin, R.; Kolaitis, P.G.; Popa, L., Data exchange: getting to the core, ACM trans. database systems, 30, 1, 174-210, (2005) · Zbl 1326.68119
[52] Gottlob, G., Computing cores for data exchange: new algorithms and practical solutions, (), 148-159
[53] Kolaitis, P.G.; Panttaja, J.; Tan, W., The complexity of data exchange, (), 30-39
[54] Gottlob, G.; Nash, A., Data exchange: computing cores in polynomial time, (), 40-49
[55] Benjelloun, O.; Sarma, A.D.; Hayworth, C.; Widom, J., An introduction to ULDBs and the trio system, Special issue on probabilistic databases, IEEE data engineering bulletin, 29, 5-16, (2006)
[56] Dalvi, N.N.; Miklau, G.; Suciu, D., Asymptotic conditional probabilities for conjunctive queries, (), 289-305 · Zbl 1112.68363
[57] Boulos, J.; Dalvi, N.; Mandhani, B.; Mathur, S.; Re, C.; Suciu, D., MYSTIQ: A system for finding more answers by using probabilities, (), 891-893
[58] J. Widom, Trio: A system for integrated management of data, accuracy, and lineage, in: Proceedings of the second Biennial Conference on Innovative Data Systems Research CIRD ’05, 2005, pp. 262-276
[59] Libkin, L., Data exchange and incomplete information, (), 60-69
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.