More Web Proxy on the site http://driver.im/

research-article

Public Access

AJAR: Aggregations and Joins over Annotated Relations

Authors:

Manas R. Joglekar,

Rohan Puttagunta,

Christopher RéAuthors Info & Claims

PODS '16: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

Pages 91 - 106

https://doi.org/10.1145/2902251.2902293

Published: 15 June 2016 Publication History

Abstract

We study a class of aggregate-join queries with multiple aggregation operators evaluated over annotated relations. We show that straightforward extensions of standard multiway join algorithms and generalized hypertree decompositions (GHDs) provide best-known runtime guarantees. In contrast, prior work uses bespoke algorithms and data structures and does not match these guarantees. We extend the standard techniques by providing a complete characterization of (1) the set of orderings equivalent to a given ordering and (2) the set of GHDs valid with respect to the given ordering, i.e., GHDs that correctly answer a given aggregate-join query when provided to (simple variants of) standard join algorithms. We show by example that previous approaches are incomplete. The key technical consequence of our characterizations is a decomposition of a valid GHD into a set of (smaller) unconstrained GHDs, i.e., into a set of GHDs of sub-queries without aggregations. Since this decomposition is comprised of unconstrained GHDs, we are able to connect to the wide literature on GHDs for join query processing, thereby obtaining improved runtime bounds, MapReduce variants, and an efficient method to find approximately optimal GHDs.

References

[1]

Christopher R. Aberger, Susan Tu, Kunle Olukotun, and Christopher Ré. Emptyheaded: A relational engine for graph processing. SIGMOD (to appear), 2016.

Digital Library

[2]

Serge Abiteboul, Richard Hull, and Victor Vianu, editors. Foundations of Databases: The Logical Level. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition, 1995.

Digital Library

[3]

Foto N. Afrati, Manas Joglekar, Christopher Ré, Semih Salihoglu, and Jeffrey D. Ullman. GYM: A multiround join algorithm in mapreduce. CoRR, abs/1410.4156, 2014.

[4]

Srinivas M. Aji and Robert J. McEliece. The generalized distributive law. IEEE Transactions on Information Theory, 46(2):325--343, 2000.

Digital Library

[5]

Albert Atserias, Martin Grohe, and Dániel Marx. Size bounds and query plans for relational joins. FOCS '08, pages 739--748, Washington, DC, USA, 2008. IEEE Computer Society.

Digital Library

[6]

Nurzhan Bakibayev, Tomás Kociský, Dan Olteanu, and Jakub Zavodny. Aggregation and ordering in factorised databases. PVLDB, 6(14):1990--2001, 2013.

Digital Library

[7]

Hubie Chen and Vıctor Dalmau. Decomposing quantified conjunctive (or disjunctive) formulas. In Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012, Dubrovnik, Croatia, June 25--28, 2012, pages 205--214, 2012.

Digital Library

[8]

B. Eckmann and P. J. Hilton. Group-like structures in general categories i multiplications and comultiplications. Mathematische Annalen, 145(3):227--255.

[9]

G. Gottlob, M. Grohe, M. Nysret, M. Samer, and F. Scarcello. Hypertree Decompositions: Structure, Algorithms, and Applications. In WG, 2005.

Digital Library

[10]

Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decompositions and tractable queries. In PODS 1999, pages 21--32, 1999.

Digital Library

[11]

Todd J. Green, Grigoris Karvounarakis, and Val Tannen. Provenance semirings. PODS '07, pages 31--40, New York, NY, USA, 2007. ACM.

Digital Library

[12]

Martin Grohe and Dániel Marx. Constraint solving via fractional edge covers. ACM Trans. Algorithms, 11(1):4:1--4:20, August 2014.

Digital Library

[13]

Manas Joglekar, Rohan Puttagunta, and Christopher Ré. Aggregations over generalized hypertree decompositions. CoRR, abs/1508.07532, 2015.

[14]

Manas R. Joglekar and Christopher Ré. It's all a matter of degree: Using degree information to optimize multiway joins. In ICDT (to appear), 2016.

[15]

Kalev Kask, Rina Dechter, Javier Larrosa, and Avi Dechter. Unifying tree decompositions for reasoning in graphical models. Artif. Intell., 166:165--193, 2005.

Digital Library

[16]

Mahmoud Abo Khamis, Hung Q. Ngo, and Atri Rudra. FAQ: questions asked frequently. CoRR, abs/1504.04044, 2015.

[17]

Dániel Marx. Approximating fractional hypertree width. ACM Trans. Algorithms, 6, 2010.

Digital Library

[18]

Dániel Marx. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. In Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC '10, pages 735--744, New York, NY, USA, 2010. ACM.

Digital Library

[19]

Daniel Marx. Tractable structures for constraint satisfaction with truth tables. Theory of Computing Systems, 48, 2011.

Digital Library

[20]

Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. Worst-case optimal join algorithms: {extended abstract}. In PODS 2012, pages 37--48, 2012.

Digital Library

[21]

Hung Q. Ngo, Christopher Ré, and Atri Rudra. Skew strikes back: new developments in the theory of join algorithms. SIGMOD Record, 42(4):5--16, 2013.

Digital Library

[22]

Dan Olteanu and Jakub Závodný. Size bounds for factorised representations of query results. ACM Trans. Database Syst., 40(1):2, 2015.

Digital Library

[23]

Adam Perelman and Christopher Ré. Duncecap: Compiling worst-case optimal query plans. In SIGMOD 2015, pages 2075--2076, 2015.

Digital Library

[24]

Christopher Ré and Dan Suciu. The trichotomy of HAVING queries on a probabilistic database. VLDB J., 18(5):1091--1116, 2009.

Digital Library

[25]

Neil Robertson and P.D Seymour. Graph minors. iii. planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49 -- 64, 1984.

[26]

Charles A. Sutton and Andrew McCallum. An introduction to conditional random fields. Foundations and Trends in Machine Learning, 4(4):267--373, 2012.

Digital Library

[27]

Susan Tu and Christopher Ré. Duncecap: Query plans using generalized hypertree decompositions. In SIGMOD 2015, pages 2077--2078, 2015.

Digital Library

[28]

Todd L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In ICDT 2014, pages 96--106, 2014.

[29]

M. Yannakakis. Algorithms for Acyclic Database Schemes. In VLDB, 1981.

Digital Library

Cited By

Wang QLuo QWang Y(2024)Relational Algorithms for Top-k Query EvaluationProceedings of the ACM on Management of Data10.1145/36549712:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654971
Hu X(2024)Fast Matrix Multiplication for Query ProcessingProceedings of the ACM on Management of Data10.1145/36515992:2(1-25)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651599
Huang ZSen RLiu JWu E(2023)JoinBoost: Grow Trees over Normalized Data Using Only SQLProceedings of the VLDB Endowment10.14778/3611479.361150916:11(3071-3084)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611509
Show More Cited By

Index Terms

AJAR: Aggregations and Joins over Annotated Relations
1. Information systems
  1. Data management systems
    1. Database design and models
      1. Relational database model
    2. Query languages
      1. Relational database query languages
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Computing Local Sensitivities of Counting Queries with Joins
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data

Local sensitivity of a query Q given a database instance D, i.e. how much the output Q(D) changes when a tuple is added to D or deleted from D, has many applications including query analysis, outlier detection, and differential privacy. However, it is ...
A pruning-based approach for supporting Top-K join queries
WWW '06: Proceedings of the 15th international conference on World Wide Web

An important issue arising from large scale data integration is how to efficiently select the top-K ranking answers from multiple sources while minimizing the transmission cost. This paper resolves this issue by proposing an efficient pruning-based ...
Finding Optimal Triangulations Parameterized by Edge Clique Cover
Abstract
We consider problems that can be formulated as a task of finding an optimal triangulation of a graph w.r.t. some notion of optimality. We present algorithms parameterized by the size of a minimum edge clique cover ( $cc$ ) to such problems. This ... $^{}$ $^{}$ $^{}^{}$ $^{}^{}$ $^{}$ $^{}^{}$ $^{}^{}$ $^{}^{}$ $^{}$ $^{}^{^{}}$ $^{}^{}$ $^{}^{^{}}$ $^{}^{^{}}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '16: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

June 2016

504 pages

ISBN:9781450341912

DOI:10.1145/2902251

General Chair:
Tova Milo
Tel Aviv University, Israel
,
Program Chair:
Wang-Chiew Tan
University of California, Santa Cruz, USA

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Defense Advanced Research Projects Agency (XDATA Program)
National Science Foundation (EarthCube)
Moore Foundation Data Driven Investigator
Defense Advanced Research Projects Agency (SIMPLEX Program)
National Science Foundation (Career Award)
Sloan Research Fellowship
Defense Advanced Research Projects Agency (MEMEX Program)
Office of Naval Research
National Science Foundation

Conference

SIGMOD/PODS'16

Sponsor:

SIGMOD

SIGMOD/PODS'16: International Conference on Management of Data

June 26 - July 1, 2016

California, San Francisco, USA

Acceptance Rates

PODS '16 Paper Acceptance Rate 31 of 94 submissions, 33%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
783
Total Downloads

Downloads (Last 12 months)123
Downloads (Last 6 weeks)13

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang QLuo QWang Y(2024)Relational Algorithms for Top-k Query EvaluationProceedings of the ACM on Management of Data10.1145/36549712:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654971
Hu X(2024)Fast Matrix Multiplication for Query ProcessingProceedings of the ACM on Management of Data10.1145/36515992:2(1-25)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651599
Huang ZSen RLiu JWu E(2023)JoinBoost: Grow Trees over Normalized Data Using Only SQLProceedings of the VLDB Endowment10.14778/3611479.361150916:11(3071-3084)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611509
Dong WYi K(2023)Query Evaluation under Differential PrivacyACM SIGMOD Record10.1145/3631504.363150652:3(6-17)Online publication date: 2-Nov-2023
https://dl.acm.org/doi/10.1145/3631504.3631506
Huang ZWu E(2023)Lightweight Materialization for Fast Dashboards Over JoinsProceedings of the ACM on Management of Data10.1145/36267351:4(1-27)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626735
Hadar SItzhaky SStorm THirschfeld R(2023)Scalable Spreadsheet-Driven End-User Applications with Incremental ComputationProceedings of the 2023 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3622758.3622887(1-14)Online publication date: 18-Oct-2023
https://dl.acm.org/doi/10.1145/3622758.3622887
Hu XWang Q(2023)Computing the Difference of Conjunctive Queries EfficientlyProceedings of the ACM on Management of Data10.1145/35892981:2(1-26)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3589298
Kim KHa JFletcher GHan WGeerts FNgo HSintos S(2023)Guaranteeing the Õ(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over JoinsProceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3584372.3588676(113-125)Online publication date: 18-Jun-2023
https://dl.acm.org/doi/10.1145/3584372.3588676
Bonifati ADumbrava SFletcher GHidders JHofer MMartens WMurlak FShinavier JStaworko STomaszuk D(2022)Threshold queries in theory and in the wildProceedings of the VLDB Endowment10.14778/3510397.351040715:5(1105-1118)Online publication date: 18-May-2022
https://dl.acm.org/doi/10.14778/3510397.3510407
Dong WYi KLibkin LBarceló P(2022)A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive QueriesProceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3517804.3524143(213-225)Online publication date: 12-Jun-2022
https://dl.acm.org/doi/10.1145/3517804.3524143
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents