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

G.H.L. Fletcher, M. Gyssens, J. Paredaens, D. Van Gucht, Yuqing Wu

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

1 Citaat (Scopus)

Samenvatting

We study the expressiveness on a given document of various fragments of XPath, the core navigational language on XML documents. Viewing these languages as fragments of Tarski's relation algebra, we give characterizations for when a binary relation on the document's nodes (i.e., a set of paths) is definable by an expression in these algebras. In contrast with this “global view” on language semantics, there is also a “local view” where one is interested in the nodes to which one can navigate starting from a particular node. In this view, we characterize when a set of nodes can be defined as the result of applying an expression to a given node. All of these global and local definability results are obtained using a two-step methodology, which consists of first characterizing when two nodes cannot be distinguished by an expression in the language, and then bootstrapping these characterizations to the desired results.
Originele taal-2Engels
Pagina's (van-tot)229-259
TijdschriftJournal of Computer and System Sciences
Volume82
Nummer van het tijdschrift2
DOI's
StatusGepubliceerd - mrt 2016

Vingerafdruk

Duik in de onderzoeksthema's van 'Structural characterizations of the navigational expressiveness of relation algebras on a tree'. Samen vormen ze een unieke vingerafdruk.

Citeer dit