Factorised representations of query results: Size bounds and readability
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 define...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
2012
|
| _version_ | 1826285044421885952 |
|---|---|
| author | Olteanu, D Závodný, J |
| author_facet | Olteanu, D Závodný, J |
| author_sort | Olteanu, D |
| collection | OXFORD |
| description | 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. Copyright 2012 ACM. |
| first_indexed | 2024-03-07T01:22:57Z |
| format | Conference item |
| id | oxford-uuid:90fcc934-1ee0-40e5-9039-9ee4aee1e824 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T01:22:57Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | oxford-uuid:90fcc934-1ee0-40e5-9039-9ee4aee1e8242022-03-26T23:15:29ZFactorised representations of query results: Size bounds and readabilityConference itemhttp://purl.org/coar/resource_type/c_5794uuid:90fcc934-1ee0-40e5-9039-9ee4aee1e824Symplectic Elements at Oxford2012Olteanu, DZávodný, JWe 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. Copyright 2012 ACM. |
| spellingShingle | Olteanu, D Závodný, J Factorised representations of query results: Size bounds and readability |
| title | Factorised representations of query results: Size bounds and readability |
| title_full | Factorised representations of query results: Size bounds and readability |
| title_fullStr | Factorised representations of query results: Size bounds and readability |
| title_full_unstemmed | Factorised representations of query results: Size bounds and readability |
| title_short | Factorised representations of query results: Size bounds and readability |
| title_sort | factorised representations of query results size bounds and readability |
| work_keys_str_mv | AT olteanud factorisedrepresentationsofqueryresultssizeboundsandreadability AT zavodnyj factorisedrepresentationsofqueryresultssizeboundsandreadability |