グラフデータにおける問合せ式充足可能性問題の計算複雑さおよび判定アルゴリズム

点击翻译按钮获取中文摘要

近年，RDF/グラフデータ（以下，単にグラフデータ）に対する記述力の高いスキーマ言語が策定され，その利用が進みつつある．本研究ではグラフデータを対象に，この分野において基本的かつ重要な問題であるスキーマ下での問合せ式充足可能性問題を中心に考察している．ここで，スキーマSと問合せ式qに対して，もしSに妥当なグラフデータでqの検索結果が空でないものが存在するならば，qはSの下で充足可能であるといい，そうでなければ充足不能であるという．本研究では，スキーマ言語として表現力の高いShape Expression (ShEx)を採用した．2022年度においては，問合せ式の包含性判定問題を解くためのアルゴリズムを考案し，実装を行った．ここで，包含性判定問題は充足可能性問題をより一般化した問題であり，問合せ式q1,q2およびスキーマSに対して，Sに妥当などのデータに対してもq2の解がq1の解に含まれるか否かを判定する問題である．提案アルゴリズムでは，まず，q1とq2との間のノードの対応関係をSを利用して求める．次に，この得られたノードの対応関係に基づいて，q2の辺eでq1に対応するものが存在せず，かつ，eをq1に追加してもq1の解に影響がない場合，eをq1に追加するという操作を繰り返す．最終的にq1がq2の部分グラフであれば，q1はq2を包含していると判定する．提案アルゴリズムをPythonを用いて実装し，予備的な評価実験を行った．その結果，提案アルゴリズムは使用データ全てに対して正しい判定を行なっており，動作効率も概ね良好であることがわかった．