Generating optimal plans for Boolean expressions

Kastrati, Fisnik ; Moerkotte, Guido

Corporate creators: IEEE
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 > Practical Computer Science III (Moerkotte 1996-)
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.

Metadata export


+ 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