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

作者：

Highlights：

• Natural variations of Tarski's classic relation algebra are studied on trees.

• The notion of instance expressibility is introduced and studied for these languages.

• A robust methodology is given and used for characterizing instance expressivity.

• Our characterizations are given for both global and local views on query semantics.

• These characterizations are effectively computable and hence can be used in practice.

摘要

•Natural variations of Tarski's classic relation algebra are studied on trees.•The notion of instance expressibility is introduced and studied for these languages.•A robust methodology is given and used for characterizing instance expressivity.•Our characterizations are given for both global and local views on query semantics.•These characterizations are effectively computable and hence can be used in practice.

论文关键词：Trees,Relation algebra,XML,XPath,Bisimulation,Instance expressivity

论文评审过程：Received 3 June 2013, Accepted 12 July 2015, Available online 10 November 2015, Version of Record 27 November 2015.

论文官网地址：https://doi.org/10.1016/j.jcss.2015.10.002