Algorithms for Optimizing Acyclic Queries

doi:10.4230/LIPIcs.ICDT.2026.17

Algorithms for Optimizing Acyclic Queries

2026-01-01

0

PRE

AI

DOI：10.4230/LIPIcs.ICDT.2026.17

原文链接

原文求助

摘要

En 中文

关于查询优化的研究主要集中于二元连接算法，如哈希连接和排序合并连接。然而，近年来对理论最优算法的兴趣日益增长，特别是Yannakakis算法。这些算法依赖于连接树，这与二元连接的操作树不同，并需要新的优化技术。我们提出了三种针对无环查询构建连接树的方法。首先，我们给出一个算法，通过编辑操作在线性时间内以摊还常数延迟枚举无环查询的所有连接树，这构成了无环连接基于成本的优化器的基础。其次，我们证明Tarjan和Yannakakis提出的最大基数搜索算法可以构建任何Berge无环查询的唯一最浅连接树，从而支持大型连接查询的并行执行。最后，我们证明Hu等人提出的一个简单算法可以将无环查询的任何连通左深线性计划转换为连接树，允许复用为二元连接开发的优化器。

Keyword:

Query Optimization

Join Trees

Enumeration

Algorithms for Optimizing Acyclic Queries

摘要

期刊

机构

引用论文