Abstract
Grahne et al. have presented a graph algorithm for evaluating a subset of recursive queries. This method consists of two phases. In the first phase, the method transforms a linear binary-chain program into a set of equations over expressions containing predicate symbols. In the second phase, a graph is constructed from the equations and the answers are produced by traversing the relevant paths. A new algorithm is described which requires less time than Grahne's. The key idea of the improvement is to reduce the search space that will be traversed when a query is invoked. Further, the evaluation of cyclic data is speeded up by generating most answers directly in terms of the answers already found and the associated “path information” instead of traversing the corresponding paths as usual. In this way, this algorithm achieves a linear time complexity for both acyclic and most of cyclic data.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Chang, C., On the evaluation of queries containing derived relations in relational database, inAdvances in Data Base Theory, Vo. 1, New York: Plenum Press, 1981.
Chen, Y., Harder, T., Improving RQA/FQI recursive query algorithm, inProceedings ISMM-First Int. Conf. on Information and Knowledge Management, Baltimore, Maryland, Nov. 1992, New York: ACM, 1992, 106–115.
Chen, Y., A bottom-up query evaluation method for stratified databases, inProceedings of 9th International Conference on Data Engineering, Vienna, Austria, April 1993, California: IEEE, 1993, 568–575.
Chen, Y., Harder, T., On the optimal top-down evaluation of recursive queries, inProc. of 5th Int. Conf. on Database and Expert Systems Applications, Greece, Athens, Sept. 1994 (ed. Karagiannis, D.), Berlin: Springer-Verlag, 1994, 47–56.
Chen, Y., Processing of recursive rules in knowledge-based systems—Algorithms for handling recursive rules and negative information and performance measurements, Ph. D. Thesis, Computer Science Department, University of Kaiserslautern, Germany, Feb. 1995.
Chen, Y., On the bottom-up evaluation of recursive queries,Int. J. Intelligent Systems, 1996, 11(10): 807.
Chen, Y., Magic sets and stratified databases,Int. J. Intelligent Systems, 1997, 12(3): 203.
Han, J., Chain-split evaluation in deductive databases,IEEE Trans. Knowledge and Data Engineering, 1995, 7: 261.
Ullman, J. D.,Principles of Databases and Knowledge-base Systems, Rockville: Computer Science Press, 1989.
Shapiro, S., Mckay, D., Inference with recursive rules, inProceedings of the 1st Annual National Conference on Artificial Intelligence (ed. Bazler, R.), California: MIT Press, 1980, 151–156.
Bancilhon, F., Naive evaluation of recursively defined relations,On Knowledge Base Management Systems-Integrating Database and AI Systems (ed. Bancihon, F.), Berlin: Springer-Verlag, 1985, 165–178.
Vieille, L., From QSQ to QoSaQ: Global optimization of recursive queries, inProc. 2nd Int. Conf. on Expert Database System, Charleston (ed. Kerschberg, L.), Virginia: Benjamin Cummings, 1988, 743–748.
Nejdl, W., Recursive strategies for answering recursive queries-The RQA/FQI strategy, inProc. 13th VLDB Conf., Brighton, England (ed. Stocker, P. M.), California: Morgan Kaufmann, 1987, 43–50.
Henschen, L. J., Naqvi, S., On compiling queries in recursive first-order database,J. ACM, 1984, 31(1): 47.
Han, J., Zeng, K., Lu, T., Normalization of linear recursion in deductive databases, inProc. of the 9th International Conf. on Data Engineering, Vienna, Austria, April 1993, California: IEEE, 1993, 559–567.
Han, J., Chen, S., Graphic representation of linear recursive rules,International Journal of Intelligent Systems, 1992, 7: 317.
Han, J., Henschen, L. J., The level-cycle merging method, inProc. of the 1st International Conf. on Deductive and Object-oriented Databases, Kyoto (ed. Kim W.), Berlin: Springer-Verlag, 1989, 113–129.
Bancilhon, F., Maier, D., Sagiv, Y. et al., Magic sets and other strange ways to implement logic programs, inProc 5th ACM Symp. Principles of Database Systems, Cambridge, MA, March 1986 (ed. Zaniolo, C.), California: ACM, 1986, 1–15.
Beeri, C., Ramakrishnan, R., On the power of magic,J. Logic Programming, 1991, November, 10: 255.
Grahne, G., Sippo, S., Soisalon-Soininen, E., Efficient evaluation for a subset of recursive queries, inProceedings of ACM-PODS, California: ACM, 1987, 284–293.
Grahne, G., Sippo, S., Soisalon-Soininen, E., Efficient evaluation for a subset of recursive queries,J. Logic Programming, 1991, 10: 301.
Lloyd, J. W.,Foundations of Logic Programming, Berlin: Springer-Verlag, 1987.
Kanamori, T., Kawamura, T., Abstract interpretation based on OLDT resolution,J. Logic. Programming, 1993, 15: 1.
Tarjan, R., Depth-first search and linear graph algorithm,SIAM J. Comput., 1972, 1(2): 146.
Johnson, D. B., Finding all elementary circuits of a directed graph,SIAM J. Comput., 1975, 4(1): 50.
Garey, M. R., Tarjan, R. E., A linear-time algorithm for finding all feedback vertices,Information Processing Letters, 1978, 7(6): 274.
Aly, H., Ozsoyoglu, Z. M., Synchronized counting method, inProc. of the 5th International Conf. on Data Engineering, Los Angeles, California: IEEE, 1989, 366–373.
Bancilhon, F., Ramakrishnan, R., An amateur's introduction to recursive query processing strategies, inProc. 1986 ACM-SIGMOD Conf. Management of Data, Washington, DC, May 1986, California: ACM, 1986, 16–52.
Wu, C., Henschen, L. J., Answering linear recursive queries in cyclic databases, inProc. of the 1988 International Conf. on Fifth Gen. Computer Systems, Tokyo, California: ACM, 1988, 16–52.
Marchetti-Spaccamela, A., Pelaggi, A., Sacca, D., Worst case complexity analysis of methods for logic query implementation, inProc. of ACM-PODS 87, California: ACM, 1987, 294–301.
Sacca, D., Zaniolo, C., On the implementation of a simple class of logic queries for databases, inProceedings of the 5th ACM SIGMOD-SIGACT Symposium on Principles of Database Systems, California: ACM, 1986, 16–23.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Chen, Y. On the graph traversal method for evaluating linear binary-chain programs. Sci. China Ser. E-Technol. Sci. 42, 225–243 (1999). https://doi.org/10.1007/BF02916768
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02916768