Efficient Evaluation of Arbitrary Relational Calculus Queries

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Efficient Evaluation of Arbitrary Relational Calculus Queries. / Raszyk, Martin; Basin, David; Krstić, Srdan; Trayte, Dmitriy.

In: Logical Methods in Computer Science, Vol. 19, No. 4, 2023.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Raszyk, M, Basin, D, Krstić, S & Trayte, D 2023, 'Efficient Evaluation of Arbitrary Relational Calculus Queries', Logical Methods in Computer Science, vol. 19, no. 4. https://doi.org/10.46298/lmcs-19(4:38)2023

APA

Raszyk, M., Basin, D., Krstić, S., & Trayte, D. (2023). Efficient Evaluation of Arbitrary Relational Calculus Queries. Logical Methods in Computer Science, 19(4). https://doi.org/10.46298/lmcs-19(4:38)2023

Vancouver

Raszyk M, Basin D, Krstić S, Trayte D. Efficient Evaluation of Arbitrary Relational Calculus Queries. Logical Methods in Computer Science. 2023;19(4). https://doi.org/10.46298/lmcs-19(4:38)2023

Author

Raszyk, Martin ; Basin, David ; Krstić, Srdan ; Trayte, Dmitriy. / Efficient Evaluation of Arbitrary Relational Calculus Queries. In: Logical Methods in Computer Science. 2023 ; Vol. 19, No. 4.

Bibtex

@article{a995b04f983d40dcb500bc79e29fe6c1,

title = "Efficient Evaluation of Arbitrary Relational Calculus Queries",

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{\textquoteright}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{\textquoteright}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.",

keywords = "query translation, Relational calculus, relative safety, safe range",

author = "Martin Raszyk and David Basin and Srdan Krsti{\'c} and Dmitriy Trayte",

year = "2023",

doi = "10.46298/lmcs-19(4:38)2023",

language = "English",

volume = "19",

journal = "Logical Methods in Computer Science",

issn = "1860-5974",

publisher = "International Federation for Computational Logic",

number = "4",

}

RIS

TY - JOUR

T1 - Efficient Evaluation of Arbitrary Relational Calculus Queries

AU - Raszyk, Martin

AU - Basin, David

AU - Krstić, Srdan

AU - Trayte, Dmitriy

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

Department of Computer Science