{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T13:46:58Z","timestamp":1790516818125,"version":"4.1.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,3,25]],"date-time":"2015-03-25T00:00:00Z","timestamp":1427241600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"EPSRC DTA","award":["EP\/P505216\/1"],"award-info":[{"award-number":["EP\/P505216\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2015,3,25]]},"abstract":"<jats:p>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.<\/jats:p>\n                  <jats:p>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.<\/jats:p>\n                  <jats:p>Recent work showed that f-representations can significantly boost the performance of query evaluation in centralised and distributed settings and of machine learning tasks.<\/jats:p>","DOI":"10.1145\/2656335","type":"journal-article","created":{"date-parts":[[2015,3,25]],"date-time":"2015-03-25T12:03:43Z","timestamp":1427285023000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":88,"title":["Size Bounds for Factorised Representations of Query Results"],"prefix":"10.1145","volume":"40","author":[{"given":"Dan","family":"Olteanu","sequence":"first","affiliation":[{"name":"University of Oxford, Wellington Square, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jakub","family":"Z\u00e1vodn\u00fd","sequence":"additional","affiliation":[{"name":"University of Oxford, Wellington Square, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,3,25]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90058-9"},{"key":"e_1_2_2_2_1","unstructured":"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."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007609"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.43"},{"key":"e_1_2_2_5_1","volume-title":"Proceedings of the 21st International Workshop on Computer Science Logic (CSL'07)","volume":"4646","author":"Bagan G.","unstructured":"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."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556579"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350242"},{"key":"e_1_2_2_8_1","volume-title":"Proceedings of the 8th International Conference on Very Large Data Bases (VLDB'82)","author":"Bancilhon F.","unstructured":"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."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320125"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the 25th International Conference on Very Large Data Bases (VLDB'99)","author":"Boncz P. A.","unstructured":"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."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0187"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_3"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00190-5"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1497577.1497580"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.003"},{"key":"e_1_2_2_16_1","volume-title":"Proceedings of the 4th Biennial Conference on Innovative Data Systems Research (CIDR'09)","author":"Cudr\u00e9-Mauroux P.","unstructured":"P. Cudr\u00e9-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\u00e9-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)."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/320263.320271"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30214-8_22"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.07.006"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00078-3"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_2_23_1","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA'06)","author":"Grohe M.","unstructured":"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."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921077"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10990-011-9078-8"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/115790.115838"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/588111.588133"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/358024.358054"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)90171-J"},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of the 3rd International Conference on Very Large Data Bases (VLDB'77)","volume":"3","author":"Makinouchi A.","year":"1977","unstructured":"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."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721845"},{"key":"e_1_2_2_32_1","unstructured":"H. Q. Ngo D. T. Nguyen C. R\u00e9 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\u00e9 and A. Rudra. 2013. Towards instance optimal join algorithms for data in indexes. http:\/\/arxiv.org\/abs\/1302.0914."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87993-0_26"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_14"},{"key":"e_1_2_2_36_1","volume-title":"Proceedings of the 3rd USENIX Workshop on the Theory and Practice of Provenance.","author":"Olteanu D.","unstructured":"D. Olteanu and J. Z\u00e1vodn\u00fd . 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\u00e1vodn\u00fd. 2011. On factorisation of provenance polynomials. In Proceedings of the 3rd USENIX Workshop on the Theory and Practice of Provenance."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274607"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/12047.13676"},{"key":"e_1_2_2_39_1","doi-asserted-by":"crossref","unstructured":"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":"10.1016\/B978-0-08-051489-5.50008-4"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535573.2488340"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920975"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536232"},{"key":"e_1_2_2_43_1","volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05)","author":"Stonebraker M.","unstructured":"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."},{"key":"e_1_2_2_44_1","volume-title":"Proceedings of the 17th International Conference on Database Theory (ICDT'14)","author":"Veldhuizen T. L.","year":"2014","unstructured":"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."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2656335","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2656335","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:19:37Z","timestamp":1750216777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2656335"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,25]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,3,25]]}},"alternative-id":["10.1145\/2656335"],"URL":"https:\/\/doi.org\/10.1145\/2656335","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,25]]},"assertion":[{"value":"2013-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}