Cited By
View all- 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
Conjunctive Queries with Comparisons
Authors: 
Qichen Wang, Ke YiAuthors Info & Claims
Abstract
Conjunctive queries with predicates in the form of comparisons that span multiple relations have regained interest recently, due to their relevance in OLAP queries, spatiotemporal databases, and machine learning over relational data. The standard technique, predicate pushdown, has limited efficacy on such comparisons. A technique by Willard can be used to process short comparisons that are adjacent in the join tree in time linear in the input size plus output size. In this paper, we describe a new algorithm for evaluating conjunctive queries with both short and long comparisons, and identify an acyclic condition under which linear time can be achieved. We have also implemented the new algorithm on top of Spark, and our experimental results demonstrate order-of-magnitude speedups over SparkSQL on a variety of graph patterns and analytical queries.
References
[1]
S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases: The Logical Level. Addison-Wesley
[2]
G. Bagan, A. Durand, and E. Grandjean. On acyclic conjunctive queries and constant delay enumeration. CSL/EACSL, page 208--222. Springer-Verlag, 2007.
[3]
B. Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM Journal on Computing, 17(3):427--462, 1988.
[4]
B. Chazelle and L. J. Guibas. Fractional cascading: II. Applications. Algorithmica, 1:163--191, 1986.
[5]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009.
[6]
M. de Berg, O. Cheong, M. J. van Kreveld, and M. H. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag TELOS, Santa Clara, CA, USA, 3rd ed. edition, 2008.
[7]
G. Gottlob, M. Grohe, N. Musliu, M. Samer, and F. Scarcello. Hypertree decompositions: Structure, algorithms, and applications. In WG, page 1--15. Springer-Verlag, 2005.
[8]
M. Graham. On the universal relation. Technical Report. University of Toronto. Computer Systems Research Group and Graham, MH, 1980.
[9]
M. Idris, M. Ugarte, S. Vansummeren, H. Voigt, and W. Lehner. General dynamic yannakakis: conjunctive queries with theta joins under updates. The VLDB Journal, 29:619--653, 2020.
[10]
M. Khamis, H. Ngo, D. Olteanu, and D. Suciu. Boolean tensor decomposition for conjunctive queries with negation. In ICDT, volume 127 of LIPIcs, pages 21:1--21:19. Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik, 2019.
[11]
M. Khamis, H. Q. Ngo, and D. Suciu. What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? In PODS, page 429--444. ACM, 2017.
[12]
M. A. Khamis, R. R. Curtin, B. Moseley, H. Q. Ngo, X. Nguyen, D. Olteanu, and M. Schleich. Functional aggregate queries with additive inequalities. ACM Transactions on Database Systems, 45(4), dec 2020.
[13]
P. Koutris, T. Milo, S. Roy, and D. Suciu. Answering conjunctive queries with inequalities. Theory of Computing Systems, 61:2--30, 2017.
[14]
D. Marx. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. Journal of the ACM, 60(6), nov 2013.
[15]
H. Q. Ngo, E. Porat, C. R´e, and A. Rudra. Worst-case optimal join algorithms: [extended abstract]. In PODS, page 37--48. ACM, 2012.
[16]
M. Patrascu. Towards polynomial lower bounds for dynamic problems. In STOC, page 603--610. ACM, 2010.
[17]
N. Tziavelis, W. Gatterbauer, and M. Riedewald. Beyond equi-joins: Ranking, enumeration and factorization. In VLDB, volume 14, page 2599--2612. VLDB Endowment, 2021.
[18]
Q. Wang and K. Yi. Conjunctive queries with comparisons. In SIGMOD, pages 108--121. ACM, 2022.
[19]
D. E. Willard. An Algorithm for Handling Many Relational Calculus Queries Efficiently. JCSS, 65(2):295--331, Sept. 2002.
[20]
M. Yannakakis. Algorithms for acyclic database schemes. In VLDB, page 82--94. VLDB Endowment, 1981.
[21]
C. T. Yu and M. Z. Ozsoyoglu. An algorithm for tree-query membership of a distributed query. In COMPSAC, pages 306--312. IEEE, 1979.
Recommendations
Conjunctive Queries with Comparisons
SIGMOD '22: Proceedings of the 2022 International Conference on Management of DataConjunctive queries with predicates in the form of comparisons that span multiple relations have regained interest recently, due to their relevance in OLAP queries, spatiotemporal databases, and machine learning over relational data. The standard ...
Equivalence and minimization of conjunctive queries under combined semantics
ICDT '12: Proceedings of the 15th International Conference on Database TheoryThe problems of query containment, equivalence, and minimization are fundamental problems in the context of query processing and optimization. In their classic work [2] published in 1977, Chandra and Merlin solved the three problems for the language of ...
Combined-semantics equivalence of conjunctive queries
Query containment and equivalence are fundamental problems in the context of query processing and optimization. In this paper, we consider combined-semantics equivalence of conjunctive (CQ) queries. The combined-semantics formalism 10,11 generalizes the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2023
118 pages
ISSN:0163-5808
DOI:10.1145/3604437
- Editors:
- Rada Chirkova,
- Vanessa Braganholo,
- Wim Martens,
- Manos Athanassoulis,
- Marcelo Arenas,
- Marianne Winslett,
- Susan B. Davidson,
- Lyublena Antova,
- Aaron J. Elmore,
- Kyriakos Mouratidis,
- Dan Olteanu,
- Immanuel Trummer,
- Yannis Velegrakis,
- Renata Borovica-Gajic,
- Tamer Özsu,
- Pınar Tözün,
- Wook-Shin Han,
- Kenneth Ross,
- Alfons Kemper,
- Samuel Madden
Copyright © 2023 Copyright is held by the owner/author(s).
Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 June 2023
Published in SIGMOD Volume 52, Issue 1
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 56Total Downloads
- Downloads (Last 12 months)25
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024
Other Metrics
Citations
Cited By
View all- 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
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in