Structural characterizations of the navigational expressiveness of relation algebras on a tree

DOI10.1016/J.JCSS.2015.10.002zbMATH Open1346.68080arXiv1502.03258OpenAlexW1528943166MaRDI QIDQ896017FDOQ896017

Jan Paredaens, Yuqing Wu, George H. L. Fletcher, D. Van Gucht, Marc Gyssens

Publication date: 11 December 2015

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Abstract: Given a document D in the form of an unordered node-labeled tree, we study the expressiveness on D of various basic fragments of XPath, the core navigational language on XML documents. Working from the perspective of these languages as fragments of Tarski's relation algebra, we give characterizations, in terms of the structure of D, for when a binary relation on its nodes is definable by an expression in these algebras. Since each pair of nodes in such a relation represents a unique path in D, our results therefore capture the sets of paths in D definable in each of the fragments. We refer to this perspective on language semantics as the "global view." In contrast with this global view, there is also a "local view" where one is interested in the nodes to which one can navigate starting from a particular node in the document. In this view, we characterize when a set of nodes in D can be defined as the result of applying an expression to a given node of D. All these definability results, both in the global and the local view, are obtained by using a robust two-step methodology, which consists of first characterizing when two nodes cannot be distinguished by an expression in the respective fragments of XPath, and then bootstrapping these characterizations to the desired results.

Full work available at URL: https://arxiv.org/abs/1502.03258

zbMATH Keywords

XMLtreesbisimulationrelation algebraXPathinstance expressivity

Mathematics Subject Classification ID

Database theory (68P15) Cylindric and polyadic algebras; relation algebras (03G15)

Cites Work

• Computable queries for relational data bases
• Elements of finite model theory.
• Two-variable logic on data trees and XML reasoning
• XPath satisfiability in the presence of DTDs
• Title not available (Why is that?)
• Containment and equivalence for a fragment of XPath
• Structural properties of XPath fragments
• Relation algebras
• Encyclopedia of Database Systems
• Relation algebras by games
• On the expressive power of the relational algebra
• Title not available (Why is that?)
• The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs
• Relative expressive power of navigational querying on graphs using transitive closure
• Similarity and bisimilarity notions appropriate for characterizing indistinguishability in fragments of the calculus of relations
• Relative expressive power of navigational querying on graphs
• Equivalence in finite-variable logics is complete for polynomial time
• The calculus of relations as a foundation for mathematics
• Computer Science Logic
• Complete axiomatizations for XPath fragments

Cited In (4)

• Beyond representing orthology relations by trees
• Database Theory - ICDT 2005
• Structural properties of XPath fragments
• FIRST-ORDER AXIOMATISATIONS OF REPRESENTABLE RELATION ALGEBRAS NEED FORMULAS OF UNBOUNDED QUANTIFIER DEPTH

Uses Software

• XPath

This page was built for publication: Structural characterizations of the navigational expressiveness of relation algebras on a tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896017)