Publication
STOC 1977
Conference paper

Optimal implementation of conjunctive queries in relational data bases

View publication

Abstract

We define the class of conjunctive queries in relational data bases, and the generalized join operator on relations. The generalized join plays an important part in answering conjunctive queries, and it can be implemented using matrix multiplication. It is shown that while answering conjunctive queries is NP complete (general queries are PSPACE complete), one can find an implementation that is within a constant of optimal. The main lemma used to show this is that each conjunctive query has a unique minimal equivalent query (much like minimal finite automata).

Date

04 May 1977

Publication

STOC 1977

Authors

Share