Martin Raszyk ; David Basin ; Srđan Krstić ; Dmitriy Traytel - Efficient Evaluation of Arbitrary Relational Calculus Queries

lmcs:10182 - Logical Methods in Computer Science, December 22, 2023, Volume 19, Issue 4 - https://doi.org/10.46298/lmcs-19(4:38)2023
Efficient Evaluation of Arbitrary Relational Calculus QueriesArticle

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

    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.


    Volume: Volume 19, Issue 4
    Published on: December 22, 2023
    Accepted on: October 5, 2023
    Submitted on: October 21, 2022
    Keywords: Computer Science - Databases,Computer Science - Logic in Computer Science

    Consultation statistics

    This page has been seen 1098 times.
    This article's PDF has been downloaded 292 times.