论文标题
有效评估任意关系微积分查询
Efficient Evaluation of Arbitrary Relational Calculus Queries
论文作者
论文摘要
关系演算（RC）是一种简洁的声明性查询语言。但是，现有的RC查询评估方法效率低下，并且通常基于数据库管理系统中使用的有限表偏离已建立的算法。我们将任意RC查询的新翻译设计为两个安全范围的查询，为此保证了查询评估结果的有限性。假设一个无限域，两个查询具有以下含义：第一个查询是关闭的，并且表征了原始查询的相对安全性，即是否给定固定数据库，原始查询对有限的关系评估。如果后者相对安全，则第二个安全范围查询等效于原始查询。我们将翻译与其他标准的翻译构成，最终获得两个SQL查询。这使我们可以使用标准数据库管理系统来评估任意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.
