Efficient algorithms for the instantiated transitive closure queries
IEEE Transactions on Software EngineeringPublished 1 March 1991
Ghassan Z. Qadah, Lawrence J. Henschen, J.J. Kim
Citations26
SJR quartileQ1
SJR score1.45
SNIP2.43
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The study reveals that the relative performance of the algorithms is a strong function of the parameters which characterize the processed TC query and the relation referenced by that query.
Abstract
The performances of several algorithms suitable for processing an important class of recursive queries called the instantiated transitive closure (TC) queries are studied and compared. These algorithms are the wavefront, delta -wavefront, and a generic algorithm called super-TC. During the evaluation of a TC query, the first two algorithms may read a given disk page more than once, whereas super-TC reads the disk page at most once. A comprehensive performance evaluation of these three algorithms using rigorous analytical and simulation models is presented. The study reveals that the relative performance of the algorithms is a strong function of the parameters which characterize the processed TC query and the relation referenced by that query. The superiority of one of the super-TC variants over all of the other presented algorithms is shown.>
Keywords
Computer Science
Journal of the Franklin InstituteAn introduction to probability theory and its application
745 Citations1950S. Charp
ACM Computing SurveysLogic and Databases: A Deductive Approach
739 Citations1984Hervé Gallaire, Jack Minker +1 more
It is shown that logic provides a convenient formalism for studying classical database problems and the representation and manipulation of deduced facts and incomplete information is shown.
ACM SIGMOD RecordAn amateur's introduction to recursive query processing strategies
697 Citations1986François Bancilhon, Raghu Ramakrishnan
Journal of the ACMOn compiling queries in recursive first-order databases
285 Citations1984Lawrence J. Henschen, Shamim A. Naqvi
The solution uses resolution-proof techmques over connection graphs to derive a program of relational database operations that gives all the answers to a query and has a welldefined termmatton condiUon.
ACM Transactions on Database SystemsImplementing a relational database by means of specialzed hardware
254 Citations1979E. Babb
New hardware is described which allows the rapid execution of queries demanding the joining of physically stored relations, with the main feature of the hardware being a special store which can rapidly remember or recall data.
Computer Science Press eBooksFundamentals of Data Structures in Pascal
227 Citations1984Ellis Horowitz, Sartaj Sahni
This has long been the text of choice for sophomore/junior level data structure courses as well as more advanced courses-no other book offers greater depth or thoroughness.
Deductive Question-Answering on Relational Data Bases
153 Citations1978Raymond Reiter
The principal concern of this paper is the design of a retrieval system which combines current techniques for query evaluation on relational data bases with a deductive component in such a way that the interface between the two is both clean and natural.
IEEE Transactions on Software EngineeringAlpha: an extension of relational algebra to express a class of recursive queries
132 Citations1988Rakesh Agrawal
An alpha (α) operator is proposed which when added to relational algebra allows a large class of natural and useful recursive queries to be expressed, and yet has the property of being efficiently implementable.
Minds at UW (University of Wisconsin)Efficient Transitive Closure Algorithms
99 Citations1988Yannis Ioannidis, Raghu Ramakrishnan
Algorithms developed for computing the transitive closure of a directed graph can be adapted to deal with path computations and a broader class of queries based on onesided recursions, indicating that they perform very efficiently in the context of a dish-based database nvironment.
Design and evaluation of algorithms to compute the transitive closure of a database relation
51 Citations1987Hongjun Lü, Krishna Mikkilineni +1 more
This paper adapts Warren's algorithm for use with a binary relation represented as a set of tuples, as in a relational database management system, and compares it to two algorithms based on relational algebra: an iterative algorithm, and an improved version of the iterative algorithms that eliminates unnecessary I/O at the expense of more computation.
IEEE Transactions on Software EngineeringThe join algorithms on a shared-memory multiprocessor database machine
32 Citations1988Ghassan Z. Qadah, Keki B. Irani
This study shows, among other things, that for a given hardware configuration there is not just one overall best performing join algorithm, but rather different algorithms score the best performance, depending on the characteristics of the data participating in the join operation.
Lecture notes in computer scienceThe processing and evaluation of transitive closure queries
30 Citations1988Jiawei Han, Ghassan Z. Qadah +1 more
This study discusses the compilation of recursive rule clusters into formulas containing transitive closure operations and studies three promising algorithms for the processing of transitiveclosure queries, showing that the δ-wavefront algorithm performs consistently better than the wavefront algorithm, and the level-relaxedδ- Wavefront algorithm has high potential of further reducing I/O accessing cost on the databases with clustered derivation paths.
Lecture notes in computer scienceFilter-based join algorithms on uniprocessor and distributed-memory multiprocessor database machines
11 Citations1988Ghassan Z. Qadah
This paper presents several extensions to the centralized and distributed hybrid-hash algorithms based on the usage of one or more bit-vectors as filters, and shows that one of the proposed filter-based algorithms outperforms all of the other ones, including the hybrid- hash algorithm.