< Back to previous page

Publication

The Power of Tarski’s Relation Algebra on Trees

Book Contribution - Book Chapter Conference Contribution

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. 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, intersections, and/or difference, both for path queries and Boolean queries. For path queries, 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, 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. One challenging problem remains open, however, for both path and Boolean queries: does adding difference yields more expressive power to fragments containing at least diversity, coprojections, and intersection?
Book: FOUNDATIONS OF INFORMATION AND KNOWLEDGE SYSTEMS, FOIKS 2018
Series: Lecture Notes in Computer Science
Volume: 10833
Pages: 244 - 264
Number of pages: 20
ISBN:9783319900490
Publication year:2018
BOF-keylabel:yes
IOF-keylabel:yes
Accessibility:Open