|
Generating optimal plans for Boolean expressions
Kastrati, Fisnik
;
Moerkotte, Guido
|
Körperschaften:
|
IEEE
|
|
DOI:
|
https://doi.org/10.1109/ICDE.2018.00095
|
|
URL:
|
https://ieeexplore.ieee.org/document/8509316
|
|
Dokumenttyp:
|
Konferenzveröffentlichung
|
|
Erscheinungsjahr:
|
2018
|
|
Buchtitel:
|
IEEE 34th International Conference on Data Engineering : ICDE 2018 : 16-19 April 2018, Paris, France : proceedings
|
|
Seitenbereich:
|
1013-1024
|
|
Veranstaltungstitel:
|
34th International Conference on Data Engineering (ICDE)
|
|
Veranstaltungsort:
|
Paris, France
|
|
Veranstaltungsdatum:
|
16.-19.04.18
|
|
Ort der Veröffentlichung:
|
Piscataway, NJ
|
|
Verlag:
|
IEEE Computer Soc.
|
|
ISBN:
|
978-1-5386-5521-4 , 978-1-5386-5520-7
|
|
ISSN:
|
2375-026X
|
|
Sprache der Veröffentlichung:
|
Englisch
|
|
Einrichtung:
|
Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Practical Computer Science III (Moerkotte 1996-)
|
|
Fachgebiet:
|
004 Informatik
|
|
Abstract:
|
We present an algorithm that produces optimal plans to evaluate arbitrary Boolean expressions possibly containing conjunctions and disjunctions. The complexity of our algorithm is O(n3n), where n is the number of simple predicates in the Boolean expression. This complexity is far lower than that of Reinwald and Soland's algorithm (O(22(n))). This lower complexity allows us to optimize Boolean expressions with up to 16 predicates in a reasonable time. Further, opposed to many existing approaches, our algorithm fulfills all requirements necessary in the context of main memory database systems. We then use this algorithm to (1) determine the optimization potential inherent in Boolean expressions and (2) evaluate the plan quality of two heuristics proposed in the literature.
|
 | Dieser Eintrag ist Teil der Universitätsbibliographie. |
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
|
