Practical Relational Calculus Query Evaluation

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

  • Fulltwxt

    Forlagets udgivne version, 989 KB, PDF-dokument

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.

OriginalsprogEngelsk
Titel25th International Conference on Database Theory, ICDT 2022
RedaktørerDan Olteanu, Nils Vortmeier
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdato2022
Sider1-21
Artikelnummer11
ISBN (Elektronisk)9783959772235
DOI
StatusUdgivet - 2022
Begivenhed25th International Conference on Database Theory, ICDT 2022 - Virtual, Edinburgh, Storbritannien
Varighed: 29 mar. 20221 apr. 2022

Konference

Konference25th International Conference on Database Theory, ICDT 2022
LandStorbritannien
ByVirtual, Edinburgh
Periode29/03/202201/04/2022
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind220
ISSN1868-8969

Bibliografisk note

Publisher Copyright:
© Martin Raszyk, David Basin, Srđan Krstić, and Dmitriy Traytel;

Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk


Ingen data tilgængelig

ID: 307373732