Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/26385
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | HELLINGS, Jelle | - |
dc.contributor.author | Pilachowski, Catherine L. | - |
dc.contributor.author | Van Gucht, Dirk | - |
dc.contributor.author | GYSSENS, Marc | - |
dc.contributor.author | Wu, Yuqing | - |
dc.date.accessioned | 2018-07-20T09:15:06Z | - |
dc.date.available | 2018-07-20T09:15:06Z | - |
dc.date.issued | 2017 | - |
dc.identifier.citation | Proceedings of the 16th international symposium on database programming languages (DBPL 2017), ASSOC COMPUTING MACHINERY, (Art N° 5) | - |
dc.identifier.isbn | 9781450353540 | - |
dc.identifier.uri | http://hdl.handle.net/1942/26385 | - |
dc.description.abstract | Many graph query languages rely on the composition operator to navigate graphs and select nodes of interests, even though evaluating compositions of relations can be costly. Often, this need for composition can be reduced by rewriting towards queries that use semi-joins instead. In this way, the cost of evaluating queries can be significantly reduced. We study techniques to recognize and apply such rewritings. Concretely, we study the relationship between the expressive power of the relation algebras, that heavily rely on composition, and the semi-join algebras, that replace the composition operator in favor of the semi-join operators. As our main result, we show 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 that evaluate to sets of nodes. For practical relevance, we exhibit constructive steps for rewriting relation algebra queries to semi-join algebra queries, and prove that these steps lead to only a well-bounded increase in the number of steps needed to evaluate the rewritten queries. In addition, on node-labeled graphs that are 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. | - |
dc.description.sponsorship | This material is based upon work supported by the National Science Foundation under Grant No. NSF 1438990. | - |
dc.language.iso | en | - |
dc.publisher | ASSOC COMPUTING MACHINERY | - |
dc.rights | © 2017 ACM. | - |
dc.title | From Relation Algebra to Semi-Join Algebra: An Approach for Graph Query Optimization | - |
dc.type | Proceedings Paper | - |
local.bibliographicCitation.conferencedate | 01/09/2017 | - |
local.bibliographicCitation.conferencename | 16th International Symposium on Database Programming Languages (DBPL '17) | - |
local.bibliographicCitation.conferenceplace | Munich, Germany | - |
local.format.pages | 10 | - |
local.bibliographicCitation.jcat | C1 | - |
dc.description.notes | [Hellings, Jelle; Gyssens, Marc] Hasselt Univ, Hasselt, Belgium. [Pilachowski, Catherine L.; Van Gucht, Dirk] Indiana Univ, Bloomington, IN USA. [Wu, Yuqing] Pomona Coll, Claremont, CA 91711 USA. | - |
local.publisher.place | New York (NY), USA | - |
local.type.refereed | Refereed | - |
local.type.specified | Proceedings Paper | - |
local.bibliographicCitation.artnr | 5 | - |
dc.identifier.doi | 10.1145/3122831.3122833 | - |
dc.identifier.isi | 000426964700005 | - |
local.bibliographicCitation.btitle | Proceedings of the 16th international symposium on database programming languages (DBPL 2017) | - |
item.contributor | HELLINGS, Jelle | - |
item.contributor | Pilachowski, Catherine L. | - |
item.contributor | Van Gucht, Dirk | - |
item.contributor | GYSSENS, Marc | - |
item.contributor | Wu, Yuqing | - |
item.fullcitation | HELLINGS, Jelle; Pilachowski, Catherine L.; Van Gucht, Dirk; GYSSENS, Marc & Wu, Yuqing (2017) From Relation Algebra to Semi-Join Algebra: An Approach for Graph Query Optimization. In: Proceedings of the 16th international symposium on database programming languages (DBPL 2017), ASSOC COMPUTING MACHINERY, (Art N° 5). | - |
item.accessRights | Open Access | - |
item.fulltext | With Fulltext | - |
item.validation | ecoom 2019 | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
dbpl2017_paper.pdf | Peer-reviewed author version | 816.61 kB | Adobe PDF | View/Open |
a5-hellings.pdf Restricted Access | Published version | 843.44 kB | Adobe PDF | View/Open Request a copy |
SCOPUSTM
Citations
1
checked on Sep 5, 2020
WEB OF SCIENCETM
Citations
4
checked on May 1, 2024
Page view(s)
90
checked on Sep 7, 2022
Download(s)
256
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.