×

zbMATH — the first resource for mathematics

Enhancing magic sets with an application to ontological reasoning. (English) Zbl 1434.68560
Summary: Magic sets are a Datalog to Datalog rewriting technique to optimize query answering. The rewritten program focuses on a portion of the stable model(s) of the input program which is sufficient to answer the given query. However, the rewriting may introduce new recursive definitions, which can involve even negation and aggregations, and may slow down program evaluation. This paper enhances the magic set technique by preventing the creation of (new) recursive definitions in the rewritten program. It turns out that the new version of magic sets is closed for Datalog programs with stratified negation and aggregations, which is very convenient to obtain efficient computation of the stable model of the rewritten program. Moreover, the rewritten program is further optimized by the elimination of subsumed rules and by the efficient handling of the cases where binding propagation is lost. The research was stimulated by a challenge on the exploitation of Datalog/dlv for efficient reasoning on large ontologies. All proposed techniques have been hence implemented in the dlv system, and tested for ontological reasoning, confirming their effectiveness.

MSC:
68T30 Knowledge representation
68N17 Logic programming
Software:
DLV; DLV2; WASP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adrian, W. T., Alviano, M., Calimeri, F., Cuteri, B., Dodaro, C., Faber, W., Fuscà, D., Leone, N., Manna, M., Perri, S., Ricca, F., Veltri, P., and Zangari, J.2018. The ASP system DLV: advancements and applications. KI 32, 2-3, 177-179.
[2] Alviano, M., Amendola, G., Dodaro, C., Leone, N., Maratea, M., and Ricca, F.2019. Evaluation of disjunctive programs in WASP. In M. Balduccini, Y. Lierler, and S. Woltran (Eds.), Logic Programming and Nonmonotonic Reasoning - 15th International Conference, LPNMR 2019, Philadelphia, PA, USA, June 3-7, 2019, Proceedings, Volume 11481 of Lecture Notes in Computer Science, pp. 241-255. Springer. · Zbl 07115978
[3] Alviano, M., Calimeri, F., Dodaro, C., Fuscà, D., Leone, N., Perri, S., Ricca, F., Veltri, P., and Zangari, J.2017. The ASP system DLV2. In M. Balduccini and T. Janhunen (Eds.), Logic Programming and Nonmonotonic Reasoning - 14th International Conference, LPNMR 2017, Espoo, Finland, July 3-6, 2017, Proceedings, Volume 10377 of Lecture Notes in Computer Science, pp. 215-221. Springer. · Zbl 06769663
[4] Alviano, M. and Dodaro, C.2016. Anytime answer set optimization via unsatisfiable core shrinking. Theory and Practice of Logic Programming 16, 5-6, 533-551. · Zbl 1379.68033
[5] Alviano, M. and Dodaro, C.2017. Unsatisfiable core shrinking for anytime answer set optimization. In C. Sierra (Ed.), Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pp. 4781-4785. ijcai.org. · Zbl 1379.68033
[6] Alviano, M., Dodaro, C., Järvisalo, M., Maratea, M., and Previti, A.2018. Cautious reasoning in ASP via minimal models and unsatisfiable cores. Theory and Practice of Logic Programming 18, 3-4, 319-336. · Zbl 1451.68267
[7] Alviano, M., Dodaro, C., and Maratea, M.2018. Shared aggregate sets in answer set programming. Theory and Practice of Logic Programming 18, 3-4, 301-318. · Zbl 1451.68062
[8] Alviano, M., Dodaro, C., and Ricca, F.2014. Anytime computation of cautious consequences in answer set programming. Theory and Practice of Logic Programming 14, 4-5, 755-770. · Zbl 1307.68012
[9] Alviano, M. and Faber, W.2011. Dynamic magic sets and super-coherent answer set programs. AI Commun. 24, 2, 125-145. · Zbl 1215.68211
[10] Alviano, M. and Faber, W.2018. Aggregates in answer set programming. KI 32, 2-3, 119-124.
[11] Alviano, M., Faber, W., and Gebser, M.2015. Rewriting recursive aggregates in answer set programming: back to monotonicity. Theory and Practice of Logic Programming 15, 4-5, 559-573. · Zbl 1379.68034
[12] Alviano, M., Faber, W., and Gebser, M.2016. From non-convex aggregates to monotone aggregates in ASP. In S. Kambhampati (Ed.), Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, pp. 4100-4194. IJCAI/AAAI Press.
[13] Alviano, M., Faber, W., Greco, G., and Leone, N.2012. Magic sets for disjunctive datalog programs. Artif. Intell. 187, 156-192. · Zbl 1251.68051
[14] Alviano, M., Faber, W., and Woltran, S.2014. Complexity of super-coherence problems in ASP. Theory and Practice of Logic Programming 14, 3, 339-361. · Zbl 1312.68034
[15] Alviano, M., Greco, G., and Leone, N.2011. Dynamic magic sets for programs with monotone recursive aggregates. In J. P. Delgrande and W. Faber (Eds.), Logic Programming and Nonmonotonic Reasoning - 11th International Conference, LPNMR 2011, Vancouver, Canada, May 16-19, 2011. Proceedings, Volume 6645 of Lecture Notes in Computer Science, pp. 148-160. Springer. · Zbl 1239.68019
[16] Balbin, I., Port, G. S., Ramamohanarao, K., and Meenakshi, K.1991. Efficient bottom-up computation of queries on stratified databases. J. Log. Program. 11, 3&4, 295-344. · Zbl 0764.68012
[17] Bancilhon, F., Maier, D., Sagiv, Y., and Ullman, J. D.1986. Magic sets and other strange ways to implement logic programs. In A. Silberschatz (Ed.), Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 24-26, 1986, Cambridge, Massachusetts, USA, pp. 1-15. ACM.
[18] Bartholomew, M., Lee, J., and Meng, Y.2011. First-order semantics of aggregates in answer set programming via modified circumscription. In Logical Formalizations of Commonsense Reasoning, Papers from the 2011 AAAI Spring Symposium, Technical Report SS-11-06, Stanford, California, USA, March 21-23, 2011. AAAI.
[19] Beeri, C. and Ramakrishnan, R.1991. On the power of magic. J. Log. Program. 10, 3&4, 255-299. · Zbl 0722.68018
[20] Behrend, A.2003. Soft stratification for magic set based query evaluation in deductive databases. In F. Neven, C. Beeri, and T. Milo (Eds.), Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 9-12, 2003, San Diego, CA, USA, pp. 102-110. ACM.
[21] Codish, M. and Demoen, B.1995. Analyzing logic programs using “PROP”-ositional logic programs and a magic wand. J. Log. Program. 25, 3, 249-274. · Zbl 0871.68049
[22] Dodaro, C., Alviano, M., Faber, W., Leone, N., Ricca, F., and Sirianni, M.2011. The birth of a WASP: preliminary report on a new ASP solver. In F. Fioravanti (Ed.), Proceedings of the 26th Italian Conference on Computational Logic, Pescara, Italy, August 31 - September 2, 2011, Volume 810 of CEUR Workshop Proceedings, pp. 99-113. CEUR-WS.org.
[23] Eiter, T., Ortiz, M., Simkus, M., Tran, T., and Xiao, G.2012. Query rewriting for horn-shiq plus rules. In J. Hoffmann and B. Selman (Eds.), Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada. AAAI Press.
[24] Faber, W., Pfeifer, G., and Leone, N.2011. Semantics and complexity of recursive aggregates in answer set programming. Artif. Intell. 175, 1, 278-298. · Zbl 1216.68263
[25] Ferraris, P.2011. Logic programs with propositional connectives and aggregates. ACM Trans. Comput. Log. 12,4, 25. · Zbl 1351.68053
[26] Furfaro, F., Greco, S., Ganguly, S., and Zaniolo, C.2002. Pushing extrema aggregates to optimize logic queries. Inf. Syst. 27, 5, 321-343. · Zbl 1006.68669
[27] Gebser, M., Kaminski, R., Kaufmann, B., and Schaub, T.2009. On the implementation of weight constraint rules in conflict-driven ASP solvers. In P. M. Hill and D. S. Warren (Eds.), Logic Programming, 25th International Conference, ICLP 2009, Pasadena, CA, USA, July 14-17, 2009. Proceedings, Volume 5649 of Lecture Notes in Computer Science, pp. 250-264. Springer. · Zbl 1251.68059
[28] Gelder, A. V.1989. Negation as failure using tight derivations for general logic programs. J. Log. Program. 6, 1&2, 109-133. · Zbl 0668.68108
[29] Gelder, A. V., Ross, K. A., and Schlipf, J. S.1991. The well-founded semantics for general logic programs. J. ACM 38, 3, 620-650. · Zbl 0799.68045
[30] Gelfond, M. and Lifschitz, V.1991. Classical negation in logic programs and disjunctive databases. New Generation Comput. 9, 3/4, 365-386. · Zbl 0735.68012
[31] Gelfond, M. and Zhang, Y.2014. Vicious circle principle and logic programs with aggregates. Theory and Practice of Logic Programming 14, 4-5, 587-601. · Zbl 1309.68032
[32] Greco, G., Greco, S., Trubitsyna, I., and Zumpano, E.2005. Optimization of bound disjunctive queries with constraints. Theory and Practice of Logic Programming5, 6, 713-745. · Zbl 1085.68019
[33] Greco, S.2003. Binding propagation techniques for the optimization of bound disjunctive queries. IEEE Trans. Knowl. Data Eng. 15,2, 368-385.
[34] Kemp, D. B., Srivastava, D., and Stuckey, P. J.1995. Bottom-up evaluation and query optimization of well-founded models. Theor. Comput. Sci. 146, 1&2, 145-184. · Zbl 0873.68032
[35] Kerisit, J. and Pugin, J.1988. Efficient query answering on stratified databases. In FGCS, pp. 719-726.
[36] Leone, N., Allocca, C., Alviano, M., Calimeri, F., Civili, C., Costabile, R., Cuteri, B., Fiorentino, A., Fuscà, D., Germano, S., Laboccetta, G., Manna, M., Perri, S., Reale, K., Ricca, F., Veltri, P., and Zangari, J.2019. Large scale DLV: preliminary results. In A. Casagrande and E. G. Omodeo (Eds.), Proceedings of the 34th Italian Conference on Computational Logic, Trieste, Italy, June 19-21, 2019., Volume 2396 of CEUR Workshop Proceedings. CEUR-WS.org. · Zbl 07115983
[37] Leone, N., Allocca, C., Alviano, M., Calimeri, F., Civili, C., Costabile, R., Fiorentino, A., Fuscà, D., Germano, S., Laboccetta, G., Cuteri, B., Manna, M., Perri, S., Reale, K., Ricca, F., Veltri, P., and Zangari, J.2019. Enhancing DLV for large-scale reasoning. In M. Balduccini, Y. Lierler, and S. Woltran (Eds.), Logic Programming and Nonmonotonic Reasoning - 15th International Conference, LPNMR 2019, Philadelphia, PA, USA, June 3-7, 2019, Proceedings, Volume 11481 of Lecture Notes in Computer Science, pp. 312-325. Springer. · Zbl 07115983
[38] Liu, L., Pontelli, E., Son, T. C., and Truszczynski, M.2010. Logic programs with abstract constraint atoms: The role of computations. Artif. Intell. 174, 3-4, 295-315. · Zbl 1207.68119
[39] Mumick, I. S., Pirahesh, H., and Ramakrishnan, R.1990. The magic of duplicates and aggregates. In D. McLeod, R. Sacks-Davis, and H. Schek (Eds.), 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings., pp. 264-277. Morgan Kaufmann.
[40] Pelov, N., Denecker, M., and Bruynooghe, M.2007. Well-founded and stable semantics of logic programs with aggregates. Theory and Practice of Logic Programming 7, 3, 301-353. · Zbl 1111.68070
[41] Przymusinski, T. C.1989. On the declarative and procedural semantics of logic programs. J. Autom. Reasoning 5, 2, 167-205. · Zbl 0681.68109
[42] Ross, K. A.1994. Modular stratification and magic sets for datalog programs with negation. J. ACM 41, 6, 1216-1266. · Zbl 0830.68028
[43] Simons, P., Niemelä, I., and Soininen, T.2002. Extending and implementing the stable model semantics. Artif. Intell. 138, 1-2, 181-234. · Zbl 0995.68021
[44] Stuckey, P. J. and Sudarshan, S.1994. Compiling query constraints. In V. Vianu (Ed.), Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota, USA, pp. 56-67. ACM Press.
[45] Whaley, J., Avots, D., Carbin, M., and Lam, M. S.2005. Using datalog with binary decision diagrams for program analysis. In K. Yi (Ed.), Programming Languages and Systems, Third Asian Symposium, APLAS 2005, Tsukuba, Japan, November 2-5, 2005, Proceedings, Volume 3780 of Lecture Notes in Computer Science, pp. 97-118. Springer. · Zbl 1159.68386
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.