Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Sign Up
Cited by 116Advanced Database Systems and QueriesAdvanced Graph Theory ResearchAlgorithms and Data Compression

The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.

Size Bounds for Factorised Representations of Query Results

Olteanu, Dan, Závodný, Jakub·2015·ACM Transactions on Database Systems
DOI 10.1145/2656335
Open this paper in CoChat — free account

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.

Overview

Integrity signals

Registry

Crossref · 10.1145/2656335

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Citations

Cites

Research works printed but not linked: 43

  1. 10.1016/0022-0000(86)90058-9 · DOI
  2. S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley. S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley.
  3. 10.1145/1007568.1007609 · DOI
  4. 10.1109/FOCS.2008.43 · DOI
  5. G. Bagan , A. Durand , and E. Grandjean . 2007. On acyclic conjunctive queries and constant delay enumeration . In Proceedings of the 21st International Workshop on Computer Science Logic (CSL'07) . Lecture Notes in Computer Science , vol. 4646 . Springer, 208--222. G. Bagan, A. Durand, and E. Grandjean. 2007. On acyclic conjunctive queries and constant delay enumeration. In Proceedings of the 21st International Workshop on Computer Science Logic (CSL'07). Lecture Notes in Computer Science, vol. 4646. Springer, 208--222.
  6. 10.14778/2556549.2556579 · DOI
  7. 10.14778/2350229.2350242 · DOI
  8. F. Bancilhon , P. Richard , and M. Scholl . 1982. On line processing of compacted relations . In Proceedings of the 8th International Conference on Very Large Data Bases (VLDB'82) . 263--269. F. Bancilhon, P. Richard, and M. Scholl. 1982. On line processing of compacted relations. In Proceedings of the 8th International Conference on Very Large Data Bases (VLDB'82). 263--269.
  9. 10.1145/320107.320125 · DOI
  10. P. A. Boncz , S. Manegold , and M. L. Kersten . 1999. Database architecture optimized for the new bottleneck: Memory access . In Proceedings of the 25th International Conference on Very Large Data Bases (VLDB'99) . 54--65. P. A. Boncz, S. Manegold, and M. L. Kersten. 1999. Database architecture optimized for the new bottleneck: Memory access. In Proceedings of the 25th International Conference on Very Large Data Bases (VLDB'99). 54--65.
  11. 10.1147/rd.312.0187 · DOI
  12. 10.1007/978-3-540-70575-8_3 · DOI
  13. 10.1016/0020-0190(95)00190-5 · DOI
  14. 10.1145/1497577.1497580 · DOI
  15. 10.1016/j.jcss.2010.04.003 · DOI
  16. P. Cudré-Mauroux , E. Wu , and S. Madden . 2009. The case for Rodentstore: An adaptive, declarative storage system . In Proceedings of the 4th Biennial Conference on Innovative Data Systems Research (CIDR'09) . P. Cudré-Mauroux, E. Wu, and S. Madden. 2009. The case for Rodentstore: An adaptive, declarative storage system. In Proceedings of the 4th Biennial Conference on Innovative Data Systems Research (CIDR'09).
  17. 10.1007/s00778-006-0004-3 · DOI
  18. 10.1145/320263.320271 · DOI
  19. 10.1007/978-3-540-30214-8_22 · DOI
  20. 10.1016/j.artint.2012.07.006 · DOI
  21. 10.1016/S0004-3702(00)00078-3 · DOI
  22. M. Grohe and D. Marx . 2006. Constraint solving via fractional edge covers . In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA'06) . 289--298. M. Grohe and D. Marx. 2006. Constraint solving via fractional edge covers. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA'06). 289--298.
  23. 10.14778/1921071.1921077 · DOI
  24. 10.1007/s10990-011-9078-8 · DOI
  25. 10.1145/115790.115838 · DOI
  26. 10.1145/588111.588133 · DOI
  27. 10.1145/358024.358054 · DOI
  28. 10.1016/0166-218X(93)90171-J · DOI
  29. A. Makinouchi . 1977 . A consideration on normal form of not-necessarily-normalized relation in the relational data model . In Proceedings of the 3rd International Conference on Very Large Data Bases (VLDB'77) . Vol. 3 . 447--453. A. Makinouchi. 1977. A consideration on normal form of not-necessarily-normalized relation in the relational data model. In Proceedings of the 3rd International Conference on Very Large Data Bases (VLDB'77). Vol. 3. 447--453.
  30. 10.1145/1721837.1721845 · DOI
  31. H. Q. Ngo D. T. Nguyen C. Ré and A. Rudra. 2013. Towards instance optimal join algorithms for data in indexes. http://arxiv.org/abs/1302.0914. H. Q. Ngo D. T. Nguyen C. Ré and A. Rudra. 2013. Towards instance optimal join algorithms for data in indexes. http://arxiv.org/abs/1302.0914. · arXiv
  32. 10.1145/2213556.2213565 · DOI
  33. 10.1007/978-3-540-87993-0_26 · DOI
  34. 10.1007/11965893_14 · DOI
  35. D. Olteanu and J. Závodný . 2011. On factorisation of provenance polynomials . In Proceedings of the 3rd USENIX Workshop on the Theory and Practice of Provenance. D. Olteanu and J. Závodný. 2011. On factorisation of provenance polynomials. In Proceedings of the 3rd USENIX Workshop on the Theory and Practice of Provenance.
  36. 10.1145/2274576.2274607 · DOI
  37. 10.1145/12047.13676 · DOI
  38. J. Pearl. 1989. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann San Fransisco. J. Pearl. 1989. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann San Fransisco. · DOI
  39. 10.14778/2535573.2488340 · DOI
  40. 10.14778/1920841.1920975 · DOI
  41. 10.14778/2536222.2536232 · DOI
  42. M. Stonebraker , D. J. Abadi , A. Batkin , X. Chen , M. Cherniack , M. Ferreira , E. Lau , A. Lin , S. Madden , E. O'Neil , P. O'Neil , A. Rasin , N. Tran , and S. Zdonik . 2005. C-store: A column-oriented DBMS . In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05) . 553--564. M. Stonebraker, D. J. Abadi, A. Batkin, X. Chen, M. Cherniack, M. Ferreira, E. Lau, A. Lin, S. Madden, E. O'Neil, P. O'Neil, A. Rasin, N. Tran, and S. Zdonik. 2005. C-store: A column-oriented DBMS. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05). 553--564.
  43. T. L. Veldhuizen . 2014 . Triejoin: A simple, worst-case optimal join algorithm . In Proceedings of the 17th International Conference on Database Theory (ICDT'14) . 96--106. T. L. Veldhuizen. 2014. Triejoin: A simple, worst-case optimal join algorithm. In Proceedings of the 17th International Conference on Database Theory (ICDT'14). 96--106.

Cited by

See all 116

Metadata

Authors
Olteanu, D., & Závodný, J.
Affiliations
University of Oxford (GB)
ORCID
Olteanu, Dan
Venue
ACM Transactions on Database Systems
Publisher
Association for Computing Machinery (ACM)
Published
2015-03-25
Volume
40
Issue
1
Pages
1-44
ISSN
  • 0362-5915 (ISSN-L)
  • 1557-4644
DOI
10.1145/2656335
OpenAlex
W2050100848
Cited by
116
References
1
Citations by year
2026: 3 · 2025: 15 · 2024: 9 · 2023: 15 · 2022: 7 · 2021: 10 · 2020: 9 · 2019: 9 · 2018: 12 · 2017: 9 · 2016: 11 · 2015: 5
FWCI
14.14
Type
journal article
Language
en
Open access
closed
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
Locations
ACM Transactions on Database Systems (publishedVersion)
Funders
EPSRC DTA (EP/P505216/1)
Topics
  • Physical Sciences › Computer Science › Information Systems › Advanced Database Systems and Queries
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Graph Theory Research
  • Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
Keywords
succinct representation, conjunctive queries, query processing, relational algebra

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review