研究内容紹介

XPath式の検証

ユーザの記述したXPath式がDTDに関して論理的に不整合なものであったり,文書構造の規則を満たさない式であった場合,その誤りを検証したり,適切な修正候補をユーザに提示できれば有用です.そのためのアルゴリズムを構成し評価を行っています.

もしユーザの記述したXPath式が論理的に不整合であり,どの妥当なXMLデータに対しても解が空(充足不能)であるならば,その式を実行するのは無意味です.しかし,XPath式が充足不能であるか否かは多くの場合において効率よく判定できないことが示されています.当研究室では,XPath式の充足可能性判定が効率よく判定できる十分条件を求め,

その条件の下で動作する多項式時間アルゴリズムを構成しています.

更に,誤りを含むXPath式に対して,その誤りを検出するだけでなく,

適切な修正候補(妥当なXPath式)を推測してユーザに提示できればより有用です.ただし,入力XPath式に対する修正候補は無限個存在し得るので,提示すべき式を一意に特定するのは困難です.そこで,入力XPath式に類似した修正候補を複数列挙してユーザに提示すれば,ユーザはその中から所望の式を選択することができ,より有効なユーザ支援が行えます.当研究室では,このようなXPath式の列挙を行うアルゴリズムを構成し,評価を行っています.

関連発表

  • N. Suzuki and Y. Fukushima, “Satisfiability of Simple XPath Fragments in the Presence of DTDs”, Proceedings of the 11th ACM International Workshop on Web Information and Data Management (WIDM 2009), pp.15-22,2009.
  • 福島雄司,鈴木伸崇,”限定されたXPath構文に関する充足可能性問題について”, 情報処理学会第71回全国大会,1P-3,2p, 2009. (学生奨励賞受賞)
  • 池田光雪,鈴木伸崇,”妥当でないXPath式に対するK最適修正候補発見の一手法”, 日本ソフトウェア科学会第27回大会,3C-6,5p, 2010. (学生奨励賞(学生セッション部門)受賞)
  • 池田光雪, 鈴木伸崇, “妥当でないXPath式に対するK最適修正候補発見アルゴリズム”, 情報処理学会データベースシステム研究発表会報告, DBS-151-34, 8p., 2010. (学生奨励賞受賞)

スキーマ進化とXML変換

ある程度まとまった量のXMLデータを蓄積・管理する場合,通常DTDなどのスキーマを定義し,それに妥当なXMLデータを作成して管理するのが一般的です.しかし,時間の経過とともに格納すべきデータの構造や種類は変化するので,それに応じてスキーマも更新する必要があります(スキーマ進化).当研究室では,スキーマ進化に関するデータの管理手法などについて研究しています.

スキーマが更新された場合,そのスキーマの下で定義されているXMLデータも妥当でなくなるので,XMLデータを妥当なものに変換する必要が生じます.しかし,大量のXMLデータをすべて手作業で変換するのは非現実的です.当研究室では,スキーマの更新操作から適切なXML変換を推測し,その内容からXML変換を行うXSLTスクリプトを生成する手法について研究しています.

なお,スキーマが更新された場合,その更新操作から必ずしも一意にXML変換が推測できるとは限りません.そこで,当研究室では,スキーマが更新された場合に,XML変換が一意に定まるか否かを判定するアルゴリズムを構成しています.また,スキーマ進化においては,スキーマのバージョン管理も重要となります.そこで,バージョン管理を適切に行うためのスキーマの差分抽出アルゴリズムについて研究しています.

関連発表

  • N. Suzuki, “An Algorithm for Inferring K Optimum Transformations of XML Document from Update Script to DTD”, IEICE Transactions on Information and Systems, vol.E93-D, no.8, pp.2198-2212, Aug. 2010.
  • N. Suzuki and Y. Fukushima, “An XML Transformation Algorithm Inferred from an Update Script between DTDs,” IEICE Transactions on Information and Systems, vol.E92-D, no.4, pp.594-607, Apr. 2009.
  • N. Suzuki, “On Inferring K Optimum Transformations of XML Document from Update Script to DTD”, Proceedings of the 14th International Conference on Management of Data (COMAD 2008), pp.210-221, 2008.
  • N. Suzuki and Y. Fukushima, “An XML Document Transformation Algorithm Inferred from an Edit Script between DTDs”, Proceedings of the 19th Australian Database Conference (ADC 2008), pp.175-184, 2008.

XMLデータの修正支援

ユーザの記述したXMLデータが妥当でない場合,通常,ユーザは手作業で要素の追加や削除を行って,そのデータを妥当なものに修正する必要があります.しかし,データが複雑であったりユーザがスキーマ定義の詳細を把握していない場合など,必ずしも容易に修正が行えるわけではありません.そこで,妥当でないXMLデータに対して,それを妥当なものに修正するための手続きを自動生成するアルゴリズムについて研究しています.

関連発表

  • N. Suzuki, “Finding K Optimum Edit Scripts between an XML Document and a Regular Tree Grammar,” Proceedings of ICDT Workshop on Emerging Research Opportunities in Web Data Management (EROW 2007), pp.81-95, 2007.
  • N. Suzuki, “On Finding an Edit Script between an XML Document and a DTD,” IPSJ Transactions on Databases, vol.47, no.SIG19(TOD32), pp.1-13, Dec. 2006.

その他(XSLTやXQuery式の作成支援)

複数のXMLデータをHTMLなどに一括して変換する場合,通常,手作業でXSLT等の式を記述して所望の変換を行います.しかし,XSLT式の記述は一般のユーザにとって必ずしも容易ではありません.そこで,ユーザが変換に関するヒントなどを与えると,そこからXSLT式を推測・自動生成する手法について研究しています.

XPathやXQueryなどの問合せ式は,通常,ユーザが式を直接入力して実行しますが,問い合わせ対象のデータ構造を完全に把握していない/できない場合などは,正しい式を記述することは容易ではありません.

そこで,GUI上にデータの概観を示し,必要な要素や条件を指定して問合せ式を自動生成する手法について研究しています.