Comparing the expressiveness of downward fragments of the relation algebra with transitive closure on trees

作者：

Highlights：

• Complete Hasse diagrams are given for relative expressiveness on trees and chains.

• Different Hasse diagrams are obtained for Boolean and path semantics.

• Basic downward queries are closed under intersection and difference.

• Condition automata are introduced as a proof tool.

• Boolean downward queries on chains are closed under projection.

摘要

•Complete Hasse diagrams are given for relative expressiveness on trees and chains.•Different Hasse diagrams are obtained for Boolean and path semantics.•Basic downward queries are closed under intersection and difference.•Condition automata are introduced as a proof tool.•Boolean downward queries on chains are closed under projection.

论文关键词：Tree data model,Relational calculus with transitive closure,Downward query language fragments,Path queries,Boolean queries,Relative expressive power

论文评审过程：Received 15 November 2018, Revised 25 October 2019, Accepted 30 October 2019, Available online 8 November 2019, Version of Record 14 November 2019.

论文官网地址：https://doi.org/10.1016/j.is.2019.101467