Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/37014
Title: | The power of Tarski's relation algebra on trees | Authors: | HELLINGS, Jelle Van Gucht, Dirk GYSSENS, Marc WU, Yuqing |
Issue Date: | 2022 | Publisher: | ELSEVIER SCIENCE INC | Source: | Journal of Logical and Algebraic Methods in Programming, 126 (Art N° 100748) | Abstract: | Fragments of Tarski’s relation algebra form the basis of many versatile graph and tree query languages including the regular path queries, XPath, and SPARQL. Surprisingly, however, a systematic study of the relative expressive power of relation algebra fragments on trees has not yet been undertaken. In this work, we perform such a systematic study. Our approach is to start from a basic fragment which only allows composition and union. We then study how the expressive power of the query language changes if we add diversity, converse, projections, coprojections, intersection, and/or difference, both for path queries and Boolean queries. For path queries on labeled trees, we found that adding intersection and difference yields more expressive power for some fragments, while adding one of the other operators always yields more expressive power. For Boolean queries on labeled trees, we obtain a similar picture for the relative expressive power, except for a few fragments where adding converse or projection yields no more expressive power. Additionally, we also studied querying unlabeled trees, for which we have found several redundancies. One challenging problem remains open, however, for both path and Boolean queries: does adding difference yield more expressive power to fragments containing at least diversity, coprojections, and intersection? | Keywords: | Tree queries;first-order logic;relation algebra;branching;locality | Document URI: | http://hdl.handle.net/1942/37014 | ISSN: | 2352-2208 | e-ISSN: | 2352-2216 | DOI: | 10.1016/j.jlamp.2022.100748 | ISI #: | 000776715500005 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2023 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
jlamp2022_paper.pdf Restricted Access | Published version | 577.44 kB | Adobe PDF | View/Open Request a copy |
foiks2018_1_paper.pdf | Peer-reviewed author version | 581.2 kB | Adobe PDF | View/Open |
WEB OF SCIENCETM
Citations
2
checked on Oct 12, 2024
Page view(s)
40
checked on Sep 7, 2022
Download(s)
20
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.