SET PREDICATES IN SQL: ENABLING SET-LEVEL COMPARISONS USING AGGREGATE FUNCTION AND BITMAP INDEX-BASED APPROACHES FOR DYNAMICALLY FORMED GROUPS

This abstract proposed to extend SQL with set predicates for an important class of analytical queries, which otherwise would be difficult to write and optimize. It designed two query evaluation approaches for set predicates, including an aggregate function-based approach and a bitmap index-based approach. Aggregate function-based approach processes set predicates in a way similar to processing conventional aggregate functions. Given a query with set predicates, instead of decomposing the query into multiple sub queries, this approach only needs one pass of table scan. Bitmap index-based approach processes set predicates by using bitmap indices on individual attributes. It is efficient because it can focus on only the tuples from those groups that satisfy query conditions and only the bitmaps for relevant columns. It developed a histogram- based probabilistic method to estimate the selectivity of a set predicate, for optimizing queries with multiple predicates.  The experiments verified its accuracy and effectiveness in optimizing queries.