Tractable Circuits in Database Theory

这项工作回顾了数据库理论如何使用可处理电路类别来进行知识编译。我们介绍了相关的查询评估任务和可处理电路的概念。然后，我们展示了如何使用这些可处理电路来处理数据库任务。我们首先关注布尔来源及其在聚合任务中的应用，特别是概率查询评估。我们研究了这些任务在树形结构的单调二阶（MSO）查询和安全合取查询（CQs）以及合取查询的并集（UCQs）中的应用。我们还研究了查询答案的电路表示及其在枚举任务中的应用：在布尔设置中（对于MSO）和多值设置中（对于CQs和UCQs）。

本文旨在研究数据库理论如何使用知识编译中的可处理电路类来解决查询评估任务，并探讨其在布尔证明和枚举任务中的应用。

本文提出了可处理电路类的概念，将其应用于布尔证明和枚举任务中，特别是在树上的Monadic Second Order（MSO）查询和安全联合查询（CQs）和联合联合查询（UCQs）中。

本文探讨了电路表示法的查询答案和枚举任务，并提供了实验和数据集的详细信息。这篇论文的亮点在于提出了一种新的解决方案，并将其应用于数据库理论中。此外，该论文还提供了开源代码和进一步研究的建议。

近期的相关研究包括：1. Efficient Query Evaluation on Probabilistic Databases；2. Knowledge Compilation Meets Communication Complexity；3. The Complexity of Circuit-to-Circuit Functions