Full Disjunctions: Polynomial-Delay Iterators in Action

摘要

Full disjunctions are an associative extension of the outer-join operator to an arbitrary number of relations. Their main advantage is the ability to maximally combine data from different relations while preserving all the original information. An algorithm for efficiently computing full disjunctions is presented. This algorithm is superior to previous ones in three ways. First, it is the first algorithm that computes a full disjunction with a polynomial delay between tuples. Hence, it can be implemented as an iterator that produces a stream of tuples, which is important in many cases (e.g., pipelined query processing and Web applications). Second, the total runtime is linear in the size of the output. Third, the algorithm employs a novel optimization that divides the relation schemes into biconnected components, uses a separate iterator for each component and applies outerjoins whenever possible. Combining efficiently full disjunctions with standard SQL operators is discussed. Experiments show the superiority of our algorithm over the state of the art.