Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/39008
Title: | Optimizing Multiset Relational Algebra Queries Using Weak-Equivalent Rewrite Rules | Authors: | HELLINGS, Jelle Wu , Yuqing Van Gucht, Dirk GYSSENS, Marc |
Editors: | Varzinczak, I. | Issue Date: | 2022 | Publisher: | SPRINGER INTERNATIONAL PUBLISHING AG | Source: | Varzinczak, I. (Ed.). FOUNDATIONS OF INFORMATION AND KNOWLEDGE SYSTEMS (FOIKS 2022), SPRINGER INTERNATIONAL PUBLISHING AG, p. 187 -205 | Series/Report: | Lecture Notes in Computer Science | Abstract: | Relational query languages rely heavily on costly join operations to combine tuples from multiple tables into a single resulting tuple. In many cases, the cost of query evaluation can be reduced by manually optimizing (parts of) queries to use cheaper semi-joins instead of joins. Unfortunately, existing database products can only apply such optimizations automatically in rather limited cases. To improve on this situation, we propose a framework for automatic query optimization via weak-equivalent rewrite rules for a multiset relational algebra (that serves as a faithful formalization of core SQL). The weak-equivalent rewrite rules we propose aim at replacing joins by semijoins. To further maximize their usability, these rewrite rules do so by only providing "weak guarantees" on the evaluation results of rewritten queries. We show that, in the context of certain operators, these weak-equivalent rewrite rules still provide strong guarantees on the final evaluation results of the rewritten queries. | Notes: | Hellings, J (corresponding author), McMaster Univ, 1280 Main St W, Hamilton, ON L8S 4L7, Canada. jhellings@mcmaster.ca |
Keywords: | Query Optimization;Relational Algebra;Multiset Semantics;Semi-Joins | Document URI: | http://hdl.handle.net/1942/39008 | ISBN: | 9783031113215 | DOI: | 10.1007/978-3-031-11321-5_11 | ISI #: | 000883026400011 | Rights: | The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG 2022 | Category: | C1 | Type: | Proceedings Paper | Validations: | ecoom 2023 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Foundations of Information and Knowledge Systems.pdf Restricted Access | Published version | 471.61 kB | Adobe PDF | View/Open Request a copy |
foiks2022_2_paper.pdf | Peer-reviewed author version | 435.51 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.