Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/35850
Title: | From Relation Algebra to Semi-join Algebra: An Approach to Graph Query Optimization | Authors: | HELLINGS, Jelle Pilachowski, CL Van Gucht, D GYSSENS, Marc Wu, YQ |
Issue Date: | 2021 | Publisher: | OXFORD UNIV PRESS | Source: | Computer journal (Print), 64 (5) , p. 789 -811 | Abstract: | Many graph query languages rely on composition to navigate graphs and select nodes of interest, even though evaluating compositions of relations can be costly. Often, this need for composition can be reduced by rewriting toward queries using semi-joins instead, resulting in a significant reduction of the query evaluation cost. We study techniques to recognize and apply such rewritings. Concretely, we study the relationship between the expressive power of the relation algebras, which heavily rely on composition, and the semi-join algebras, which replace composition in favor of semi-joins. Our main result is that each fragment of the relation algebras where intersection and/or difference is only used on edges (and not on complex compositions) is expressively equivalent to a fragment of the semi-join algebras. This expressive equivalence holds for node queries evaluating to sets of nodes. For practical relevance, we exhibit constructive rules for rewriting relation algebra queries to semijoin algebra queries and prove that they lead to only a well-bounded increase in the number of steps needed to evaluate the rewritten queries. In addition, on sibling-ordered trees, we establish new relationships among the expressive power of Regular XPath, Conditional XPath, FO-logic and the semi-join algebra augmented with restricted fixpoint operators. | Keywords: | graph query optimization;relation algebra;semi join algebra;rewriting;transitive closure;restricted transitive closure;expressiveness | Document URI: | http://hdl.handle.net/1942/35850 | ISSN: | 0010-4620 | e-ISSN: | 1460-2067 | DOI: | 10.1093/comjnl/bxaa031 | ISI #: | 000661492300007 | Rights: | 2017 ACM. This is the author’s version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Proceedings of DBPL 2017, September 1, 2017, https://doi.org/10.1145/3122831.3122833. | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2022 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
cj2020_paper (1).pdf | Peer-reviewed author version | 607.19 kB | Adobe PDF | View/Open |
bxaa031.pdf Restricted Access | Published version | 1.08 MB | Adobe PDF | View/Open Request a copy |
WEB OF SCIENCETM
Citations
2
checked on Apr 15, 2024
Page view(s)
54
checked on Sep 7, 2022
Download(s)
6
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.