Tue 27 Oct 2015 16:00 - 16:30 at Ellwood 1 - Session 4 Chair(s): Jeremy Gibbons

Motivated by the continuing interest in the tree data model, we study the expressive power of downward fragments of navigational query languages on trees. The basic navigational query language we consider expresses queries by building binary relations from the edge relations and the identity relation, using composition and union. We study the effects on the expressive power when we add transitive closure, projections, coprojections, intersection, and difference. We study expressiveness at the level of boolean queries and path queries, on labeled and unlabeled trees, and on labeled and unlabeled chains. In all these cases, we are able to present the complete Hasse diagram of relative expressiveness. In particular, we were able to decide, for each fragment of the navigational query languages that we study, whether it is closed under difference and intersection when applied on trees.

Tue 27 Oct

Displayed time zone: Eastern Time (US & Canada) change

15:30 - 17:00
Session 4DBPL at Ellwood 1
Chair(s): Jeremy Gibbons University of Oxford, UK
15:30
30m
Talk
Using Dependent Types and Tactics to Enable Semantic Optimization of Language-Integrated Queries
DBPL
16:00
30m
Talk
Relative Expressive Power of Downward Fragments of Navigational Query Languages on Trees and Chains
DBPL
Jelle Hellings Hasselt University and Transnational University of Limburg, Marc Gyssens Hasselt University and Transnational University of Limburg, Yuqing Wu Indiana University, Dirk Van Gucht Indiana University, Jan Van den Bussche Hasselt University and Transnational University of Limburg, Stijn Vansummeren Université Libre de Bruxelles, George Fletcher Eindhoven University of Technology
16:30
30m
Talk
Typing Regular Path Query Languages for Data Graphs
DBPL