Practical Relational Calculus Query Evaluation
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Practical Relational Calculus Query Evaluation. / Raszyk, Martin; Basin, David; Krstić, Srđan; Traytel, Dmitriy.
25th International Conference on Database Theory, ICDT 2022. ed. / Dan Olteanu; Nils Vortmeier. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. p. 1-21 11 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 220).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Practical Relational Calculus Query Evaluation
AU - Raszyk, Martin
AU - Basin, David
AU - Krstić, Srđan
AU - Traytel, Dmitriy
N1 - Publisher Copyright: © Martin Raszyk, David Basin, Srđan Krstić, and Dmitriy Traytel;
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
KW - query translation
KW - Relational calculus
KW - relative safety
KW - safe-range
UR - http://www.scopus.com/inward/record.url?scp=85127898861&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICDT.2022.11
DO - 10.4230/LIPIcs.ICDT.2022.11
M3 - Article in proceedings
AN - SCOPUS:85127898861
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 21
BT - 25th International Conference on Database Theory, ICDT 2022
A2 - Olteanu, Dan
A2 - Vortmeier, Nils
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 25th International Conference on Database Theory, ICDT 2022
Y2 - 29 March 2022 through 1 April 2022
ER -
ID: 307373732