{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T19:37:59Z","timestamp":1773344279684,"version":"3.50.1"},"reference-count":63,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2020,5,9]],"date-time":"2020-05-09T00:00:00Z","timestamp":1588982400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["NSF 1438990"],"award-info":[{"award-number":["NSF 1438990"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,5,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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.<\/jats:p>","DOI":"10.1093\/comjnl\/bxaa031","type":"journal-article","created":{"date-parts":[[2020,3,12]],"date-time":"2020-03-12T20:22:16Z","timestamp":1584044536000},"page":"789-811","source":"Crossref","is-referenced-by-count":4,"title":["From Relation Algebra to Semi-join Algebra: An Approach to Graph Query Optimization"],"prefix":"10.1093","volume":"64","author":[{"given":"Jelle","family":"Hellings","sequence":"first","affiliation":[{"name":"Exploratory Systems Lab, Department of Computer Science, University of California, Davis, CA 95616-8562, USA, and Hasselt University, Faculty of Sciences, Martelarenlaan 42, 3500 Hasselt, Belgium"}]},{"given":"Catherine L","family":"Pilachowski","sequence":"additional","affiliation":[{"name":"Indiana University, Luddy School of Informatics, Computing and Engineering, 919 E 10th Street, Bloomington, IN 47408, USA"}]},{"given":"Dirk","family":"Van Gucht","sequence":"additional","affiliation":[{"name":"Indiana University, Luddy School of Informatics, Computing and Engineering, 919 E 10th Street, Bloomington, IN 47408, USA"}]},{"given":"Marc","family":"Gyssens","sequence":"additional","affiliation":[{"name":"Hasselt University, Faculty of Sciences, Data Science Institute, Martelarenlaan 42, 3500 Hasselt, Belgium"}]},{"given":"Yuqing","family":"Wu","sequence":"additional","affiliation":[{"name":"Pomona College, 185 E 6th Street, Claremont, CA 91711, USA"}]}],"member":"286","published-online":{"date-parts":[[2020,5,9]]},"reference":[{"key":"2021052900092713400_ref1","doi-asserted-by":"crossref","first-page":"68:1","DOI":"10.1145\/3104031","article-title":"Foundations of modern query languages for graph databases","volume":"50","author":"Angles","year":"2017","journal-title":"ACM Comput. Surv."},{"key":"2021052900092713400_ref2","article-title":"SPARQL 1.1 Query Language","volume-title":"W3C Recommendation","author":"Harris","year":"2013"},{"key":"2021052900092713400_ref3","article-title":"The Neo4j Cypher Manual v3.5","author":"Neo4j Team","year":"2019"},{"key":"2021052900092713400_ref4","article-title":"Apache TinkerPop Documentation v3.4.4","author":"Apache TinkerPop","year":"2019"},{"key":"2021052900092713400_ref5","doi-asserted-by":"crossref","first-page":"73","DOI":"10.2307\/2268577","article-title":"On the calculus of relations","volume":"6","author":"Tarski","year":"1941","journal-title":"J. Symb. Log."},{"key":"2021052900092713400_ref6","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.tcs.2004.10.030","article-title":"Structural properties of XPath fragments","volume":"336","author":"Benedikt","year":"2005","journal-title":"Theoret. Comput. Sci."},{"key":"2021052900092713400_ref7","doi-asserted-by":"crossref","first-page":"3:1","DOI":"10.1145\/1456650.1456653","article-title":"XPath leashed","volume":"41","author":"Benedikt","year":"2009","journal-title":"ACM Comput. Surv."},{"key":"2021052900092713400_ref8","article-title":"XML Path Language (XPath) v1.0","volume-title":"W3C Recommendation","author":"Clark","year":"1999"},{"key":"2021052900092713400_ref9","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/1114244.1114247","article-title":"Conditional XPath","volume":"30","author":"Marx","year":"2005","journal-title":"ACM Trans. Database Syst."},{"key":"2021052900092713400_ref10","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1145\/1083784.1083792","article-title":"Semantic characterizations of navigational XPath","volume":"34","author":"Marx","year":"2005","journal-title":"SIGMOD Record"},{"key":"2021052900092713400_ref11","doi-asserted-by":"crossref","DOI":"10.1145\/1142351.1142398","article-title":"The expressivity of XPath with transitive closure","author":"ten Cate","year":"2006"},{"key":"2021052900092713400_ref12","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/1328854.1328858","article-title":"Navigational XPath: Calculus and algebra","volume":"36","author":"ten Cate","year":"2007","journal-title":"SIGMOD Record"},{"key":"2021052900092713400_ref13","doi-asserted-by":"crossref","DOI":"10.1145\/2448496.2448513","article-title":"Querying graph databases with XPath","author":"Libkin","year":"2013"},{"key":"2021052900092713400_ref14","doi-asserted-by":"crossref","DOI":"10.1145\/38713.38749","article-title":"A graphical query language supporting recursion","author":"Cruz","year":"1987"},{"key":"2021052900092713400_ref15","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1016\/j.ins.2014.11.031","article-title":"Relative expressive power of navigational querying on graphs","volume":"298","author":"Fletcher","year":"2015","journal-title":"Inf. Sci."},{"key":"2021052900092713400_ref16","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/s10472-013-9346-x","article-title":"The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs","volume":"73","author":"Fletcher","year":"2015","journal-title":"Ann. Math. Artif. Intell."},{"key":"2021052900092713400_ref17","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/s10817-006-9062-x","article-title":"The calculus of relations as a foundation for mathematics","volume":"37","author":"Givant","year":"2006","journal-title":"J. Autom. Reason."},{"key":"2021052900092713400_ref18","doi-asserted-by":"crossref","DOI":"10.1145\/2815072.2815081","article-title":"Relative expressive power of downward fragments of navigational query languages on trees and chains","author":"Hellings","year":"2015"},{"key":"2021052900092713400_ref19","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1093\/jigpal\/jzv028","article-title":"Relative expressive power of navigational querying on graphs using transitive closure","volume":"23","author":"Surinx","year":"2015","journal-title":"Log. J. IGPL"},{"key":"2021052900092713400_ref20","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1016\/j.jcss.2006.10.011","article-title":"On the complexity of division and set joins in the relational algebra","volume":"73","author":"Leinders","year":"2007","journal-title":"J. Comput. Syst. Sci."},{"key":"2021052900092713400_ref21","doi-asserted-by":"crossref","DOI":"10.1145\/362384.362685","article-title":"A relational model of data for large shared data banks","volume-title":"Communications of the ACM, 13","author":"Codd","year":"1970"},{"key":"2021052900092713400_ref22","article-title":"The semijoin algebra","volume-title":"Hasselt University and Transnational University of Limburg","author":"Leinders","year":"2008"},{"key":"2021052900092713400_ref23","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.ipl.2004.03.011","article-title":"On the expressive power of semijoin queries","volume":"91","author":"Leinders","year":"2004","journal-title":"Inform. Process. Lett."},{"key":"2021052900092713400_ref24","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/s10849-005-5789-8","article-title":"The semijoin algebra and the guarded fragment","volume":"14","author":"Leinders","year":"2005","journal-title":"J. Log. Lang. Inf."},{"key":"2021052900092713400_ref25","article-title":"Multirelations: Semantice and languages","author":"Klausner","year":"1985"},{"key":"2021052900092713400_ref26","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/322234.322238","article-title":"Using semi-joins to solve relational queries","volume":"28","author":"Bernstein","year":"1981","journal-title":"J. ACM"},{"key":"2021052900092713400_ref27","volume-title":"Principles of Database and Knowledge-Base Systems: Volume II: The New Technologies","author":"Ullman","year":"1990"},{"key":"2021052900092713400_ref28","article-title":"Algorithms for acyclic database schemes","author":"Yannakakis","year":"1981"},{"key":"2021052900092713400_ref29","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1145\/235968.233360","article-title":"Cost-based optimization for magic: Algebra and implementation","volume":"25","author":"Seshadri","year":"1996","journal-title":"SIGMOD Record"},{"key":"2021052900092713400_ref30","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/S0304-3975(98)00308-9","article-title":"On logics with two variables","volume":"224","author":"Gr\u00e4del","year":"1999","journal-title":"Theoret. Comput. Sci."},{"key":"2021052900092713400_ref31","doi-asserted-by":"crossref","first-page":"345","DOI":"10.2307\/420954","article-title":"Finite variable logics in descriptive complexity theory","volume":"4","author":"Grohe","year":"1998","journal-title":"Bull. Symb. Log."},{"key":"2021052900092713400_ref32","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"Libkin","year":"2004"},{"key":"2021052900092713400_ref33","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/s001530050127","article-title":"Bounded variable logics: Two, three, and more","volume":"38","author":"Otto","year":"1999","journal-title":"Arch. Math. Logic"},{"key":"2021052900092713400_ref34","doi-asserted-by":"crossref","first-page":"147","DOI":"10.2307\/2275602","article-title":"The expressive power of fixed-point logic with counting","volume":"61","author":"Otto","year":"1996","journal-title":"J. Symb. Log."},{"key":"2021052900092713400_ref35","doi-asserted-by":"crossref","DOI":"10.1145\/1938551.1938578","article-title":"Relative expressive power of navigational querying on graphs","author":"Fletcher","year":"2011"},{"key":"2021052900092713400_ref36","doi-asserted-by":"crossref","DOI":"10.1145\/3122831.3122833","article-title":"From relation algebra to semi-join algebra: An approach for graph query optimization","author":"Hellings","year":"2017"},{"key":"2021052900092713400_ref37","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-28472-4_8","article-title":"The impact of transitive closure on the boolean expressiveness of navigational query languages on graphs","author":"Fletcher","year":"2012"},{"key":"2021052900092713400_ref38","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-90050-6_14","article-title":"The power of Tarski\u2019s relation algebra on trees","author":"Hellings","year":"2018"},{"key":"2021052900092713400_ref39","volume-title":"An Introduction to Formal Languages and Automata","author":"Linz","year":"2012"},{"key":"2021052900092713400_ref40","article-title":"Multi-Dimensional Modal Logic","volume-title":"Applied Logic Series, vol. 4","author":"Marx","year":"1997"},{"key":"2021052900092713400_ref41","doi-asserted-by":"crossref","DOI":"10.1145\/2463664.2465216","article-title":"Querying graph databases","author":"Barcel\u00f3","year":"2013"},{"key":"2021052900092713400_ref42","article-title":"Relative expressiveness of nested regular expressions","author":"Barcel\u00f3","year":"2012"},{"key":"2021052900092713400_ref43","doi-asserted-by":"crossref","DOI":"10.1145\/298514.298591","article-title":"GraphLog: A visual formalism for real life recursion","author":"Consens","year":"1990"},{"key":"2021052900092713400_ref44","article-title":"Containment of conjunctive regular path queries with inverse","author":"Calvanese","year":"2000"},{"key":"2021052900092713400_ref45","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/s00224-016-9676-2","article-title":"Regular queries on graph databases","volume":"61","author":"Reutter","year":"2017","journal-title":"Theory Comput. Syst."},{"key":"2021052900092713400_ref46","article-title":"Extensible markup language (XML) 1.1","volume-title":"W3C recommendation","author":"Bray","year":"2006"},{"key":"2021052900092713400_ref47","doi-asserted-by":"crossref","first-page":"1091","DOI":"10.1093\/comjnl\/bxq055","article-title":"A study of a positive fragment of path queries: Expressiveness, normal form and minimization","volume":"54","author":"Wu","year":"2011","journal-title":"Comput. J."},{"key":"2021052900092713400_ref48","article-title":"RDF 1.1 primer","volume-title":"W3C working group note","author":"Schreiber","year":"2014"},{"key":"2021052900092713400_ref49","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/0022-0000(79)90046-1","article-title":"Propositional dynamic logic of regular programs","volume":"18","author":"Fischer","year":"1979","journal-title":"J. Comput. Syst. Sci."},{"key":"2021052900092713400_ref50","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1145\/256167.256195","article-title":"Kleene algebra with tests","volume":"19","author":"Kozen","year":"1997","journal-title":"ACM Trans. Programming Lang. Syst."},{"key":"2021052900092713400_ref51","volume-title":"Model Checking","author":"Clarke","year":"1999"},{"key":"2021052900092713400_ref52","volume-title":"Database System Concepts","author":"Silberschatz","year":"2011"},{"key":"2021052900092713400_ref53","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/234313.234367","article-title":"Query optimization","volume":"28","author":"Ioannidis","year":"1996","journal-title":"ACM Comput. Surveys"},{"key":"2021052900092713400_ref54","doi-asserted-by":"crossref","DOI":"10.1145\/275487.275492","article-title":"An overview of query optimization in relational systems","author":"Chaudhuri","year":"1998"},{"key":"2021052900092713400_ref55","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1145\/62061.62063","article-title":"Statistical profile estimation in database systems","volume":"20","author":"Mannino","year":"1988","journal-title":"ACM Comput. Surveys"},{"key":"2021052900092713400_ref56","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1145\/356924.356928","article-title":"Query optimization in database systems","volume":"16","author":"Jarke","year":"1984","journal-title":"ACM Comput. Surveys"},{"key":"2021052900092713400_ref57","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1145\/152610.152611","article-title":"Query evaluation techniques for large databases","volume":"25","author":"Graefe","year":"1993","journal-title":"ACM Comput. Surveys"},{"key":"2021052900092713400_ref58","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF01383878","article-title":"A linear-time model-checking algorithm for the alternation-free modal mu-calculus","volume":"2","author":"Cleaveland","year":"1993","journal-title":"Form. Methods System Design"},{"key":"2021052900092713400_ref59","doi-asserted-by":"crossref","DOI":"10.1145\/800070.802186","article-title":"The complexity of relational query languages (extended abstract)","author":"Vardi","year":"1982"},{"key":"2021052900092713400_ref60","article-title":"On Tarski\u2019s Relation Algebra: querying trees and chains and the semi-join algebra.","volume-title":"Hasselt University and Transnational University of Limburg, Hasselt","author":"Hellings","year":"2018"},{"key":"2021052900092713400_ref61","doi-asserted-by":"crossref","first-page":"1737","DOI":"10.1137\/110859440","article-title":"Size bounds and query plans for relational joins","volume":"42","author":"Atserias","year":"2013","journal-title":"SIAM J. Comput."},{"key":"2021052900092713400_ref62","article-title":"Leapfrog triejoin: A simple, worst-case optimal join algorithm","author":"Veldhuizen","year":"2014"},{"key":"2021052900092713400_ref63","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1145\/5236.5237","article-title":"On the complexity of join dependencies","volume":"11","author":"Gyssens","year":"1986","journal-title":"ACM Trans. on Database Syst."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/5\/789\/38335010\/bxaa031.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/5\/789\/38335010\/bxaa031.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,29]],"date-time":"2021-05-29T00:29:35Z","timestamp":1622248175000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/64\/5\/789\/5827080"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,9]]},"references-count":63,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2020,5,9]]},"published-print":{"date-parts":[[2021,5,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxaa031","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,5]]},"published":{"date-parts":[[2020,5,9]]}}}