6533b7d3fe1ef96bd126133c
RESEARCH PRODUCT
A generalized transitive closure for relational queries
Seppo SippuEljas Soisalon-soininensubject
Transitive relationSelection (relational algebra)Closure (topology)Transitive closure020207 software engineering02 engineering and technologyTransitive setRelational algebraTransitive reductionAlgebraTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESOperator (computer programming)TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS020204 information systems0202 electrical engineering electronic engineering information engineeringMathematicsdescription
We augment relational algebra with a generalized transitive closure operator that allows for the efficient evaluation of a subclass of recursive queries. The operator is based on a composition operator which is as general as possible when the operator is required to be associative and when only relational algebra operators are used in its definition. The closure of such a composition can be computed using the well-known efficient algorithms designed for the computation of the usual transitive closure. Besides the case in which complete materialization of recursive relations are required, our strategy also yields an efficient solution in the case in which a selection is applied to the closure.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1988-01-01 | Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems - PODS '88 |