HP Labs Technical Reports

Optimization of Real Conjunctive Queries

Chaudhuri, Surajit; Vardi, Moshe Y.

HPL-93-26

Keyword(s):

Abstract: The optimization problem for conjunctive queries has been studied extensively. Unfortunately, this research almost invariably assumes set-theoretic semantics (i.e., duplicates are eliminated). In contrast, SQL queries have bag-theoretic semantics (i.e., in general duplicates are not eliminated). In this paper we study the optimization problems for conjunctive queries under bag-theoretic semantics. We show that optimization techniques from the set-theoretic setting do not carry over to the bag-theoretic setting.

Back to Index