Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 1134))
Included in the following conference series:
140Accesses
Abstract
Normalization is a powerful query independent compilation and optimization technique for complex linear recursions in deductive databases [6, 7, 10, 8, 4]. It transforms a linear recursion into ann-chain recursion which consists ofn chain predicates among which there is no shared variables. Normalization facilitates capturing more bindings and doing quantitative analysis, hence generating efficient query processing plans. However, the existing normalization methods are applicable only tosingle linear recursions. In this paper, we revise the concept of chain andn-chain recursion, and propose a novel method, called counting-based transformation, to transform a generalmultiple linear recursive program to singlen-chain recursion. Based on this method, the existing evaluation methods which are applicable to single linear recursions can be applied also to multiple linear recursions.
Work partially supported by the Hori Information Science Promotion Foundation
This is a preview of subscription content,log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Beeri,C., Ramakrishnan, R.: “On the Power of Magic”Proc. ACM Symp. on Principles of Database Systems (PODS) pp.269–283 (1987)
Du, X., Ishii, N.: Optimizing Linear Recursive Formulas by Detaching Isolated Variables.IEICE Trans. Info. and Syst. Vol.E78-D, No.5, pp.579–585 (1995).
Du, X., Ishii, N.: Reducing the Arity of Predicates by Realigning Some Predicates.Proc. ICLP'95 Joint Workshop on Deductive Databases and Logic Programming. pp.57–69 (1995).
Du,X., Ishii,N.: Normalization of Linear Recursions based on Graph Transformation.Proc. Int'l Conf. CISMOD, LNCS 1009. pp.265–282 (Nov. 1995)
Han,J.: Multi-Way Counting Method,Information Systems, Vol.14, No.3, pp.219–229 (1989)
Han,J.: Compiling General Linear Recursions by Variable Connection Graph Analysis,Comput. Intell. 5, pp.12–31,(1989)
Han,J., Zeng,K.: Automatic Generation of Compiled Forms for Linear Recursions,Information Systems, Vol.17, No.4, pp.299–322 (1992)
Lu,W., Lee,D.L., Han,J.: A Study on the Structure of Linear Recursion,IEEE Trans. KDE, Vol.6, No.5, pp.723–737 (1994)
Wang,K., Zhang, W., Chou,S.C.: Decomposition of Magic RewritingJACM Vol.42, No.2, pp.329–381, March(1995)
Yong,C., Kim,H.J., et al.: Classification and Compilation of Linear Recursive Queries in Deductive Databases.IEEE Trans. KDE, Vol.4, No.1, pp.52–67 (1992)
Author information
Authors and Affiliations
Department of Intelligence and Computer Science, Nagoya Institute of Technology, Nagoya, Japan
Xiaoyong Du, Zhibin Liu & Naohiro Ishii
- Xiaoyong Du
You can also search for this author inPubMed Google Scholar
- Zhibin Liu
You can also search for this author inPubMed Google Scholar
- Naohiro Ishii
You can also search for this author inPubMed Google Scholar
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Du, X., Liu, Z., Ishii, N. (1996). Counting-based normalization for multiple linear recursions. In: Wagner, R.R., Thoma, H. (eds) Database and Expert Systems Applications. DEXA 1996. Lecture Notes in Computer Science, vol 1134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0034710
Download citation
Published:
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-61656-6
Online ISBN:978-3-540-70651-9
eBook Packages:Springer Book Archive
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative