XMLスキーマのもとでのXPath問い合わせの型振る舞い等価性を判定する多項式時間アルゴリズム

摘要

データ統合におけるラッパプログラムでは，統合後の問い合わせを，その意味が変わらないように統合前の問い合わせ群に変換できなくてはならない．また，データベースを扱うアプリケーションでは，スキーマ進化によって動作の意図しない変化が起きないことを保証できることが望まれる．つまり，異なるスキーマ上で同じ「振る舞い」をする問い合わせが必要となる．本稿では，異なるXMLスキーマ上でのXPath問い合わせの振る舞いの等価性を，スキーマで与えられる「（XML文書の頂点の）型」の概念を用いて，データの変換方法とは独立に「型振る舞い等価性」として定義する．さらに，型振る舞いに関する情報を決定性有限オートマトンで表すことにより，多項式時間で等価性を判定するアルゴリズムを提案する．