• Articles • Previous Articles     Next Articles

Magic Sets Revisited

Chen Yangjun;   

  1. Technical Institute of Changsha; Changsha 410073;
  • Online:1997-07-10 Published:1997-07-10

This paper distinguishes among three kinds of linear recursions: canonical strongly linear recursion (CSLR), non-interdependent linear recursion (NILR) and interdependent linear recurstion (ILR) and presents an optimal algorithm for each. First, for the CSLRs, the magic-set method is refined in such a way that queries can be evaluated efficiently. Then, for the NILRS and ILRs, the concept of query dependency graphs is introduced to partition the rules of a program into a set of CSLRs and the computation is elaborated so that the oplimization for CSLRs can also be applied

Key words: software engineering; hierarchical model; program slicing; JAVA; stepwise algorithm; JATO;

[1] Bancilhon F, Ramakrishnan R. An Amateur's introduction to recursive query processing strategies. In Proc. 1986 ACM-SIGMOD Conf.on Management of Data, Washington, D.C., May 1986, pp.16-52.

[2] Han J, Zeng K, Lu T. Normalization of linear recursion in deductive databases. In Proc.of the 9th Int'l Conf.on Data Engineering, Vienna, Austria,April 1993, pp.559-567

[3] Han J, Chen S. Graphic representation of linear recursive rules. International Journal of Intelligence System,, 1992, 7: 317-337. ……….
[1] Xin Tan, Long-Yin Zhang, and Guo-Dong Zhou. Document-Level Neural Machine Translation with Hierarchical Modeling of Global Context [J]. Journal of Computer Science and Technology, 2022, 37(2): 295-308.
[2] Zi-Jie Huang, Zhi-Qing Shao, Gui-Sheng Fan, Hui-Qun Yu, Xing-Guang Yang, and Kang Yang. Community Smell Occurrence Prediction on Multi-Granularity by Developer-Oriented Features and Process Metrics [J]. Journal of Computer Science and Technology, 2022, 37(1): 182-206.
[3] Ying-Zhou Zhang. SymPas: Symbolic Program Slicing [J]. Journal of Computer Science and Technology, 2021, 36(2): 397-418.
[4] Bo Guo, Young-Woo Kwon, Myoungkyu Song. Decomposing Composite Changes for Code Review and Regression Test Selection in Evolving Software [J]. Journal of Computer Science and Technology, 2019, 34(2): 416-436.
[5] Rim Mahouachi. Search-Based Cost-Effective Software Remodularization [J]. Journal of Computer Science and Technology, 2018, 33(6): 1320-1336.
[6] Li Zhang, Jia-Hao Tian, Jing Jiang, Yi-Jun Liu, Meng-Yuan Pu, Tao Yue. Empirical Research in Software Engineering-A Literature Survey [J]. Journal of Computer Science and Technology, 2018, 33(5): 876-899.
[7] Najam Nazar, Yan Hu, He Jiang. Summarizing Software Artifacts: A Literature Review [J]. , 2016, 31(5): 883-909.
[8] Xiangyu Zhang, Dongmei Zhang, Yves Le Traon, Qing Wang, Lu Zhang. Roundtable: Research Opportunities and Challenges for Emerging Software Systems [J]. , 2015, 30(5): 935-941.
[9] Bo Wang, Ying-Fei Xiong, Zhen-Jiang Hu, Hai-Yan Zhao, Wei Zhang, and Hong Mei. Interactive Inconsistency Fixing in Feature Modeling [J]. , 2014, 29(4): 724-736.
[10] Hong Mei (梅宏), Fellow, CCF, and Xuan-Zhe Liu(刘譞哲), Member, CCF. Internetware: An Emerging Software Paradigm for Internet Computing [J]. , 2011, 26(4): 588-599.
[11] Jitender Kumar Chhabra and Varun Gupta. A Survey of Dynamic Software Metrics [J]. , 2010, 25(5): 1016-1029.
[12] David Notkin, Fellow, ACM, IEEE. Software, Software Engineering and Software Engineering Research: Some Unconventional Thoughts [J]. , 2009, 24(2): 189-197.
[13] Pierre Bourque, Serge Oligny, Alain Abran, and Bertrand Fournier. Developing Project Duration Models in Software Engineering [J]. , 2007, 22(3): 348-357 .
[14] Juan J. Cuadrado Gallego, Daniel Rodri guez, Miguel Angel Sicilia, Miguel Garre Rubio and Angel Garci a Crespo. Software Project Effort Estimation Based on Multiple Parametric Models Generated Through Data Clustering [J]. , 2007, 22(3): 371-378 .
[15] Hong Mei, Dong-Gang Cao, and Fu-Qing Yang. Development of Software Engineering: A Research Perspective [J]. , 2006, 21(5): 682-696 .
Full text



[1] Li Renwei;. Soundness and Completeness of Kung s Reasoning Procedure[J]. , 1988, 3(1): 7 -15 .
[2] Xu Jianguo; Gou Yuchai; Lin Zongkai;. HEPAPS:A PCB Automatic Placement System[J]. , 1992, 7(1): 39 -46 .
[3] Wang Yihe; Hong Jiarong;. AECAM:An Extension Matrix Algorithm on a Cellular Automata Machine[J]. , 1992, 7(1): 88 -91 .
[4] Andrew I. Adamatzky;. Identification of Nonstationary Cellular Automata[J]. , 1992, 7(4): 379 -382 .
[5] Xu Qingyun; Wang Nengbin;. Concurrency Control Mechanism of Complex Objects[J]. , 1992, 7(4): 305 -310 .
[6] Ma Jun; Ma Shaohan;. An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph[J]. , 1994, 9(1): 86 -91 .
[7] Zhou Jianqiang; Xie Li; Dai Fei; Sun Zhongxiu;. Adaptive Memory Coherence Algorithms in DSVM[J]. , 1994, 9(4): 365 -372 .
[8] Xu Meihe; Tang Zesheng;. A Boundary Element Method for Simulation of Deformable Objects[J]. , 1996, 11(5): 497 -506 .
[9] Hao Ruibing; Wu Jianping;. A Formal Approach to Protocol Interoperability Testing[J]. , 1998, 13(1): 79 -90 .
[10] Chen Yangjun;. Graph Traversal and Top-Down Evaluation of Logic Queries[J]. , 1998, 13(4): 300 -316 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved