データベース理論

データベース理論とは, データベースシステムを支える基礎理論・基礎技術を 構築・開発する研究分野です. データベースシステムにおいて 現実に起こっている(あるいは将来起こりうる)問題に注目し, その問題の本質を見極めた上でその問題を形式的に定義し, 本質的な解決を目指しています.

藤原研究室ではここ数年,以下のようなテーマに取り組んでいます.

XMLデータベースのスキーマ進化・スキーマ統合
データベーススキーマの設計は,データベースの運用開始前に 慎重に行われるものですが,実際に運用してみて不具合があったり, 長年の運用によって時代遅れになったりして, スキーマを改良する必要が生じる場合があります. そのようなスキーマの改良をスキーマ進化と呼びます. また,同種のデータが独立した複数の組織で管理されている場合, それらのスキーマが完全に一致することはまずありません. ユーザの利便性のためには,同種データを扱う異なるスキーマ群を 一つのスキーマに統合できることが望まれます. これをスキーマ統合と呼びます.

本研究ではXMLデータベースのスキーマ進化支援システムの構築を目標とし, 「もとのデータベースの情報を欠落させないようなスキーマ進化」とは なにかを追究してきました. 具体的には,情報を欠落させないスキーマ進化を行うための スキーマ更新操作群を提案しました. 最近では,スキーマ進化や統合に応じて, XML文書や問合せを「適切に」変換する手法を研究しています. 同じ問合せでも,スキーマ進化や統合の前後で振舞いが変わってしまう ことがあるため,そのような振舞いの変化を検出したり, 振舞いが変化しない問合せへ変換したりする手法を研究しています.

  • 二神 司, 石原 靖哲, 藤原 融, ``XMLスキーマのもとでのXPath問い合わせの型振る舞い等価性を 判定する多項式時間アルゴリズム,'' 電子情報通信学会技術研究報告, SS2014-29, Vol. 114, No. 271, pp. 23-28 (2014-10).
  • Kenji Hashimoto, Ryuta Sawada, Yasunori Ishihara, Hiroyuki Seki and Toru Fujiwara, ``Determinacy and Subsumption for Single-valued Bottom-up Tree Transducers,'' Proceedings of the 7th International Conference on Language and Automata Theory and Applications (LATA2013), Lecture Notes in Computer Science 7810, pp. 335-346 (2013-04).
  • 吉田 昌起, 橋本 健二, 石原 靖哲, 藤原 融, ``XMLスキーマ更新操作に応じたXSLT文書変換プログラムの自動生成法,'' 第10回プログラミングおよびプログラミング言語ワークショップ(PPL2008), pp. 168-182 (2008-03).
  • 橋本 健二, 石原 靖哲, 藤原 融, ``XMLデータベースにおけるスキーマ進化のための更新操作群と それらのスキーマ表現能力保存に関する性質,'' 電子情報通信学会論文誌(D), Vol. J90-D, No. 4, pp. 990-1004 (2007-04).
また, XMLスキーマ進化や統合においてスキーマ間の意味的な対応づけを表す 「XMLスキーママッピング」に注目し, XMLスキーママッピングが望ましい性質を満たしているかを 効率よく判定する手法も提案しています. この研究成果はAPWeb2013という国際会議で Best Student Paper Awardを受賞し, すでに海外ジャーナルへの掲載が決定しています.
  • Hayato Kuwada, Kenji Hashimoto, Yasunori Ishihara and Toru Fujiwara, ``The Consistency and Absolute Consistency Problems of XML Schema Mappings between Restricted DTDs,'' World Wide Web Journal (accepted).
  • Yasunori Ishihara, Hayato Kuwada and Toru Fujiwara, ``The Absolute Consistency Problem of XML Schema Mappings with Data Values between Restricted DTDs,'' Proceedings of the 25th International Conference on Database and Expert Systems Applications (DEXA2014), Lecture Notes in Computer Science 8644, pp. 317-327 (2014-09).
データベースセキュリティ
データベースに対する脅威のひとつに, 推論攻撃という脅威があります. 推論攻撃とは,データベースのユーザが, 自分に許可された問合せの結果を用いて, 許可されていない問合せの結果(機密情報)の値を 推論して得ようとする攻撃です. 現在,XMLデータベースを対象として, 推論攻撃に対してデータベースが安全かどうかを 検証するアルゴリズムを開発しています. そして,企業と共同で,推論攻撃に対する安全性検証技術を応用して 暗号化データベースの安全性を評価する試みも行っており, 成果も出始めています. 以前は,オブジェクト指向データベースを対象として, 推論攻撃に対するセキュリティについての研究を行っていました. 攻撃者の推論が等式論理に基づいてモデル化されているのが特徴です. 問題の定式化も得られた成果も,理論的に非常に美しいものになっています.
データベース問合せの静的解析と最適化
XMLデータベースへの問合せを静的に(具体的なデータがない状態で)解析し, その結果を問合せ処理高速化に役立てようという研究を行っています. 主にXPathという問合せ言語を対象として, さまざまな静的解析問題に取り組んでいます. また,国立情報学研究所の研究者と共同で, XQueryという問合せ言語の処理高速化にも取り組んでいます. これまでに得られた成果の多くは, 世界的に著名ないくつかの国際会議に採択されています. 最近ではこれらの静的解析アルゴリズムの実装にも取り組んでいます. 他にも,データベースの安全性定義・安全性判定への応用を目的として, 「問合せ解像度」という概念に着目し, その高低関係を判定する問題について検討を行っています. 以前は,オブジェクト指向データベースへの問合せの型検査問題 という問題に取り組んでいました. そして,型検査問題を難しくする要因を理論的に明らかにしました.
不完全な情報の表現と処理
「石原はプログラミングCを担当しているが,講義の曜日は不明である」 のように,一部が欠けていたり曖昧である情報を,不完全な情報と呼びます. これまで,不完全情報を表現するための, 多重集合ベースのデータモデルを提案し,その性質を調べてきました. その成果を発表した論文は大阪大学論文100選(2008-2009)にも選ばれています. 以前は,マルチエージェントシステムを対象とし, エージェントが得る時間的知識 (例えば「1時から2時まで部屋の灯がついていた」などのように 時刻情報が付帯した知識)のためのデータモデルの研究に取り組みました. そして,エージェント同士がこの時間的知識を交換・共有することにより 新たな知識を推論することが,効率よく行えることを示しました. この成果は,情報科学分野で世界的に著名な論文誌上で発表しています. 不完全情報のためのデータモデルは, 推論攻撃を行うユーザがもっている知識の表現に用いることができたり, スキーマ統合においてスキーマ変換後のデータの表現に用いることができるなど, 他のテーマとの関連も非常に深いものです. 今後はXMLベースの不完全情報データモデルを開発していく予定です.

Valid CSS! Valid XHTML 1.1! Yasunori ISHIHARA (最終更新日: 2015年3月20日)