Magic sets for disjunctive Datalog programs.

*(English)*Zbl 1251.68051Summary: In this paper, a new technique for the optimization of (partially) bound queries over disjunctive Datalog programs with stratified negation is presented. The technique exploits the propagation of query bindings and extends the magic set optimization technique (originally defined for non-disjunctive programs).

An important feature of disjunctive Datalog programs is non-monotonicity, which calls for non-deterministic implementations, such as backtracking search. A distinguishing characteristic of the new method is that the optimization can be exploited also during the non-deterministic phase. In particular, after some assumptions have been made during the computation, parts of the program may become irrelevant to a query under these assumptions. This allows for dynamic pruning of the search space. In contrast, the effect of the previously defined magic set methods for disjunctive Datalog is limited to the deterministic portion of the process. In this way, the potential performance gain by using the proposed method can be exponential, as could be observed empirically.

The correctness of the method is established and proved in a formal way thanks to a strong relationship between magic sets and unfounded sets that has not been studied in the literature before. This knowledge allows for extending the method and the correctness proof also to programs with stratified negation in a natural way.

The proposed method has been implemented in the DLV system and various experiments on synthetic as well as on real-world data have been conducted. The experimental results on synthetic data confirm the utility of magic sets for disjunctive Datalog, and they highlight the computational gain that may be obtained by the new method with respect to the previously proposed magic set method for disjunctive Datalog programs. Further experiments on data taken from a real-life application show the benefits of the magic set method within an application scenario that has received considerable attention in recent years, the problem of answering user queries over possibly inconsistent databases originating from integration of autonomous sources of information.

An important feature of disjunctive Datalog programs is non-monotonicity, which calls for non-deterministic implementations, such as backtracking search. A distinguishing characteristic of the new method is that the optimization can be exploited also during the non-deterministic phase. In particular, after some assumptions have been made during the computation, parts of the program may become irrelevant to a query under these assumptions. This allows for dynamic pruning of the search space. In contrast, the effect of the previously defined magic set methods for disjunctive Datalog is limited to the deterministic portion of the process. In this way, the potential performance gain by using the proposed method can be exponential, as could be observed empirically.

The correctness of the method is established and proved in a formal way thanks to a strong relationship between magic sets and unfounded sets that has not been studied in the literature before. This knowledge allows for extending the method and the correctness proof also to programs with stratified negation in a natural way.

The proposed method has been implemented in the DLV system and various experiments on synthetic as well as on real-world data have been conducted. The experimental results on synthetic data confirm the utility of magic sets for disjunctive Datalog, and they highlight the computational gain that may be obtained by the new method with respect to the previously proposed magic set method for disjunctive Datalog programs. Further experiments on data taken from a real-life application show the benefits of the magic set method within an application scenario that has received considerable attention in recent years, the problem of answering user queries over possibly inconsistent databases originating from integration of autonomous sources of information.

##### MSC:

68N17 | Logic programming |

PDF
BibTeX
XML
Cite

\textit{M. Alviano} et al., Artif. Intell. 187--188, 156--192 (2012; Zbl 1251.68051)

Full Text:
DOI

##### References:

[1] | Abiteboul, Serge; Hull, Richard; Vianu, Victor, Foundations of databases, (1995), Addison-Wesley · Zbl 0848.68031 |

[2] | Krzysztof R. Apt, Howard A. Blair, Adrian Walker, Towards a Theory of Declarative Knowledge, in: Minker [52], pp. 89-148. |

[3] | Arenas, Marcelo; Bertossi, Leopoldo; Chomicki, Jan, Scalar aggregation in fd-inconsistent databases, (), 39-53 · Zbl 1047.68560 |

[4] | Marcelo Arenas, Leopoldo E. Bertossi, Jan Chomicki, Consistent query answers in inconsistent databases, in: Proc. of the 18th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODSʼ99), 1999, pp. 68-79. · Zbl 1079.68026 |

[5] | Arenas, Marcelo; Bertossi, Leopoldo E.; Chomicki, Jan, Specifying and querying database repairs using logic programs with exceptions, (), 27-41 |

[6] | François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey 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. |

[7] | Pablo Barceló, Leopoldo Bertossi, Repairing databases with annotated predicate logic, in: Proc. the 10th Int. Workshop on Non-Monotonic Reasoning (NMR 2002), 2002, pp. 160-170. |

[8] | Baumgartner, Peter; Furbach, Ulrich; Niemelä, Ilkka, Hyper tableaux, (), 1-17 |

[9] | Beeri, Catriel; Ramakrishnan, Raghu, On the power of magic, Journal of logic programming, 10, 1-4, 255-259, (1991) · Zbl 0722.68018 |

[10] | Behrend, Andreas, Soft stratification for magic set based query evaluation in deductive databases, (), 102-110 |

[11] | Bertossi, Leo; Chomicki, Jan, Query answering in inconsistent databases, (), 43-83, Chapter 2 |

[12] | Leopoldo Bertossi, Jan Chomicki, Alvaro Cortes, Claudio 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. |

[13] | Bertossi, Leopoldo E.; Bravo, Loreto, Consistent query answers in virtual data integration systems, (), 42-83 · Zbl 1111.68666 |

[14] | Loreto Bravo, Leopoldo 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. |

[15] | Cadoli, Marco; Eiter, Thomas; Gottlob, Georg, Default logic as a query language, IEEE transactions on knowledge and data engineering, 9, 3, 448-463, (May/June 1997) |

[16] | Andrea Calì, Domenico Lembo, Riccardo 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. |

[17] | Chomicki, Jan; Marcinkowski, Jerzy, Minimal-change integrity maintenance using tuple deletions, Information and computation, 197, 1-2, 90-121, (2005) · Zbl 1075.68022 |

[18] | Chomicki, Jan; Marcinkowski, Jerzy; Staworko, Slawomir, Computing consistent query answers using conflict hypergraphs, (), 417-426 |

[19] | Chomicki, Jan; Marcinkowski, Jerzy; Staworko, Slawomir, Hippo: A system for computing consistent answers to a class of SQL queries, (), 841-844 |

[20] | Cumbo, Chiara; Faber, Wolfgang; Greco, Gianluigi; Leone, Nicola, Enhancing the magic-set method for disjunctive Datalog programs, (), 371-385 · Zbl 1104.68371 |

[21] | Drescher, Christian; Gebser, Martin; Grote, Torsten; Kaufmann, Benjamin; König, Arne; Ostrowski, Max; Schaub, Torsten, Conflict-driven disjunctive answer set solving, (), 422-432 |

[22] | Eiter, Thomas; Gottlob, Georg; Mannila, Heikki, Disjunctive Datalog, ACM transactions on database systems, 22, 3, 364-418, (September 1997) |

[23] | Wolfgang Faber, Enhancing efficiency and expressiveness in answer set programming systems, PhD thesis, Institut für Informationssysteme, Technische Universität Wien, 2002. |

[24] | Faber, Wolfgang; Greco, Gianluigi; Leone, Nicola, Magic sets and their application to data integration, Journal of computer and system sciences, 73, 4, 584-609, (2007) · Zbl 1115.68047 |

[25] | Ariel Fuxman, Elham Fazli, Renée J. Miller Conquer, Efficient management of inconsistent databases, in: SIGMOD Conference, 2005. |

[26] | Fuxman, Ariel; Miller, Renée J., First-order query rewriting for inconsistent databases, (), 337-351 · Zbl 1112.68367 |

[27] | Garey, Michael R.; Johnson, David S., Computers and intractability, A guide to the theory of NP-completeness, (1979), W.H. Freeman and Company · Zbl 0411.68039 |

[28] | Gebser, Martin; Schaub, Torsten; Thiele, Sven, Gringo: A new grounder for answer set programming, (), 266-271 |

[29] | Gelfond, M.; Lifschitz, V., The stable model semantics for logic programming, (), 1070-1080 |

[30] | Goldman, R.; Boddy, M., Expressive planning and explicit knowledge, (), 110-117 |

[31] | Greco, Gianluigi; Greco, Sergio; Zumpano, Ester, A logic programming approach to the integration, repairing and querying of inconsistent databases, (), 348-364 · Zbl 1053.68564 |

[32] | Greco, Sergio, Optimization of disjunction queries, (), 441-455 |

[33] | Greco, Sergio, Binding propagation techniques for the optimization of bound disjunctive queries, IEEE transactions on knowledge and data engineering, 15, 2, 368-385, (March/April 2003) |

[34] | Sergio Greco, Domenico Saccà, Carlo Zaniolo, The PushDown method to optimize chain logic programs, in: Proc. Int. Colloquim on Automata, Languages and Programming, 1995, pp. 523-534 (extended abstract). · Zbl 1412.68031 |

[35] | Ashish Gupta, Inderpal Singh Mumick, Magic-sets transformation in nonrecursive systems, in: Proceedings of the Thirteenth ACM SIGACT SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-92), 1992, pp. 354-367. |

[36] | Hustadt, Ullrich; Motik, Boris; Sattler, Ulrike, Reasoning in description logics by a reduction to disjunctive Datalog, Journal of automated reasoning, 39, 3, 351-384, (2007) · Zbl 1132.68735 |

[37] | Janhunen, Tomi; Niemelä, Ilkka; Seipel, Dietmar; Simons, Patrik; You, Jia-Huai, Unfolding partiality and disjunctions in stable model semantics, ACM transactions on computational logic, 7, 1, 1-37, (January 2006) |

[38] | Kemp, David B.; Srivastava, Divesh; Stuckey, Peter J., Bottom-up evaluation and query optimization of well-founded models, Theoretical computer science, 146, 145-184, (July 1995) |

[39] | Jean-Marc Kerisit, Jean-Marc Pugin, Efficient query answering on stratified databases, in: FGCS, 1988, pp. 719-726. |

[40] | Lee, Joohyung; Lifschitz, Vladimir, Loop formulas for disjunctive logic programs, () · Zbl 1204.68056 |

[41] | Maurizio 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. |

[42] | Leone, Nicola; Gottlob, Georg; Rosati, Riccardo; Eiter, Thomas; Faber, Wolfgang; Fink, Michael; Greco, Gianluigi; Ianni, Giovambattista; Kałka, Edyta; Lembo, Domenico; Lenzerini, Maurizio; Lio, Vincenzino; Nowicki, Bartosz; Ruzzi, Marco; Staniszkis, Witold; Terracina, Giorgio, The INFOMIX system for advanced integration of incomplete and inconsistent data, (), 915-917 |

[43] | Leone, Nicola; Pfeifer, Gerald; Faber, Wolfgang; Eiter, Thomas; Gottlob, Georg; Perri, Simona; Scarcello, Francesco, The DLV system for knowledge representation and reasoning, ACM transactions on computational logic, 7, 3, 499-562, (July 2006) |

[44] | Leone, Nicola; Rullo, Pasquale; Scarcello, Francesco, Disjunctive stable models: unfounded sets, fixpoint semantics and computation, Information and computation, 135, 2, 69-112, (June 1997) |

[45] | Liang, Senlin; Fodor, Paul; Wan, Hui; Kifer, Michael, Openrulebench: an analysis of the performance of rule engines, (), 601-610 |

[46] | Lierler, Yuliya, Disjunctive answer set programming via satisfiability, (), 447-451 · Zbl 1423.68483 |

[47] | Lin, Fangzhen; Zhao, Yuting, ASSAT: computing answer sets of a logic program by SAT solvers, () · Zbl 1085.68544 |

[48] | Lobo, Jorge; Minker, Jack; Rajasekar, Arcot, Foundations of disjunctive logic programming, (1992), The MIT Press Cambridge, MA · Zbl 0755.68033 |

[49] | Manna, Marco; Ruffolo, Massimo; Oro, Ermelinda; Alviano, Mario; Leone, Nicola, The hilex system for semantic information extraction, (), 91-125 |

[50] | Manna, Marco; Scarcello, Francesco; Leone, Nicola, On the complexity of regular-grammars with integer attributes, Journal of computer and system sciences (JCSS), 77, 2, 393-421, (2011) · Zbl 1218.68093 |

[51] | Mónica Caniupán Marileo, Leopoldo E. Bertossi, The consistency extractor system: Querying inconsistent databases using answer set programs, in: SUM 2007, 2007, pp. 74-88. |

[52] | () |

[53] | Boris Motik, Reasoning in description logics using resolution and deductive databases, PhD thesis, Fakultät für Wirtschaftswissenschaften, Universität Fridericiana zu Karlsruhe, 2006. |

[54] | Motik, Boris; Sattler, Ulrike, A comparison of reasoning techniques for querying large description logic aboxes, (), 227-241 · Zbl 1165.68506 |

[55] | Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan, Magic is relevant, in: Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, 1990, pp. 247-258. |

[56] | Ramakrishnan, Raghu; Sagiv, Yehoshua; Ullman, Jeffrey D.; Vardi, Moshe Y., Logical query optimization by proof-tree transformation, Journal of computer and system sciences, 47, 1, 222-248, (1993) · Zbl 0808.68057 |

[57] | Ricca, Francesco; Alviano, Mario; Dimasi, Antonella; Grasso, Giovanni; Maria Ielpa, Salvatore; Iiritano, Salvatore; Manna, Marco; Leone, Nicola, A logic-based system for e-tourism, Fundamenta informaticae, 105, 1-2, 35-55, (2010) |

[58] | Francesco Ricca, Giovanni Grasso, Mario Alviano, Marco Manna, Vincenzino Lio, Salvatore Iiritano, Nicola Leone, Team-building with answer set programming in the Gioia-Tauro seaport, Theory and Practice of Logic Programming (2012), http://dx.doi.org/10.1017/S147106841100007X, in press. · Zbl 1250.90050 |

[59] | Ross, K.A., Modular stratification and magic sets for Datalog programs with negation, Journal of the ACM, 41, 6, 1216-1266, (1994) · Zbl 0830.68028 |

[60] | Seshadri, Praveen; Hellerstein, Joseph M.; Pirahesh, Hamid; Cliff Leung, T.Y.; Ramakrishnan, Raghu; Srivastava, Divesh; Stuckey, Peter J.; Sudarshan, S., Cost-based optimization for magic: algebra and implementation, (), 435-446 |

[61] | Simons, Patrik; Niemelä, Ilkka; Soininen, Timo, Extending and implementing the stable model semantics, Artificial intelligence, 138, 181-234, (June 2002) |

[62] | Stuckey, Peter J.; Sudarshan, S., Compiling query constraints, (), 56-67 |

[63] | Ullman, Jeffrey D., Principles of database and knowledge-base systems, vol. II, (1989), Computer Science Press |

[64] | A. van Gelder, Negation as failure using tight derivations for general logic programs, in: Minker [52], pp. 1149-1176. · Zbl 0726.68065 |

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.