Cost-Optimal Execution of Boolean DNF Trees with Shared Streams - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2014

Cost-Optimal Execution of Boolean DNF Trees with Shared Streams

Résumé

Several applications process queries expressed as trees of Boolean operators applied to predicates on sensor data streams, e.g., mobile apps and automotive apps. Sensor data must be retrieved from the sensors, which incurs a cost, e.g., an energy expense that depletes the battery of a mobile device, a bandwidth usage. The objective is to determine the order in which predicates should be evaluated so as to shortcut part of the query evaluation and minimize the expected cost. This problem has been studied assuming that each data stream occurs at a single predicate. In this work we study the case in which a data stream occurs in multiple predicates, either when each predicate references a single stream or when a predicate can reference multiple streams. In the single-stream case we give an optimal algorithm for a single-level tree and show that the problem is NP-complete for DNF trees. For DNF trees we show that there exists an optimal predicate evaluation order that is depth-first, which provides a basis for designing a range of heuristics. In the multi-stream case we show that the problem is NP-complete even for single-level trees. As in the single stream case, for DNF trees we show that there exists a depth-first leaf evaluation order that is optimal and we design efficient heuristics.
Fichier principal
Vignette du fichier
RR-8616.pdf (1.32 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01079868 , version 1 (03-11-2014)
hal-01079868 , version 2 (11-12-2014)

Identifiants

  • HAL Id : hal-01079868 , version 1

Citer

Henri Casanova, Lipyeow Lim, Yves Robert, Frédéric Vivien, Dounia Zaidouni. Cost-Optimal Execution of Boolean DNF Trees with Shared Streams. [Research Report] RR-8616, INRIA. 2014. ⟨hal-01079868v1⟩
258 Consultations
162 Téléchargements

Partager

Gmail Facebook X LinkedIn More