Factorised representations of query results: size bounds and readability
Factorised representations of query results: size bounds and readability
复制标题
查询结果的因式分解表示：大小范围和可读性
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Jakub Závodný
中科院分区：
文献类型：
--
作者：
Dan Olteanu;Jakub Závodný
我们介绍了一种基于代数分解的关系数据的表示系统，该系统使用产品的分配性而不是产品和联合的结合性和交通量。
我们基于其结果的分解，给出了两种结合查询的特征，它们的嵌套结构是由所谓的分解树定义的。
第一个特征涉及分解表示的大小。对于任何查询，我们得出了在分解类别中渐近紧密的大小结合。
我们还通过对结果元组的出处的可读性的紧密界限来表征查询，并以有限的可读性来定义查询类。
We introduce a representation system for relational data based on algebraic factorisation using distributivity of product over union and commutativity of product and union.
We give two characterisations of conjunctive queries based on factorisations of their results whose nesting structure is defined by so-called factorisation trees.
The first characterisation concerns sizes of factorised representations. For any query, we derive a size bound that is asymptotically tight within our class of factorisations.
We also characterise the queries by tight bounds on the readability of the provenance of result tuples and define syntactically the class of queries with bounded readability.