Multiset semantics in SPARQL, Relational Algebra and Datalog

Angels、Gutierrez、Hernández による論文「Multiset semantics in SPARQL, Relational Algebra and Datalog*」の詳細な技術的サマリーを以下に示す。

1. 問題提起

本論文は、RDF データベース向けのクエリ言語であるSPARQLの文脈におけるマルチセット（バッグ）セマンティクスの理論的基盤に取り組んでいる。マルチセット（重複要素を許容する集合）は、集約や高価な重複除去の回避といった実用的な必要性から、SQL などの現代のデータベースシステムでは標準的な機能となっているが、宣言型クエリ言語におけるその理論的扱いは複雑である。

特定された主な課題は以下の通りである：

• セマンティクスの変動性: 集合ベースの演算子（和集合、共通部分、差集合）をマルチセットに拡張する方法について、単一の合意が存在しない。異なる演算子が存在する（例：算術和集合対最大和集合、算術差集合対存在否定）。
• 表現力のギャップ: SPARQL がサポートする特定のマルチセット演算子の部分集合（AND、UNION、FILTER、EXCEPT、SELECT）が、最適かつ一貫した集合を構成するかどうかは不明である。
• 形式的同等性の欠如: SPARQL のマルチセットセマンティクスが、確立された形式体系である関係代数およびDatalogと比較して、その表現力を厳密に特徴づける必要がある。

2. 手法

著者らは、マルチセットセマンティクス下における 3 つの異なる形式体系間の表現的同等性を確立するために、比較形式的分析を採用している：

1. SPARQL: 具体的には、AND、UNION、FILTER、EXCEPT、SELECT を含む「関係的核心」フラグメント。
2. NRMD¬（安全否定付き非再帰マルチセット Datalog）: 証明論的セマンティクス（導出木の計数）に基づき、マルチセットと安全否定をサポートするように拡張された Datalog の論理形式体系。
3. MRA（マルチセット関係代数）: 標準的な関係代数をマルチセット演算子（射影、選択、自然結合、算術和集合、フィルタ差集合）で拡張した代数形式体系。

核心的アプローチ:
著者らは、これら言語間のシミュレーション（変換）を定義することで、同等の表現力を持つことを証明する。これには、各言語のペア $(L_1, L_2)$ に対して 3 つの関数を定義することが含まれる：

• $g$: データベース変換（データ構造の変換）。
• $f$: クエリ変換（クエリ構文の変換）。
• $h$: 答え変換（結果集合の変換）。

彼らは $L_1$ が $L_2$ に含まれ、かつその逆も成り立つことを証明し、$L_1 \equiv L_2$ を確立する。

対処された主要な技術的課題:

• Null/未束縛値の処理: SPARQL のマッピングは部分領域（未束縛変数）を持つが、関係タプルと Datalog 置換は全領域である。著者らは、対象言語における未束縛値を表す特別な定数（$\bot$ または NULL）を導入する。
• フィルタにおける三値論理: SPARQL はフィルタに対して三値論理（真、偽、エラー）を使用する。著者らは、バッグセマンティクス下でフィルタ内の OR と NOT を処理するための特定の変換規則を開発し、「エラー」条件が正しく伝播し、基数が誤って増大しないことを保証した。
• 正規化: 変換前にサブパターンの変数が適切にスコープされるように、SPARQL パターンと Datalog ルールのための正規形を定義する。

3. 主要な貢献

A. 形式体系の定義

• NRMD¬: 著者らは、マルチセットと安全否定をサポートする Datalog のバージョンを定義し、SPARQL の能力に一致させるために非再帰プログラムに制限する。事実（証明）の基数を追跡するために「彩色集合」を利用する。
• MRA: 彼らは以下のマルチセット関係代数を定義する：
  • $\pi$（射影）: 射影されたタプルの基数を合計する。
  • $\sigma$（選択）: 基数を保持しながらフィルタリングする。
  • $\bowtie$（自然結合）: 互換性のあるタプルの基数を乗算する。
  • $\cup$（算術和集合）: 基数を加算する。
  • $\setminus$（フィルタ差集合）: 基数を減算する（ゼロでクリップ）。

B. 変換メカニズム

本論文は、3 つの言語間の厳密な変換アルゴリズムを提供する：

• SPARQL $\leftrightarrow$ NRMD¬:
  • SPARQL から Datalog へ: 三連パターンはアトムになり、AND は結合になり、UNION は複数のルールになり、EXCEPT は否定になり、FILTER 条件は三値論理とエラーを明示的に処理するように書き換えられる。
  • Datalog から SPARQL へ: 事実は重複を保持するために一意の識別子付き RDF 三連としてエンコードされ、ルールは AND、UNION、EXCEPT を使用してグラフパターンに変換される。
• MRA $\leftrightarrow$ NRMD¬:
  • 標準的な関係演算は Datalog ルールにマッピングされる（例：結合 $\to$ ルール本体の論理積）。
  • Datalog ルールは代数式にマッピングされる（例：否定 $\to$ 集合差）。
• SPARQL $\leftrightarrow$ MRA:
  • SPARQL パターンは、部分領域の処理を含む解マッピングの互換性チェックをシミュレートする特別な Comp 関係を使用して、代数式に変換される。
  • 代数式は、空の結果に対する変数スキーマを再構築するために NULL 三連を使用して、SPARQL パターンに戻って変換される。

C. 表現的同等性の証明

中心的な理論的結果は同等性の三角形である：
$$\text{SPARQL} \equiv \text{NRMD}^\neg \equiv \text{MRA}$$
著者らは、マルチセット付きの SPARQL の核心フラグメントが、安全否定付き非再帰マルチセット Datalog およびマルチセット関係代数の両方と表現的に同等であることを証明する。

4. 結果

• SPARQL の特徴付け: この研究は、コア SPARQL フラグメントのマルチセットセマンティクスが恣意的なものではなく、明確に定義された論理的および代数的構造に正確に対応することを明らかにする。
• 演算子の一貫性: 最大和集合、最小共通部分、算術差集合など、カオス的な多様なマルチセット演算子をサポートする SQL とは異なり、SPARQL の設計は一貫した部分集合であることが示された。これは算術和集合とフィルタ差集合をサポートするが、最大和集合と最小共通部分はサポートしない。
• 「エラー」状態の処理: 本論文は、SPARQL の三値論理（特にフィルタにおける Error 状態）がマルチセット基数とどのように相互作用するかを成功裡に形式化し、標準的な集合代数の同等性（和集合に対するド・モルガンの法則など）が、特定の変換なしにはバッグセマンティクスでは直接成立しないことを示した。

5. 意義と含意

• 理論的基盤: この作業は、SPARQL のマルチセットセマンティクスに対する最初の厳密な代数的および論理的特徴付けを提供し、セマンティックウェブ（RDF/SPARQL）と古典的なデータベース理論（関係代数/Datalog）の間のギャップを埋める。
• 最適化の可能性: MRA および NRMD¬ との同等性を確立することにより、著者らは Datalog（例：マジックセット）および関係代数（例：結合の順序付け変更、選択のプッシュダウン）のために開発された最適化技術が、バッグベースのクエリのパフォーマンスを向上させるために SPARQL エンジンに適応可能であることを示唆している。
• 設計ガイダンス: 結果は、SPARQL の将来の拡張は、現在の演算子集合の一貫性を維持することを目指すべきであることを示唆している。この「一貫した」代数的構造の範囲外の演算子（最大和集合など）を追加することは、理論的な矛盾をもたらすか、またはアドホックな処理を必要とする可能性がある。
• 標準化: この作業は、重複が存在する状況における EXCEPT（SetMinus）および OPTIONAL の動作を明確にし、SPARQL 1.1 以降におけるクエリ最適化と同等性チェックの確固たる基盤を提供する。

要約すると、本論文は、SPARQL のマルチセットセマンティクスが複雑であるにもかかわらず、数学的に堅牢であり、確立された形式体系と同等であることを示しており、より効率的かつ理論的に健全な SPARQL クエリエンジンの実装への道筋を提供している。