Parallel Algorithms for the Generalized Same Generation Query in Deductive Databases

Arman, Nabil
September 2006
Journal of Digital Information Management;Sep2006, Vol. 4 Issue 3, p192
Academic Journal
The intelligence of traditional database systems can be improved by recursion. Using recursion, relational database systems are extended into knowledgebase systems (deductive database systems). Linear recursion is the most frequently found type of recursion in deductive databases. Deductive databases queries are computationally intensive and lend themselves naturally to parallelization to speed up the solution of such queries. In this paper, parallel algorithms to solve the generalized fully and partially instantiated forms of the same generation query in deductive databases are presented. The algorithms use special data structures, namely, a special matrix that stores paths from source nodes of the graph representing a two-attribute normalized database relation to all nodes reachable from these source nodes, and a reverse matrix that stores paths from any node to all source nodes related to that node.


Related Articles

  • Efficient Mining Algorithms of Finding Frequent Datasets. Lijuan Zhou; Zhang Zhang // Journal of Software (1796217X);Apr2012, Vol. 7 Issue 4, p727 

    This work proposes an efficient mining algorithm to find maximal frequent item sets from relational database. It adapts to large datasets.Itemset is stored in list with special structure. The two main lists called itemset list and Frequent itemset list are created by scanning database once for...

  • Discovery of Functional and Approximate Functional Dependencies in Relational Databases. King, Ronald S.; Legendre, James J. // Journal of Applied Mathematics & Decision Sciences;2003, Vol. 7 Issue 1, p49 

    Presents a study that calculated functional and approximate functional dependencies in relational databases. Basis of the technique used in the study; Application of a levelwise algorithm to the minimal non-trivial functional dependencies; Role of row identifiers in nominally identifying...

  • State evolution for general approximate message passing algorithms, with applications to spatial coupling. Javanmard, Adel; Montanari, Andrea // Information & Inference: A Journal of the IMA;Dec2013, Vol. 2 Issue 2, p115 

    We consider a class of approximated message passing (AMP) algorithms and characterize their high-dimensional behavior in terms of a suitable state evolution recursion. Our proof applies to Gaussian matrices with independent but not necessarily identically distributed entries. It covers—in...

  • Lumping algorithms for computing Google's PageRank and its derivative, with attention to unreferenced nodes. Yu, Qing; Miao, Zhengke; Wu, Gang; Wei, Yimin // Information Retrieval Journal;Dec2012, Vol. 15 Issue 6, p503 

    In this paper, we introduce five type nodes for lumping the Web matrix, and give a unified presentation of some popular lumping methods for PageRank. We show that the PageRank problem can be reduced to solving the PageRank corresponding to the strongly non-dangling and referenced nodes, and the...

  • A new algorithm for inverse of a block period tridiagonal matrix. CHE Yi; XU Zlwng; LEI Xiao-na // Basic Sciences Journal of Textile Universities / Fangzhi Gaoxia;Mar2011, Vol. 24 Issue 1, p15 

    The problem of the inverse of block period tridiagonal matrices are discussed. Using the recursion method , the inversion of higher-order block period tridiagonal matrices are changed into the inversion of low-order block tridiagonal matrices, then a new algorithm for inverse of a block period...

  • Efficient Evaluation of Multiple Linear Recursions. Jiawei Han; Ling Liu // IEEE Transactions on Software Engineering;Dec91, Vol. 17 Issue 12, p1241 

    A multiple linear (ML) recursion is a recursion which consists of multiple linear recursive rules and one or more nonrecursive rules. ML recursions can be classified into two classes: side-coherent and non-side-coherent. This paper studies the efficient evaluation of side-coherent ML recursions,...

  • Application of Apriori Algorithm in Open Experiment. Li Mengshan; Liu Bingxiang; Wu Yan // International Proceedings of Computer Science & Information Tech;2012, Vol. 51, p781 

    In this paper, we introduce the basic ideas of Association Rules and Apriori Algorithm, and analyse the relationship between the booking database of the open experiment and the implementation of Apriori Algorithm. After the pre-processing of the dataset we have accumulated, we apply the Apriori...

  • A test of significance for the index of ordinal variation. Berry, Kenneth J.; Mielke, Jr., Paul W. // Perceptual & Motor Skills;Dec94, Vol. 79 Issue 3, p1291 

    Presents a test of significance for the Index of Ordinal Variation using recursion algorithm; Generation of permutations of objects to categories; Potential applications; Limitation of probability solutions to small sample sizes.

  • Recursive method for inversion of lower triangular matrix. reddy, B. Rami // Journal of Experimental Sciences;Apr2012, Vol. 3 Issue 4, p55 

    Algorithm for finding by recursion, the inverse of a lower triangular matrix of order n is developed, using its last row and the sub matrix obtained by deleting the last row and last column. In these algorithms the hitherto using double suffix notation for the entries of amatrix is replaced by...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics