Document Open Access Logo

Practical Relational Calculus Query Evaluation

Authors Martin Raszyk , David Basin , Srđan Krstić , Dmitriy Traytel

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2022.11.pdf
  • Filesize: 0.96 MB
  • 21 pages

Document Identifiers

Author Details

Martin Raszyk
  • Department of Computer Science, ETH Zürich, Switzerland
David Basin
  • Department of Computer Science, ETH Zürich, Switzerland
Srđan Krstić
  • Department of Computer Science, ETH Zürich, Switzerland
Dmitriy Traytel
  • Department of Computer Science, University of Copenhagen, Denmark

Cite As Get BibTex

Martin Raszyk, David Basin, Srđan Krstić, and Dmitriy Traytel. Practical Relational Calculus Query Evaluation. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICDT.2022.11

Abstract

The relational calculus (RC) is a concise, declarative query language. However, existing RC query evaluation approaches are inefficient and often deviate from established algorithms based on finite tables used in database management systems. We devise a new translation of an arbitrary RC query into two safe-range queries, for which the finiteness of the query’s evaluation result is guaranteed. Assuming an infinite domain, the two queries have the following meaning: The first is closed and characterizes the original query’s relative safety, i.e., whether given a fixed database, the original query evaluates to a finite relation. The second safe-range query is equivalent to the original query, if the latter is relatively safe. We compose our translation with other, more standard ones to ultimately obtain two SQL queries. This allows us to use standard database management systems to evaluate arbitrary RC queries. We show that our translation improves the time complexity over existing approaches, which we also empirically confirm in both realistic and synthetic experiments.

Subject Classification

ACM Subject Classification
  • Theory of computation → Database query languages (principles)
Keywords
  • Relational calculus
  • relative safety
  • safe-range
  • query translation

Metrics

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

Related Versions

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/.
  2. Alfred K. Ailamazyan, Mikhail M. Gilula, Alexei P. Stolboushkin, and Grigorii F. Schwartz. Reduction of a relational model with infinite domains to the case of finite domains. Doklady Akademii Nauk SSSR, 286(2):308-311, 1986. URL: http://mi.mathnet.ru/dan47310.
  3. Arnon Avron and Yoram Hirshfeld. On first order database query languages. In LICS, July 15-18, 1991, Amsterdam, The Netherlands, pages 226-231. IEEE Computer Society, 1991. URL: https://doi.org/10.1109/LICS.1991.151647.
  4. David A. Basin, Felix Klaedtke, Samuel Müller, and Eugen Zalinescu. Monitoring metric first-order temporal properties. J. ACM, 62(2):15:1-15:45, 2015. URL: https://doi.org/10.1145/2699444.
  5. Michael Benedikt and Leonid Libkin. Relational queries over interpreted structures. J. ACM, 47(4):644-680, 2000. URL: https://doi.org/10.1145/347476.347477.
  6. Achim Blumensath and Erich Grädel. Finite presentations of infinite structures: Automata and interpretations. Theory Comput. Syst., 37(6):641-674, 2004. URL: https://doi.org/10.1007/s00224-004-1133-y.
  7. Sagar Chaki, Arie Gurfinkel, and Ofer Strichman. Decision diagrams for linear arithmetic. In FMCAD, 15-18 November 2009, Austin, Texas, USA, pages 53-60. IEEE, 2009. URL: https://doi.org/10.1109/FMCAD.2009.5351143.
  8. Jan Chomicki and David Toman. Implementing temporal integrity constraints using an active DBMS. IEEE Trans. Knowl. Data Eng., 7(4):566-582, 1995. URL: https://doi.org/10.1109/69.404030.
  9. Jens Claußen, Alfons Kemper, Guido Moerkotte, and Klaus Peithner. Optimizing queries with universal quantification in object-oriented and object-relational databases. In Matthias Jarke, Michael J. Carey, Klaus R. Dittrich, Frederick H. Lochovsky, Pericles Loucopoulos, and Manfred A. Jeusfeld, editors, VLDB, August 25-29, 1997, Athens, Greece, pages 286-295. Morgan Kaufmann, 1997. URL: http://www.vldb.org/conf/1997/P286.PDF.
  10. E. F. Codd. Relational completeness of data base sublanguages. Research Report / RJ / IBM / San Jose, California, RJ987, 1972. Google Scholar
  11. Erling Ellingsen. Regex golf, 2013. URL: https://alf.nu/RegexGolf.
  12. Martha Escobar-Molano, Richard Hull, and Dean Jacobs. Safety and translation of calculus queries with scalar functions. In Catriel Beeri, editor, PODS, May 25-28, 1993, Washington, DC, USA, pages 253-264. ACM Press, 1993. URL: https://doi.org/10.1145/153850.153909.
  13. Allen Van Gelder and Rodney W. Topor. Safety and correct translation of relational calculus formulas. In Moshe Y. Vardi, editor, PODS, March 23-25, 1987, San Diego, California, USA, pages 313-327. ACM, 1987. URL: https://doi.org/10.1145/28659.28693.
  14. Allen Van Gelder and Rodney W. Topor. Safety and translation of relational calculus queries. ACM Trans. Database Syst., 16(2):235-278, 1991. URL: https://doi.org/10.1145/114325.103712.
  15. Richard Hull and Jianwen Su. Domain independence and the relational calculus. Acta Informatica, 31(6):513-524, 1994. URL: https://doi.org/10.1007/BF01213204.
  16. Michael Kifer. On safety, domain independence, and capturability of database queries (preliminary report). In Catriel Beeri, Joachim W. Schmidt, and Umeshwar Dayal, editors, Proceedings of the Third International Conference on Data and Knowledge Bases: Improving Usability and Responsiveness, June 28-30, 1988, Jerusalem, Israel, pages 405-415. Morgan Kaufmann, 1988. URL: https://doi.org/10.1016/b978-1-4832-1313-2.50037-8.
  17. Nils Klarlund and Anders Møller. MONA v1.4 User Manual. BRICS, Department of Computer Science, University of Aarhus, January 2001. URL: http://www.brics.dk/mona/.
  18. Leonid Libkin. Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2004. URL: https://doi.org/10.1007/978-3-662-07003-1.
  19. Hong-Cheu Liu, Jeffrey Xu Yu, and Weifa Liang. Safety, domain independence and translation of complex value database queries. Inf. Sci., 178(12):2507-2533, 2008. URL: https://doi.org/10.1016/j.ins.2008.02.005.
  20. Jesper B. Møller. DDDLIB: A library for solving quantified difference inequalities. In Andrei Voronkov, editor, CADE, July 27-30, 2002, Copenhagen, Denmark, volume 2392 of Lecture Notes in Computer Science, pages 129-133. Springer, 2002. URL: https://doi.org/10.1007/3-540-45620-1_9.
  21. Jesper B. Møller, Jakob Lichtenberg, Henrik Reif Andersen, and Henrik Hulgaard. Difference decision diagrams. In Jörg Flum and Mario Rodríguez-Artalejo, editors, CSL, September 20-25, 1999, Madrid, Spain, volume 1683 of Lecture Notes in Computer Science, pages 111-125. Springer, 1999. URL: https://doi.org/10.1007/3-540-48168-0_9.
  22. Hung Q. Ngo, Christopher Ré, and Atri Rudra. Skew strikes back: new developments in the theory of join algorithms. SIGMOD Rec., 42(4):5-16, 2013. URL: https://doi.org/10.1145/2590989.2590991.
  23. Jianmo Ni, Jiacheng Li, and Julian J. McAuley. Justifying recommendations using distantly-labeled reviews and fine-grained aspects. In Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan, editors, EMNLP, November 3-7, 2019, Hong Kong, China, pages 188-197. Association for Computational Linguistics, 2019. URL: https://doi.org/10.18653/v1/D19-1018.
  24. Robert A. Di Paola. The recursive unsolvability of the decision problem for the class of definite formulas. J. ACM, 16(2):324-327, 1969. URL: https://doi.org/10.1145/321510.321524.
  25. Martin Raszyk, David Basin, Srđjan Krstić, and Dmitriy Traytel. Implementation, evaluation, and extended report associated with this paper, 2022. URL: https://github.com/rc2sql/rc2sql.
  26. Peter Z. Revesz. Introduction to Constraint Databases. Texts in Computer Science. Springer, 2002. URL: https://doi.org/10.1007/b97430.
  27. Boris A Trakhtenbrot. Impossibility of an algorithm for the decision problem in finite classes. Doklady Akademii Nauk SSSR, 70(4):569-572, 1950. Google Scholar
  28. Moshe Y. Vardi. The decision problem for database dependencies. Inf. Process. Lett., 12(5):251-254, 1981. URL: https://doi.org/10.1016/0020-0190(81)90025-9.
  29. Moshe Y. Vardi. The complexity of relational query languages (extended abstract). In Harry R. Lewis, Barbara B. Simons, Walter A. Burkhard, and Lawrence H. Landweber, editors, STOC, May 5-7, 1982, San Francisco, California, USA, pages 137-146. ACM, 1982. URL: https://doi.org/10.1145/800070.802186.
  30. Jun Yang. radb, 2019. URL: https://github.com/junyang/radb.
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 About DROPS Imprint Privacy Contact