Conjunctive queries implementation

May 4, 1977We define the class of conjunctive queries in relational data bases, and the generalized join operator on relations.ABSTRACTReferencesIndex Terms

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.