Abstract
The critical problem of finding efficient implementations for recursive queries with bound arguments offers many open challenges of practical and theoretical import. We propose a novel approach that solves this problem for chain queries, i.e., for queries where bindings are propagated from arguments in the head to arguments in the tail of the rules, in a chain-like fashion. The method, called pushdown, is based on the fact that a chain query can have associated a context-free language and a pushdown automaton recognizing this language can be emulated by rewriting the query as a particular fectorized left-linear program. The proposed method generalizes and unifies previous techniques such as the ‘counting’ and ‘right-, left-, mixed-linear’ methods. It also succeeds in reducing many non-linear programs to query-equivalent linear ones.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
F. Afrati, S. Cosmadakis. Expressiveness of Restricted Recursive Queries. In Proc. ACM SIGACT Symp. on Theory of Computing, 1989, pages 113–126.
F. Afrati, C.H. Papadrimitriou. The parallel complexity of simple chain queries. In Proceedings of the Sixth ACM PODS Conf., 1987, pages 210–213.
A.V. Aho, and J.F. Ullmann. The Theory of Parsing Translating and Compiling. Volume 1 & 2, Prentice-Hall, 1972.
F. Bancilhon, D. Mayer, Y. Sagiv, and J.F. Ullman. Magic sets and other strange ways to implement logic programs. In Proc. Fifth ACM PODS, 1986, pages 1–15.
C. Beeri, P. Kanellakis, F. Bancilhon, and R. Ramakrisnhan. Bounds on the Propagation of Selection into Logic Programs, JCSS, Vol. 41, No. 2, 1990, pages 157–180.
C. Beeri and R. Ramakrisnhan. On the power of magic. Journal of Logic Programming, 10 (3 & 4), 1991, pages 255–299.
F. Buccafurri, S. Greco, and E. Spadafora. Implementation of chain queries (in Italian) Proc. 2nd Italian Conference on Advance Database Systems. 1994.
G. Dong, On Datalog Linearization of Chain Queries. In J.D. Ullman, editor, Theoretical Studies in Computer Science, Academic Press, 1991, pages 181–206.
G. Dong, Datalog Expressiveness of Chain Queries: Grammar Tools and Characterization. In Proc. Eleventh ACM PODS Conf., 1992, pages 81–90.
S. Greco and C. Zaniolo, Optimization of linear logic programs using counting methods. In Proc. of the Extending Database Technology, 1992, pages 187–220.
B. Lang. Datalog Automata. In Third Conf. on Data and Knowledge Bases, 1988.
J.W. Lloyd. Foundations of Logic Programming. Springer-Verlag, 2nd ed., 1987.
J. Naughton, R. Ramakrisnhan, Y. Sagiv, and J.F. Ullman. Argument Reduction by Factoring. In Proc. 15th Conf. on Very Large data Bases, 1989, pages 173–182.
J. Naughton, R. Ramakrisnhan, Y. Sagiv, and J.F. Ullman. Efficient evaluation of right-, left-, and multi-linear rules. In Proc. SIGMOD Conf., 1989, pages 235–242.
J.E. Hopcroft, and J.F. Ullmann. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
R. Ramakrisnhan, Y. Sagiv, J.F. Ullman, and M.Y. Vardi. Logical Query Optimization by Proof-Tree Transformation. In JCSS, No. 47, pages 222–248, 1993.
D. Saccà and C. Zaniolo, The generalized counting method of recursive logic queries for databases. Theoretical Computer Science, Vol. 4, No. 4, 1988, pages 187–220.
J.D. Ullmann. Principles of Data and Knowledge-Base Systems. Comp. Sc., 1989.
J.D. Ullmann. The Interface Between Language Theory and Database Theory. In Theoretical Studies in Computer Science (J.D. Ullman, ed.), Academic Press, 1991.
J.D. Ullmann and A. Van Gelder. Parallel Complexity of Logical Query Programs. In Proc. 27th IEEE Symp. on Found. of Computer Science, 1986, pages 438–454.
L. Vielle. Recursive Query processing: The Power of Logic. Theor. Comp. Sc. 1989.
M. Yannakakis. Graph-Theoretic Methods in Database Theory. In Proc. Ninth ACM Symposium on Principles of Database Systems, 1990, pages 230–242.
W. Zang, C.T. Yu and D. Troy. Linearization of Nonlinear Recursive Rules. IEEE Transaction on Software Engineering, Vol. 15, No. 9, 1989, pages 1109–1119.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Greco, S., Saccà, D., Zaniolo, C. (1995). The pushdown method to optimize chain logic programs. In: Fülöp, Z., Gécseg, F. (eds) Automata, Languages and Programming. ICALP 1995. Lecture Notes in Computer Science, vol 944. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60084-1_102
Download citation
DOI: https://doi.org/10.1007/3-540-60084-1_102
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60084-8
Online ISBN: 978-3-540-49425-6
eBook Packages: Springer Book Archive