From Relation Algebra to Semi-join Algebra: An Approach to Graph Query Optimization
- 9 May 2020
- journal article
- research article
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 64 (5), 789-811
- https://doi.org/10.1093/comjnl/bxaa031
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 semi-join 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
Funding Information
- National Science Foundation (NSF 1438990)
This publication has 45 references indexed in Scilit:
- Foundations of Modern Query Languages for Graph DatabasesACM Computing Surveys, 2017
- Querying graph databases with XPathPublished by Association for Computing Machinery (ACM) ,2013
- XPath leashedACM Computing Surveys, 2009
- Navigational XPathACM SIGMOD Record, 2007
- The expressivity of XPath with transitive closurePublished by Association for Computing Machinery (ACM) ,2006
- Conditional XPathACM Transactions on Database Systems, 2005
- Semantic characterizations of navigational XPathACM SIGMOD Record, 2005
- Structural properties of XPath fragmentsTheoretical Computer Science, 2005
- A graphical query language supporting recursionPublished by Association for Computing Machinery (ACM) ,1987
- On the calculus of relationsThe Journal of Symbolic Logic, 1941