1 Search Results for "Krstić, Srđan"

Practical Relational Calculus Query Evaluation

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

Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)

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.

Cite as

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)

Copy BibTex To Clipboard

  author =	{Raszyk, Martin and Basin, David and Krsti\'{c}, Sr{\d}an and Traytel, Dmitriy},
  title =	{{Practical Relational Calculus Query Evaluation}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{11:1--11:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.11},
  URN =		{urn:nbn:de:0030-drops-158857},
  doi =		{10.4230/LIPIcs.ICDT.2022.11},
  annote =	{Keywords: Relational calculus, relative safety, safe-range, query translation}
  • Refine by Author
  • 1 Basin, David
  • 1 Krstić, Srđan
  • 1 Raszyk, Martin
  • 1 Traytel, Dmitriy

  • Refine by Classification
  • 1 Theory of computation → Database query languages (principles)

  • Refine by Keyword
  • 1 Relational calculus
  • 1 query translation
  • 1 relative safety
  • 1 safe-range

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail