Size Bound-Adorned Datalog

doi:10.1145/3801893

Size Bound-Adorned Datalog

2026-05-01

0

PRE

AI

F

Fattebert, Christian *

DOI：10.1145/3801893

原文求助

摘要

En 中文

我们介绍了EDB有界Datalog，一种用于推导Datalog中中间结果大小的上界和递归查询的渐近复杂性的框架。我们提出了一种算法，该算法针对任意Datalog程序，构造一个EDB有界Datalog程序，其中每条规则都附加了一个（非递归的）合取查询，该查询包含规则的结果，从而作为上界。通过这些附加信息，我们基于（整数或分数）边覆盖宽度定义了一个宽度概念。通过附加信息和宽度度量，对于每个IDB谓词，在给定固定程序结构的情况下，我们得到了其大小的最坏情况上界，这些上界是输入数据大小的多项式。此外，利用这些大小上界，我们还推导出评估整个程序的固定参数可处理、输出敏感的渐近复杂度上界。另外，通过调整我们的框架，我们得到了一个Datalog有界性的半判定过程，该过程能够高效地将大多数实际的有限程序重写为非递归的等价程序。

Keyword:

Datalog

Cost-based query optimization

Result size estimation

Size Bound-Adorned Datalog

摘要

期刊

机构

引用论文