技術要約：RDFルールにおける階層化否定：正しいアプローチ

1. 問題提起

本論文は、RDFルール言語（N3やSHACL Rulesなど）を、デフォルト否定（失敗による否定：negation-as-failure）および値の生成（空白ノードや存在変数などの新しい要素の作成）と組み合わせる際の課題に対処している。Datalogベースのルールエンジンは通常、層化（非単調な操作が完全に計算されたデータに対してのみ適用されるように、ルールの適用順序を制御すること）を用いて否定を処理するが、既存の手法はRDFの文脈では2つの主要な問題により失敗する。

1. 従来の層化の失敗： 従来の層化は、異なる述語間の依存関係に依存している。しかし、RDFは単一の三項述語（トリプル）を利用する。その結果、いかなる否定の使用も標準的な層化を不可能にする。SHACLは洗練された単一化ベースの依存関係分析を提案しているが、「全変数」トリプル（例：?x ?p ?y）を含むルールでは、ルール間の依存関係が作成されてしまい、制約によって論理的なフィードバックサイクルが防止されている場合であっても、層化が不可能になる。
2. 明確に定義された意味論の欠如： ルールが正常に層化されている場合であっても、空白ノード（存在変数）がルールのヘッドに含まれると、一意またはリーン（lean）ではない結果を招く可能性がある。ルールの適用順序によって、新しい空白ノードが作成されるか、あるいは既存のデータがルールを満たすかが決定され、最終的なRDFグラフが異なる結果となる。これは、古典的に層化されたRDFルールセットが、実行順序に依存するため、明確に定義された意味論を欠く可能性があることを意味する。

2. 手法

著者らは、**チェイン層化（chain stratification）**と呼ばれる新しい条件を提案している。このアプローチは、単純な述語レベルまたはインスタンスレベルのチェックを超えて、より堅牢な多段階の導出の分析へと、ルール依存関係の分析を洗練させるものである。

コア概念

• リライアンス（Reliances）： Krötzschの先行研究に基づき、本論文ではルール間の3種類の二項関係を利用する：
  • 正のリライアンス ($\prec^+$)： ルール $\rho_1$ が $\rho_2$ に必要なデータを作成する。
  • 負のリライアンス ($\prec^-$)： ルール $\rho_1$ が（否定を介して）$\rho_2$ のマッチングを阻止する。
  • 抑制リライアンス ($\prec^\square$)： ルール $\rho_1$ が $\rho_2$ に対する「代替のマッチ」を作成し、非リーンな結果（冗長な空白ノード）を招く可能性がある。
• トレイル（Trails）： 著者らは、ルール適用のシーケンスのデータ独立な抽象化としてトレイルを導入する。トレイルは、各ステップが前のステップに因果的に依存し、そのシーケンスが後続のルールに対する新しい未充足のマッチにつながるような、ルールインスタンスのシーケンスを表す。関係 $\prec^+_t$（トレイルに基づく正のリライアンス）は、優先順位を尊重することが負のリライアンスや抑制リライアンスの違反を防ぐことを保証する最小の関数として定義される。
  • 理論的限界： トレイルの存在を判定することは、存在的ルールにエンコードされたチューリングマシンの停止問題と等価であるため、決定不能である（定理4）。
• チェイン（Chains）： 決定可能性を実現するために、著者らはトレイルの決定可能な緩和策としてチェインを定義する。チェインは、意図しない古い変数との単一化を避けるために変数が再命名された（デカップリングされた）、デカップルドな（decoupled）ルールインスタンスのシーケンスであり、「チェインルール」（シーケンスを代表する集約されたルール）に基づく特定の正のリライアンス条件（$\prec^{\ll+}$）を満たす。
  • すべてのチェインがトレイルであるわけではないが、すべてのトレイルはデカップルドなチェインによって一般化できる（補題5）。
  • すべてのデカップルドなチェインの集合は正規言語（$L_R$）として特徴付けられ、有限の決定手続きを可能にする（定理11）。
• チェイン層化（Chain Stratification）： チェインに基づく正のリライアンスと、負および抑制のリライアンスの合成によって形成される優先関係（$\prec^-_c \cup \prec^\square_c$）が非循環であるとき、ルールセットはチェイン層化されていると言える。
• 制約の処理： 制約（矛盾 $\bot$ を導出するルール）を扱うようにアプローチを拡張する。特定のチェインが制約を違反するかどうかを分析することで（Datalogルールを介して）、問題のあるフィードバックサイクルを作成する可能性のあるチェインを破棄できる。これにより、「制約下でのチェイン層化」が可能となる。

アルゴリズム

本論文は、チェイン層化を決定するアルゴリズム1を提示している。これは、チェインを反復的に構築し、それらのラベル（チェインによる正、負、および抑制の依存関係への影響を要約したもの）を計算し、優先関係グラフにおけるサイクルをチェックするものである。正規言語の特性を利用することで、アルゴリズムの停止が保証される。

3. 主な貢献

1. チェイン層化： 否定と存在変数を持つRDFルールを層化するための、新しく堅牢な条件。これは、導出された優先順位を尊重する任意のチェイス・シーケンスが、失敗による否定の意味論の下で、一意かつリーンで、正当化されたRDFグラフを生成することを保証する。
2. 理論的基礎：
   • 多段階の相互作用を正確に捉えるためのトレイルの定式化を行い、トレイルに基づく優先順序を尊重することが、生成および代替マッチフリーなチェイスを保証することを証明した。
   • 決定不能性の証明。
   • 決定可能な近似としてのチェインの開発、およびチェインの言語が正規であることの証明。
3. 制約の統合： 制約を遵守するチェインを破棄することでチェイン層化を洗練させる手法。これにより、従来の層化が失敗するケース（導入部の問題1のようなケース）においても、ルールが論理的に安全である場合に解決できる。
4. プロトタイプ実装： N3、Nemo、およびVLog構文を受け入れるRustベースの実装。このツールは、数千のルールを含むルールセットの分析に成功している。

4. 結果と評価

著者らは、プロトタイプを20の否定なしルールセット（以前のコア層化分析で使用されたもの）のベンチマークで評価した。

• パフォーマンス： 80のルールセットを0.1秒未満で分類し、187個を15分間のタイムアウト内に処理した。タイムアウトした14のルールセットは、それぞれ6万個以上のルールを含んでいた。
• オーバーヘッド： 標準的なコア層化チェックと比較して、チェイン分析を必要とした128のケースにおける追加の計算コストは、平均で**12.51%**であった。
• 正確性： 実装は、以前は層化不可能と判断されていたチェイン層化可能なルールセット（RDFSの部分プロパティ・ルールと空白ノードおよび否定が組み合わさった複雑なケースを含む）を正常に特定した。

5. 意義と主張

本論文は、チェイン層化が、RDFルール推論における長年の未解決問題に対する正しいアプローチであることを主張している。

• 正確性： 空白ノードを伴う層化されたRDFルールの意味論における曖昧さを解消し、ルール適用順序（優先順位を尊重する場合）に関わらず、推論されたグラフが一意かつリーンであることを保証する。
• 実用性： 大規模なルールセットに対しても、プロトタイプで示されたように、計算量的に実行可能である。
• 標準化： 著者らは、本研究をN3およびSHACL Rulesの継続的な標準化への貢献として位置づけており、空白ノードと否定を組み合わせたRDFベースのルール言語における、理論的に健全な取り扱いを提供している。
• 限界： 著者らは、この手法が定義されたクラスのルールに対して理論的および実用的な問題を解決する一方で、現実世界のデプロイメントにおける「有効性」を完全に評価するための、否定を含む代表的なRDFベースのベンチマークが存在しないことを謙虚に認めており、合成的またはオントロジー由来のベンチマークに依存している。

結論として、チェイン層化は完全な層化を一般化し、適切な制約がある場合には、空白ノードと否定を組み合わせたN3ルール（RDFSの部分プロパティの推移性など）の安全な使用を可能にする。