Matching and Evaluation of Disjunctive Predicates for Data Stream Sharing

Traditional query optimization largely neglects the handling of disjunctive predicates. However, new and evolving applications and optimization techniques, e.g., in the domain of data stream management systems (DSMSs), make the treatment of disjunctive predicates a necessity.\\ In this paper, we introduce and discuss methods for matching and evaluating disjunctive predicates in the context of data stream sharing in a DSMS. Nevertheless, the presented techniques are generic and can be applied to other domains as well. Data stream sharing uses one data stream for satisfying multiple similar continuous queries in a network. Sharing an existing stream for answering a new query requires, among other things, the selection predicates of the new query to be matched with the predicates describing the contents of the shared stream. Predicate matching is a combination of predicate implication checking and predicate relaxation. If no match is found, sharing can be enabled by widening the stream, e.g., by relaxing a selection predicate, which can introduce additional disjunctions in the stream predicates. We propose heuristics as well as an exact algorithm for solving the predicate matching problem and discuss the use of multi-dimensional indexing for speeding up the matching and evaluation processes for interval-based disjunctive predicates. To the best of our knowledge, this is the first work to investigate the use of multi-dimensional indexes for matching and continuously evaluating disjunctive predicates. An extensive experimental study compares and evaluates the presented algorithms and reveals a performance gain of several orders of magnitude for predicate matching and evaluation through multi-dimensional indexing.     «

Traditional query optimization largely neglects the handling of disjunctive predicates. However, new and evolving applications and optimization techniques, e.g., in the domain of data stream management systems (DSMSs), make the treatment of disjunctive predicates a necessity.\\ In this paper, we introduce and discuss methods for matching and evaluating disjunctive predicates in the context of data stream sharing in a DSMS. Nevertheless, the presented techniques are generic and can be applied to...     »