一句话：提出将任意关系演算查询翻译为两个安全范围查询，再转成SQL，从而借助标准DBMS高效求值并改进复杂度。
关系演算（RC）是一种简洁的声明式查询语言，但现有求值方法效率不高，且常偏离数据库管理系统中基于有限表的成熟算法。本文提出一种新翻译，在假设无限域的前提下，将任意RC查询转换为两个安全范围查询：第一个是封闭查询，用于刻画原查询的相对安全性，即在给定数据库上原查询是否求值为有限关系；第二个安全范围查询在原查询相对安全时与之等价。作者进一步将该翻译与其他标准翻译组合，最终得到两个SQL查询，从而可用标准DBMS执行任意RC查询。理论分析表明该翻译相比已有方法具有更优的时间复杂度，并在真实与合成实验中经验证实了其效率。
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.
@article{paperbot2156,
title = {Efficient Evaluation of Arbitrary Relational Calculus Queries},
author = {Martin Raszyk and David Basin and Srđan Krstić and Dmitriy Traytel},
journal = {Logical Methods in Computer Science},
volume = {Volume 19, Issue 4},
year = {2023},
doi = {10.46298/lmcs-19(4:38)2023}
}