Size Bounds for Factorised Representations of Query Results
Authors:
Top Cited Papers
Open Access
- 25 March 2015
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 40 (1) , 1-44
Abstract
We study two succinct representation systems for relational data based on relational algebra expressions with unions, Cartesian products, and singleton relations: f-representations, which employ algebraic factorisation using distributivity of product over union, and d-representations, which are f-representations where further succinctness is brought by explicit sharing of repeated subexpressions. In particular we study such representations for results of conjunctive queries. We derive tight asymptotic bounds for representation sizes and present algorithms to compute representations within these bounds. We compare the succinctness of f-representations and d-representations for results of equi-join queries, and relate them to fractional edge covers and fractional hypertree decompositions of the query hypergraph. Recent work showed that f-representations can significantly boost the performance of query evaluation in centralised and distributed settings and of machine learning tasks.Keywords
Funding Information
- EPSRC DTA (EP/P505216/1)
This publication has 34 references indexed in Scilit:
- Constraint satisfaction with succinctly specified relationsJournal of Computer and System Sciences, 2010
- Approximating fractional hypertree widthACM Transactions on Algorithms, 2010
- Closed patterns meet n -ary relationsACM Transactions on Knowledge Discovery From Data, 2009
- Efficient query evaluation on probabilistic databasesThe VLDB Journal, 2006
- A comparison of structural CSP decomposition methodsArtificial Intelligence, 2000
- A simple linear-time algorithm for finding path-decompositions of small widthInformation Processing Letters, 1996
- A new normal form for nested relationsACM Transactions on Database Systems, 1987
- A simple guide to five normal forms in relational database theoryCommunications of the ACM, 1983
- On searching transposed filesACM Transactions on Database Systems, 1979
- Normalization and hierarchical dependencies in the relational data modelACM Transactions on Database Systems, 1978