Practical Relational Calculus Query Evaluation
OPEN ACCESS
Loading...
Author / Producer
Date
2022-03
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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’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.
Permanent link
Publication status
published
External links
Book title
25th International Conference on Database Theory (ICDT 2022)
Volume
220
Pages / Article No.
11
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
25th International Conference on Database Theory (ICDT 2022)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Relational calculus; Relative safety; Safe-range; Query translation
Organisational unit
03634 - Basin, David / Basin, David