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

DOI10.1016/J.JCSS.2015.10.002MaRDI QIDQ896017zbMATH OpenOpenAlexFDO

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

Publication date 11 December 2015

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

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)

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.

Recommendations

• Structural properties of XPath fragments
• scientific article; zbMATH DE number 1953125
• Database Theory - ICDT 2005
• The power of Tarski's relation algebra on trees
• Relative expressive power of navigational querying on graphs

Cites work

• scientific article; zbMATH DE number 193143 (Why is no real title available?)
• scientific article; zbMATH DE number 3607517 (Why is no real title available?)
• Complete axiomatizations for XPath fragments
• Computable queries for relational data bases
• Computer Science Logic
• Containment and equivalence for a fragment of XPath
• Elements of finite model theory.
• Encyclopedia of Database Systems
• Equivalence in finite-variable logics is complete for polynomial time
• On the expressive power of the relational algebra
• Relation algebras
• Relation algebras by games
• Relative expressive power of navigational querying on 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
• Structural properties of XPath fragments
• The calculus of relations as a foundation for mathematics
• The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs
• Two-variable logic on data trees and XML reasoning
• XPath satisfiability in the presence of DTDs

Cited in

(5)

• The power of Tarski's relation algebra on trees
• 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

Describes a project that uses

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)