TRANSFORMATION FOR GENERALIZED LEFT-LINEAR RECURSIONS: ALGORITHM AND ITS CORRECTNESS
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [1]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    This paper presents an algorithm which transform a generalized left-linear recursion into more efficient rules,and shows the correctness of the given algorithm. A generalized left-linear recursion contains one or more IDB predicates and its definition is essentially generalized from that of left-linear recursions. As the algorithm for the evaluation of left - linear recursions, the algorithm we present here follows the magic-sets paradigm of a rewriting phase followed by semi -naive bottom-up evaluation. The efficinecy of the transformed rules is also discussed in this paper.

    Reference
    l Bancilhon F.Ramakrishnan R.An amateur'S introduction to reeursive query processing strategies.In Proc.of the 1986 ACM SIGMOD Intl.Conf.on Management of Data,Washinghton:1986,ACM Press,1986:16—52. 2 Bancilhon F,Maier D,Sagiv Y et al.Magic sets and other strange ways to implement logic programs.In Proe.of the 5th ACM SIGACT—SIGMOD Sympo.on Principles of Database systems,Cambridge:1986,ACM Press, 1986;1—15. 3 Beery C,Ramakrishnan R.On the power of magic.In Proc.of the 6th ACM SIGACT—SIGMOD Sympo.on Principles of Database systems,ACM Press,1987:269—283. 4 UNman J D.Principles of database and knowledge—Base systems,Vol.II,Computer Science Press,1989. 5 Naughton J F,Ramakrishnan R,Sagiv Y et al.Efficient evaluation of right一,left一,and multi—linear rules.In Proc.of the 1989 ACM SIGMOD Intl.Conf.on Management of Data,ACM Press,1989:235—242. 6 Morris K,Ullman J D,Van Gelder A.Design overview of the NAIL! system.In Proc.of the Third Intl.Conf.on Logic Programming,ACM Pressl986:554—568. 7 Naqvi S A,Tsur S.A logic language for data and knowledge bases.Computer Science Press,1988. 8 范明.拓广的右线性递归变换算法及其正确性.计算机学报,1992;15(12):906—912.Abstract This paper presents an algorithm which transform a generalized left—linearrecursion into more efficient rules,and shows the correctness of the given algorithm.Ageneralized left—linear recursion contains one or more IDB predicates and its definition isessentially generalized from that of left—linear recursions.As the algorithm for the evaluation of left—linear recursions,the algorithm we present here follows the magic—setsparadigm of a rewriting phase followed by semi—naive bottom—up evaluation.The ef-ficinecy of the transformed rules iS also discussed in this paper.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

范明.拓广的左线性递仅变换算法及其正确性.软件学报,1994,5(1):56-61

Copy
Share
Article Metrics
  • Abstract:3831
  • PDF: 4576
  • HTML: 0
  • Cited by: 0
History
  • Received:March 15,1991
  • Revised:June 25,1991
You are the first2045202Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063