The expressive power and intelligence of traditional database systems can be improved by recursion. Using recursion, relational database systems are extended into knowledge-base systems (deductive database systems). Linear recursion is the most frequently found type of recursion in deductive databases. In this paper, an algorithm to solve the generalized partially instantiated form of the same generation query in deductive databases is presented. The algorithm uses special data structures, namely, a special matrix that stores paths from roots of the graph representing a two-attribute normalized database relation to all nodes reachable from these roots, and a reverse matrix that stores paths from any node to all roots related to that node. Using simulation, this paper also studies the performance of the algorithm and compares that with the standard depth-first search based algorithms.

[1] Banchilon F., Maire D., Sagiv Y., and Ullman J., “Magic Sets and other Strange Ways to Implement Logic Programs,” in Proceedings of 5th ACM Symp. on Principles of Database System, pp. 1-15, 1986.

[2] Elmasri R. and Navathe S., Fundamentals of Database Systems, The Benjamin/Cummings Publishing Company Inc., 2000.

[3] Hopfner M., and Seipel D., “Reasoning about Rules in Deductive Databases,” in Proceedings of 17th Workshop on Logic Programming (WLP'2002), 2002.

[4] Onet A., “An Approach on Semantic Query Optimization for Deductive Databases,” Informatica, vol. 48, no. 1, 2003.

[5] Qadah G., Henschen L., and Kim J., “Efficient Algorithms for the Instantiated Transitive Closure Queries,” IEEE Transactions on Software Engineering, vol. 17, no. 3, 1991.

[6] Suzuki S., Kishi M., and Ibaraki T., “Query Evaluation of the Same Generation Problem with any Variables,” Systms and Computers in Japan, vol. 24, no. 10, 1993.

[7] Toroslu I. and Arman N., “An Efficient Algorithm for the Partially Instantiated Same Generation Query in Deductive Databases,” in Proceedings of the 10th International Symposium on Computer and Information Sciences, Istanbul, Turkey, 1995.

[8] Toroslu I., Qadah G., and Henschen L., “An Efficient Database Transitive Closure Algorithm,” Journal of Applied Intelligence 4, pp. 205-218, 1994.

[9] Ullman J., Principles of Database and Knowledge-Base Systems, Computer Science Press, 1989.

[10] Yahya A., “Duality for Efficient Query Processing in Disjunctive Deductive Databases,” Journal of Automated Reasoning, vol. 28, no. 1, pp. 1-34, 2002.

[11] Young C., Kim H., Henschen L., and Han J., “Classification and Compilation of Linear Recursive Queries in Deductive Databases,” IEEE Transactions on Knowledge and Data Engineering, vol. 4, no. 1, 1992. Nabil Arman received his BSc in computer science with high honors from Yarmouk University in 1990 and an MSc in computer engineering from Middle East Technical University in 1995. He also received an MSc in computer science from The American University of Washington DC in 1997. In May 2000, he received his PhD in information technology/computer science from the School of Information Technology and Engineering, George Mason University, Virginia, USA. He is an assistant professor at Palestine Polytechnic University, Hebron, Palestine, and was on a one-year leave teaching at the Department of Computer Science, Alisra University while part of this work was done. He is interested in database and knowledge-base systems, and algorithms.