Efficient Evaluation of Arbitrary Relational Calculus Queries
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Efficient Evaluation of Arbitrary Relational Calculus Queries. / Raszyk, Martin; Basin, David; Krstić, Srdan; Trayte, Dmitriy.
I: Logical Methods in Computer Science, Bind 19, Nr. 4, 2023.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Efficient Evaluation of Arbitrary Relational Calculus Queries
AU - Raszyk, Martin
AU - Basin, David
AU - Krstić, Srdan
AU - Trayte, Dmitriy
N1 - Publisher Copyright: © 2023, Logical Methods in Computer Science. All rights reserved.
PY - 2023
Y1 - 2023
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
U2 - 10.46298/lmcs-19(4:38)2023
DO - 10.46298/lmcs-19(4:38)2023
M3 - Journal article
AN - SCOPUS:85180616843
VL - 19
JO - Logical Methods in Computer Science
JF - Logical Methods in Computer Science
SN - 1860-5974
IS - 4
ER -
ID: 378187919