Algebraic optimization of recursive queries

Maurice A.W. Houtsma, Peter M.G. Apers

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
149 Downloads (Pure)


Over the past few years, much attention has been paid to deductive databases. They offer a logic-based interface, and allow formulation of complex recursive queries. However, they do not offer appropriate update facilities, and do not support existing applications. To overcome these problems an SQL-like interface is required besides a logic-based interface. In the PRISMA project we have developed a tightly-coupled distributed database, on a multiprocessor machine, with two user interfaces: SQL and PRISMAlog. Query optimization is localized in one component: the relational query optimizer. Therefore, we have defined an eXtended Relational Algebra that allows recursive query formulation and can also be used for expressing executable schedules, and we have developed algebraic optimization strategies for recursive queries. In this paper we describe an optimization strategy that rewrites regular (in the context of formal grammars) mutually recursive queries into standard Relational Algebra and transitive closure operations. We also describe how to push selections into the resulting transitive closure operations. The reason we focus on algebraic optimization is that, in our opinion, the new generation of advanced database systems will be built starting from existing state-of-the-art relational technology, instead of building a completely new class of systems.
Original languageEnglish
Pages (from-to)299-325
Number of pages27
JournalData & knowledge engineering
Issue number4
Publication statusPublished - Jul 1992


  • Transitive closure
  • Algebraic optimization
  • Recursive queries
  • Relational databases
  • Deductive databases


Dive into the research topics of 'Algebraic optimization of recursive queries'. Together they form a unique fingerprint.

Cite this