図書館情報メディアパンフ2017

12/56

学位論文(2016年度修了)10学位論文(2016年度修了)的解析の1つである。XMLにおける静的解析問題は多くの場合において計算困難であることが知られているが、本論文で考察するXPath式修正問題が効率よく解けるか否かは自明でなく、アルゴリズム・計算複雑性の観点からこの問題の性質を究明することは重要な課題である。そこで本論文では、XPath式修正問題において、スキーマやXPath式に対する制約の強さの観点から、計算困難な部分と効率よく解ける部分を明らかにすることを主な目的とする。　これまで、XPath式に対する修正を形式的に定義し議論した研究は存在しなかった。本論文では、XPath式に対する編集操作の形式的な定義を与え、2つの編集操作のクラスcoreおよびextendedを定めた。これに加えて、XPath式の2つの部分クラスsimpleおよびXPを定義し、これら編集操作およびXPathのクラスが、XPath式修正問題の計算複雑さに影響を与える主要な要因であることを明らかにした。特に、編集操作としてextendedを許した場合、XPath式修正問題が計算困難であることを明らかにした。　また、編集操作としてcoreのみを用いると仮定した上で、XPath式修正問題を解くためのアルゴリズムを提案した。このアルゴリズムに関する議論を通じて、XPath式がsimpleなものである場合、XPath式修正問題が多項式時間可解であることを明らかにした。さらに、XPath式がXPに属する場合において、XPath式修正問題が多項式時間可解であるための十分条件を明らかにした。（研究指導担当教員　鈴木伸崇）XML問合せ式における修正候補発見アルゴリズムに関する研究池田光雪　記述した問合せ式が所望の結果を返さない場合、問合せ式を正しく修正する必要がある。このような場合に、正しい問合せ式の記述を支援する手法が利用できれば有用である。これまで、関係データベースにおいては、SQL文の記述を支援するための手法が提案されてきた。一方、XMLは関係データベースと比べ複雑な構造を有している。このため、XML において問合せ式の記述を支援するのはより困難であり、有効な手法はほとんど存在しないのが現状である。　正しい問合せ式の記述を支援するためには、データ構造に関する正確な情報を把握する必要がある。そのような情報を得る方法として、データを走査してデータ構造に関する情報を収集する方法と、データの代わりにスキーマを参照する方法の2つが考えられる。しかし、前者にはプライバシーやセキュリティ上の理由から、データの全体または一部を参照するのが困難な場合があるといった問題がある。そこで本論文では後者に着目し、スキーマから得られる構造情報に基づいて正しい問合せ式の記述を支援することについて考察する。また、問合せ式の記述を支援する場合、要素名の補完のように問合せ式記述の際に支援を行う方法と、正しくない問合せ式が記述された場合にその式を修正する方法が考えられる。とりわけ後者は、記述された問合せ式が所望の結果を返さない時や、スキーマが更新されて問合せ式が正しくないものとなった場合などに有効である。本論文では後者に着目し、利用者によって記述されたXPath式を正しいものに修正する問題について考察する。　データを参照せずスキーマに基づいて問合せ式の振る舞いを解析することを静的解析といい、本論文で考察する問題も静博士（情報学）