Efficient Evaluation of Arbitrary Relational Calculus Queries

DOI10.46298/LMCS-19(4:38)2023MaRDI QIDQ6137874zbMATH OpenFDO

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

Publication date 16 January 2024

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2210.09964

zbMATH Keywords

relational calculusquery translationrelative safetysafe range

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

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.

Recommendations

• Domain independence and the relational calculus
• scientific article; zbMATH DE number 219206
• Safety, domain independence and translation of complex value database queries
• Finite queries do not have effective syntax.
• An algorithm for handling many relational calculus queries efficiently.

Cites work

• scientific article; zbMATH DE number 2090292 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• scientific article; zbMATH DE number 1424030 (Why is no real title available?)
• scientific article; zbMATH DE number 3057871 (Why is no real title available?)
• Domain independence and the relational calculus
• Elements of finite model theory.
• Finite presentations of infinite structures: Automata and interpretations
• Introduction to constraint databases
• Monitoring metric first-order temporal properties
• Relational queries over interpreted structures
• Safety, domain independence and translation of complex value database queries
• The Recursive Unsolvability of the Decision Problem for the Class of Definite Formulas
• The decision problem for database dependencies

Cited in

(1)

• Computing infinite relations using finite expressions: A new approach to the safety issue in relational databases

This page was built for publication: Efficient Evaluation of Arbitrary Relational Calculus Queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6137874)