Generating optimal plans for Boolean expressions


Kastrati, Fisnik ; Moerkotte, Guido


Corporate creators: IEEE
DOI: https://doi.org/10.1109/ICDE.2018.00095
URL: https://ieeexplore.ieee.org/document/8509316
Document Type: Conference or workshop publication
Year of publication: 2018
Book title: IEEE 34th International Conference on Data Engineering : ICDE 2018 : 16-19 April 2018, Paris, France : proceedings
Page range: 1013-1024
Conference title: 34th International Conference on Data Engineering (ICDE)
Location of the conference venue: Paris, France
Date of the conference: 16.-19.04.18
Place of publication: Piscataway, NJ
Publishing house: IEEE Computer Soc.
ISBN: 978-1-5386-5521-4 , 978-1-5386-5520-7
ISSN: 2375-026X
Publication language: English
Institution: School of Business Informatics and Mathematics > Praktische Informatik III (Moerkotte)
Subject: 004 Computer science, internet
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.




+ Citation Example and Export

Kastrati, Fisnik ; Moerkotte, Guido IEEE Generating optimal plans for Boolean expressions. 1013-1024 In: IEEE 34th International Conference on Data Engineering : ICDE 2018 : 16-19 April 2018, Paris, France : proceedings (2018) Piscataway, NJ 34th International Conference on Data Engineering (ICDE) (Paris, France) [Conference or workshop publication]


+ Search Authors in

+ Page Views

Hits per month over past year

Detailed information



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item