データベース理論における扱いやすい回路

本研究では、データベース理論が知識コンパイルからの扱いやすい回路クラスをどのように使用しているかをレビューします。関連するクエリ評価タスクと扱いやすい回路の概念を提示します。次に、これらの扱いやすい回路がデータベースタスクにどのように役立つかを示します。まず、ブーリアンの出所と集約タスク、特に確率的クエリ評価への応用に焦点を当てます。これを木に対するモナディック第二次（MSO）クエリおよび安全な結合クエリ（CQ）と結合クエリの和（UCQ）について研究します。さらに、クエリの回答の回路表現と、その列挙タスクに対する応用を研究します：ブーリアン設定（MSOの場合）および多値設定（CQおよびUCQの場合）の両方で。