A Value-propagating Transformation Technique for Datalog Programs Based on Non-Deterministic Constructs

• Autorzy: Potikas P. , Rondogiannis P. , Gergatsoulis M.
• Języki publikacji: EN

Abstrakty

EN

The branching-time transformation is a recent technique for optimizing Chain Datalog programs. In this paper we propose a significant extension of the branching-time transformation which we believe opens up a promising new direction of research in the area of value-propagating Datalog optimizations. More specifically, the proposed transformation can handle more general programs that allow multiple consumptive occurrences of variables in the bodies of clauses. This extension is achieved by using as target language the temporal logic programming formalism DatalognS enriched with choice predicates (a non-deterministic construct that was originally introduced in the area of intensional logic programming). We demonstrate the correctness of the transformation and propose several optimizations that can be applied to the target code. Moreover, we define a bottom-up proof procedure that applies to the target programs and demonstrate that it always terminates (despite the fact that the Herbrand base of these programs is generally infinite).

Słowa kluczowe

EN

Logic Programming (LP); deductive databases; program and query transformations; nondeterministic constructs

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 72, nr 4
• Strony: 485--527
• Opis fizyczny: bibliogr. 30 poz.

Twórcy

autor

Potikas P.

autor

Rondogiannis P.

autor

Gergatsoulis M.

• Department of Archive and Library Sciences, Ionian University, Palea Anaktora, Plateia Eleftherias, 49100 Corfu, Greece,

Bibliografia

• [1] Afrati, F., Gergatsoulis, M., Katzouraki, M.: On Transformations into Linear Database Logic Programs, Perspectives of Systems Informatics (PSI'96), Proceedings (D. Bj􀀀 rner, M. Broy, I. Pottosin, Eds.), Lecture Notes in Computer Science (LNCS) 1181, Springer-Verlag, 1996.
• [2] Afrati, F., Gergatsoulis, M., Toni, F.: Linearizability on Datalog Programs, Theoretical Computer Science, 308(1 - 3), November 2003, 199-226.
• [3] Beeri, C., Ramakrishnan, R.: On the power of magic, The Journal of Logic Programming, 10(1,2,3 & 4), 1991, 255-299.
• [4] Chomicki, J.: Depth-Bounded Bottom-Up evaluation of Logic Programs, The Journal of Logic Programming, 25(1), 1995, 1-31.
• [5] Chomicki, J., Imielinski, T.: Finite representation of Infinite Query Answers, ACM Transaction of Database Systems, 18(2), June 1993, 181-223.
• [6] Gergatsoulis, M., Katzouraki, M.: Unfold/fold transformations for definite clause programs, Programming Language Implementation and Logic Programming (PLILP'94), Proceedings (M. Hermenegildo, J. Penjam, Eds.), Lecture Notes in Computer Science (LNCS) 844, Springer-Verlag, 1994.
• [7] Giannotti, F., Greco, S., Sacc`a, D., Zaniolo, C.: Programming with Non-determinism in Deductive Databases, Annals of Mathematics and Artificial Intelligence, 19(1-2), 1997, 97-125.
• [8] Giannotti, F., Pedreschi, D., Zaniolo, C.: Semantics and Expressive Power of Non-deterministic Constructs in Deductive Databases, Journal of Computer and Systems Sciences, 62(1), 2001, 15-42.
• [9] Greco, S., Sacc`a, D., Zaniolo, C.: Grammars and Automata to Optimize Chain Logic Queries, International Journal on Foundations of Computer Science, 10(3), 1999, 349-372.
• [10] Haddad, R. W., Naughton, J. F.: Counting Methods for Cyclic Relations, Proc. 7th ACM SIGACT-SIGMODSIGART Symposium on Principles of Database Systems, ACM Press, 1988.
• [11] Lloyd, J. W.: Foundations of Logic Programming, 2nd edition, Springer-Verlag, 1987.
• [12] Marchetti-Spaccamella, A., Pelaggi, A., Sacca, D.: Worst-case complexity analysis of methods for logic query implementation, PODS '87: Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, ACM Press, New York, USA, 1987, ISBN 0-89791-223-3.
• [13] Orgun, M. A., Wadge, W. W.: Towards a unified theory of intensional logic programming, The Journal of Logic Programming, 13(4), 1992, 413-440.
• [14] Orgun, M. A., Wadge, W. W.: Extending Temporal Logic Programming with Choice Predicates Nondeterminism, Journal of Logic and Computation, 4(6), 1994, 877-903.
• [15] Pettorossi, A., Proietti, M.: Transformation of Logic Programs, in: Handbook of Logic in Artificial Intelligence and Logic Programming (D. M. Gabbay, C. J. Hogger, J. A. Robinson, Eds.), vol. 5, Oxford University Press, 1997, 697-787.
• [16] Potikas, P., Rondogiannis, P., Gergatsoulis, M.: A Transformation Technique for Datalog Programs based on Non-Deterministic Constructs, Logic Based Program Synthesis and Transformation, 11th Int. Workshop, LOPSTR 2001, Paphos, Cyprus, November 28-30 (A. Pettorossi, Ed.), Lecture Notes in Computer Science (LNCS), Vol. 2372, Springer-Verlag, 2002.
• [17] Ramakrishnan, R., Ullman, J. D.: A Survey of Deductive Database Systems, The Journal of Logic Programming, 23(2), 1995, 125-149.
• [18] Rondogiannis, P., Gergatsoulis, M.: The Intensional Implementation Technique for Chain Datalog Programs, Proc. of the 11th International Symposium on Languages for Intensional Programming (ISLIP'98), May 7-9, Palo Alto, California, USA, 1998.
• [19] Rondogiannis, P., Gergatsoulis, M.: The Branching-Time Transformation Technique for Chain Datalog Programs, Journal of Intelligent Information Systems, 17(1), 2001, 71-94.
• [20] Rondogiannis, P., Gergatsoulis, M., Panayiotopoulos, T.: Branching-time logic programming: The language Cactus and its applications, Computer Languages, 24(3), October 1998, 155-178.
• [21] Rondogiannis, P., Wadge, W. W.: First-order functional languages and intensional logic, Journal of Functional Programming, 7(1), 1997, 73-101.
• [22] Rondogiannis, P., Wadge, W. W.: Higher-Order Functional Languages and Intensional Logic, Journal of Functional Programming, 9(5), 1999, 527-564.
• [23] Sacca, D., Zaniolo, C.: Magic counting methods, SIGMOD '87: Proceedings of the 1987 ACM SIGMOD international conference on Management of data, ACM Press, New York, USA, 1987, ISBN 0-89791-236-5.
• [24] Sacc`a, D., Zaniolo, C.: The generalized counting method for recursive logic queries, Theoretical Computer Science, 4(4), 1988, 187-220.
• [25] Sippu, S., Soisalon-Soininen, E.: An analysis of Magic Sets and Related Optimization Strategies for Logic Queries, Journal of the ACM, 43(6), 1996, 1046-1088.
• [26] Tamaki, H., Sato, T.: Unfold/Fold Transformations of Logic Programs, Proc. of the Second International Conference on Logic Programming (S.-A° . Tarnlund, Ed.), 1984.
• [27] Tsopanakis, K.: Implementation and Evaluation of the Branching-Time Transformation for Chain Datalog Programs, Diploma thesis, Dept. of Informatics and Telecommunications, University of Athens, Greece, 2003.
• [28] Ullman, J. D.: Principles of Database and Knowledge-Base Systems, vol. I & II, Computer Science Press, 1989.
• [29] Wadge, W. W.: Higher-Order Lucid, Proceedings of the Fourth International Symposium on Lucid and Intensional Programming, 1991.
• [30] Yaghi, A.: The intensional implementation technique for functional languages, Ph.D. Thesis, Dept. of Computer Science, University of Warwick, Coventry, UK, 1984.