Document Open Access Logo

Enumeration Algorithms for Conjunctive Queries with Projection

Authors Shaleen Deep, Xiao Hu, Paraschos Koutris

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2021.14.pdf
  • Filesize: 3.38 MB
  • 17 pages

Document Identifiers

Author Details

Shaleen Deep
  • Department of Computer Sciences, University of Wisconsin-Madison, Madison, WI, USA
Xiao Hu
  • Department of Computer Sciences, Duke University, Durham, NC, USA
Paraschos Koutris
  • Department of Computer Sciences, University of Wisconsin-Madison, Madison, WI, USA

Funding

This research was supported in part by National Science Foundation grants CRII-1850348 and III-1910014.

Acknowledgements

We would like to thank the anonymous reviewers for their careful reading and valuable comments that contributed greatly in improving the manuscript.

Cite AsGet BibTex

Shaleen Deep, Xiao Hu, and Paraschos Koutris. Enumeration Algorithms for Conjunctive Queries with Projection. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICDT.2021.14

Abstract

We investigate the enumeration of query results for an important subset of CQs with projections, namely star and path queries. The task is to design data structures and algorithms that allow for efficient enumeration with delay guarantees after a preprocessing phase. Our main contribution is a series of results based on the idea of interleaving precomputed output with further join processing to maintain delay guarantees, which maybe of independent interest. In particular, we design combinatorial algorithms that provide instance-specific delay guarantees in linear preprocessing time. These algorithms improve upon the currently best known results. Further, we show how existing results can be improved upon by using fast matrix multiplication. We also present {new} results involving tradeoff between preprocessing time and delay guarantees for enumeration of path queries that contain projections. CQs with projection where the join attribute is projected away is equivalent to boolean matrix multiplication. Our results can therefore be also interpreted as sparse, output-sensitive matrix multiplication with delay guarantees.

Subject Classification

ACM Subject Classification
  • Theory of computation → Database theory
Keywords
  • Query result enumeration
  • joins
  • ranking

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Mahmoud Abo Khamis, Hung Q Ngo, and Dan Suciu. What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 429-444, 2017. Google Scholar
  2. Rasmus Resen Amossen and Rasmus Pagh. Faster join-projects and sparse matrix multiplications. In Proceedings of the 12th International Conference on Database Theory, pages 121-126. ACM, 2009. Google Scholar
  3. Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. On acyclic conjunctive queries and constant delay enumeration. In International Workshop on Computer Science Logic, pages 208-222. Springer, 2007. Google Scholar
  4. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering conjunctive queries under updates. In proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems, pages 303-318. ACM, 2017. Google Scholar
  5. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering fo+ mod queries under updates on bounded degree databases. ACM Transactions on Database Systems (TODS), 43(2):7, 2018. Google Scholar
  6. Johann Brault-Baron. De la pertinence de l’énumération: complexité en logiques propositionnelle et du premier ordre. PhD thesis, Université de Caen, 2013. Google Scholar
  7. Amrita Roy Chowdhury, Theodoros Rekatsinas, and Somesh Jha. Data-dependent differentially private parameter learning for directed graphical models. In International Conference on Machine Learning, pages 1939-1951. PMLR, 2020. Google Scholar
  8. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Chapter 8.2, Introduction to algorithms. MIT press, 2009. Google Scholar
  9. Shaleen Deep, Xiao Hu, and Paraschos Koutris. Fast join project query evaluation using matrix multiplication. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 1213-1223, 2020. Google Scholar
  10. Shaleen Deep, Xiao Hu, and Paraschos Koutris. Enumeration algorithms for conjunctive queries with projection. arXiv preprint arXiv:2101.03712, 2021. Google Scholar
  11. Shaleen Deep and Paraschos Koutris. Compressed representations of conjunctive query results. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 307-322. ACM, 2018. Google Scholar
  12. Shaleen Deep and Paraschos Koutris. Ranked enumeration of conjunctive query results. To appear in Joint 2021 EDBT/ICDT Conferences, ICDT '21 Proceedings, 2021. Google Scholar
  13. François Le Gall and Florent Urrutia. Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1029-1046. SIAM, 2018. Google Scholar
  14. Georg Gottlob, Gianluigi Greco, and Francesco Scarcello. Treewidth and hypertree width. Tractability: Practical Approaches to Hard Problems, 1, 2014. Google Scholar
  15. Gianluigi Greco and Francesco Scarcello. Structural tractability of enumerating csp solutions. Constraints, 18(1):38-74, 2013. Google Scholar
  16. John E Hopcroft, Jeffrey D Ullman, and AV Aho. The design and analysis of computer algorithms, 1975. Google Scholar
  17. Ahmet Kara, Hung Q Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Counting triangles under updates in worst-case optimal time. In 22nd International Conference on Database Theory, 2019. Google Scholar
  18. Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Trade-offs in static and dynamic evaluation of hierarchical queries. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 375-392, 2020. Google Scholar
  19. Wojciech Kazana. Query evaluation with constant delay. PhD thesis, ENS Cachan, 2013. Google Scholar
  20. Hung Q Ngo, Ely Porat, Christopher Ré, and Atri Rudra. Worst-case optimal join algorithms. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems, pages 37-48. ACM, 2012. Google Scholar
  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. URL: https://doi.org/10.1145/2590989.2590991.
  22. Dan Olteanu and Maximilian Schleich. Factorized databases. ACM SIGMOD Record, 45(2):5-16, 2016. Google Scholar
  23. Dan Olteanu and Jakub Závodny. Size bounds for factorised representations of query results. ACM Transactions on Database Systems (TODS), 40(1):1-44, 2015. Google Scholar
  24. Mark H Overmars and Jan Van Leeuwen. Dynamization of decomposable searching problems yielding good worst-case bounds. In Theoretical Computer Science, pages 224-233. Springer, 1981. Google Scholar
  25. Anna Pagh and Rasmus Pagh. Scalable computation of acyclic joins. In Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 225-232, 2006. Google Scholar
  26. Amrita Roy Chowdhury, Chenghong Wang, Xi He, Ashwin Machanavajjhala, and Somesh Jha. Crypt?: Crypto-assisted differential privacy on untrusted servers. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 603-619, 2020. Google Scholar
  27. Luc Segoufin. Constant delay enumeration for conjunctive queries. SIGMOD Record, 44(1):10-17, 2015. URL: https://doi.org/10.1145/2783888.2783894.
  28. Luc Segoufin. Constant delay enumeration for conjunctive queries. ACM SIGMOD Record, 44(1):10-17, 2015. Google Scholar
  29. Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch. Probabilistic databases, synthesis lectures on data management. Morgan & Claypool, 2011. Google Scholar
  30. Konstantinos Xirogiannopoulos and Amol Deshpande. Extracting and analyzing hidden graphs from relational databases. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 897-912. ACM, 2017. Google Scholar
  31. Konstantinos Xirogiannopoulos, Udayan Khurana, and Amol Deshpande. Graphgen: Exploring interesting graphs in relational data. Proceedings of the VLDB Endowment, 8(12):2032-2035, 2015. Google Scholar
  32. Konstantinos Xirogiannopoulos, Virinchi Srinivas, and Amol Deshpande. Graphgen: Adaptive graph processing using relational databases. In Proceedings of the Fifth International Workshop on Graph Data-management Experiences & Systems, GRADES'17, pages 9:1-9:7, New York, NY, USA, 2017. ACM. URL: https://doi.org/10.1145/3078447.3078456.
  33. Mihalis Yannakakis. Algorithms for acyclic database schemes. In VLDB, volume 81, pages 82-94, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact