Efficient Evaluation of Arbitrary Relational Calculus Queries
Authors:
- Martin RaszykMRMartin Raszyk
- David BasinDBDavid Basin
- Srđan KrstićSKSrđan Krstić
- Dmitriy TraytelDTDmitriy Traytel
Open Access
- 22 December 2023
- journal article
- research article
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 19, Is (4)
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.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Safety, domain independence and translation of complex value database queriesInformation Sciences, 2008
- Finite Presentations of Infinite Structures: Automata and InterpretationsTheory of Computing Systems, 2004
- Elements of Finite Model Theory2004
- DDDLIB: A Library for Solving Quantified Difference Inequalities2002
- Introduction to Constraint Databases2002
- Difference Decision Diagrams1999
- Implementing temporal integrity constraints using an active DBMSIEEE Transactions on Knowledge and Data Engineering, 1995
- Domain independence and the relational calculusActa Informatica, 1994
- ON SAFETY, DOMAIN INDEPENDENCE, AND CAPTURABILITY OF DATABASE QUERIES* (Preliminary Report)*Research sponsored in part by the NSF grant DCR-8603676.1988
- The decision problem for database dependenciesInformation Processing Letters, 1981