DEIM Forum 2013 B2-2

スキーマ進化に伴う XPath 式修正アルゴリズムの提案
長谷川数馬†

池田光雪†

鈴木 伸祟 ††

† 筑波大学大学院 図書館情報メディア研究科 〒 305–8550 茨城県つくば市春日 1–2†† 筑波大学 図書館情報メディア系 〒 305–8550 茨城県つくば市春日 1–2
E-mail: †s1221595@u.tsukuba.ac.jp, ††{lumely,nsuzuki}@slis.tsukuba.ac.jp
あらまし XML データを蓄積・管理する場合，DTD などのスキーマを用いてデータの構造を定義するのが一般的である．スキーマは，利用者の要求や使用状況に応じて更新される (スキーマ進化)．スキーマが更新された場合，検索対象の XML データの構造が変化するため，XPath 式の修正が必要となる場合がある．しかし，これを手作業で行うのは容易ではない．本稿では，木オートマトンに基づいて，スキーマに対して行われた更新操作を用いて XPath 式を修正するアルゴリズムを提案する．
キーワード

XPath，スキーマ進化，木オートマトン，クエリ修正

1. は じ め に対応が困難である．また，このアルゴリズムでは XPath 式の述語は使用不可となっているが，述語は実用において用いられXML(Extensible Markup Language) はあらゆるデータを記る場合が多い．本稿では，XML の主要なスキーマが木オート述するフォーマットとして様々なシステムで用いられている．

マトンとして表せることに着目し，木オートマトンに基づいて大量の XML データを蓄積・管理する場合，DTD(Document

XPath 式を修正するアルゴリズムを提案する．また，述語へのType Definition) などのスキーマ言語を用いてあらかじめ格納対応も行う．

するデータの構造を定義しておき，スキーマの定義にしたがっ

本アルゴリズムは，child 軸と descendant-or-self 軸のみを用ている（妥当な）データを生成・蓄積するのが一般的である．

いた XPath 式を対象とする．ただし、実際に使用されているスキーマは，利用者の要求や使用状況に伴い要素の削除や新たXPath 式の多くはこれらの軸のみを用いているため，実用上な要素の追加などの更新操作により内容が変化する．これをスの問題は小さいと考えられる．また，スキーマの更新操作は文キーマ進化と呼ぶ．また，XML データへの問合せ言語として献 [3] では 7 つ定義されている．本稿では，そのうち要素に関XPath(XML Path Language) がよく使われている．

する更新操作，要素の追加・削除・挿入・抜き取りを木オート

ここで，スキーマに妥当な XML データに対し XPath 式でマトンの更新操作として拡張し使用する．特に，要素の削除が問合せを行う場合を考える．スキーマが更新された場合，ス行われた場合，スキーマ進化後に XPath 式の検索対象が消失

キーマに対し妥当であった XML データは進化後のスキーマにする場合がある．本アルゴリズムは，要素の削除が行われた場

対し妥当になるように修正される必要がある．同様に，XML合，検索対象が消失するかを判定し，消失した場合はスキーマ

データの構造が変化したことにより，進化前のスキーマには妥

進化後に XPath 式が使えない旨を，そうでないときは修正さ当であった XPath 式の妥当性が失われる可能性がある．このれた XPath 式を出力する．本アルゴリズムでは XPath 式の修場合，XPath 式を進化後のスキーマに対し妥当になるように修正を行うために，スキーマと XPath 式の有限木オートマトン

正する必要がある．また，XPath 式は XML データの構造を利を作成し，積オートーマトンを作る．作成した積オートマトン

用して問合せを行う．そのため，XML データやそれに対するとスキーマに対して行った更新操作から，XPath 式に対する修修正内容を参照せずとも，スキーマ進化に対する更新操作のみ

正内容を決定する．

から XPath 式に対する修正を推測できることが多い．しかし，

本稿と最も関連が強いのは森本らの研究 [4] である．本論文

XML データやスキーマの構造が複雑であったり，スキーマにとの主な違いは，同文献ではスキーマ進化においてスキーマの行われた更新操作が膨大な場合，XPath 式を修正するのは容易

内容が単調に増加すると仮定しており，要素の削除を伴う更新

ではない．

操作を定義していない．一方，本稿では，要素の削除や抜き取

これまで著者らはこの問題に対して，XPath 式がスキーマ進りも含めて考察する．これらの更新を行う場合，元のスキーマ

化後の DTD に対して妥当か否かを DTD に対し行った更新操

では XPath 式で検索できていた要素が更新後のスキーマでは作から判断し，妥当でない場合には妥当となるように XPath

検索できなくなることがある．したがって，XPath 式の修正を

式を修正するアルゴリズムを提案してきた [1]．そのアルゴリズ

行うのはより複雑で困難な問題になる．著者らの知る限り，ス

ムでは，DTD に対して行われた更新操作から更新後の DTD

キーマ進化と XPath 式の変換を共に扱った研究は森本らの研に対し妥当となるように XPath 式を修正することが可能であ究を除いて存在しない．

る．しかし，そのアルゴリズムは DTD を参照して XPath 式の修正を行っているため，XML Schema など他スキーマへのここで，reg v は reg における位置 v の子孫からなる部分式を表

2. 諸 定 義

す．例えば，reg=(A|B)*の場合，前置記法により reg=*(|(A,B))

本章では，有限木オートマトン及び有限木オートマトンの積演算を定義する．積演算の定義は文献 [5] に従う．

と表わされる．pos(reg)={λ, 1, 11, 12} であり，λ が*，1 が |，11 が A，12 が B に対応する．

2. 1 有限木オートマトン

3. 2 有限木オートマトンに対する更新操作

有限木オートマトンは 4 次組 TA = (N, Σ, s, P) と定義され有限木オートマトン TA=(N, Σ, s, P) に対する更新操作を
次のように定義する．

る．ここで，••

N は状態の有限集合•

Σは要素名の有限集合a に対応する遷移規則の右辺の位置 i に B を追加する操作であ•s ∈ N は初期状態

る．これを，ins elm tree(a, A, B, i) と表す．

•

P は X → a(reg) または X → Y の形をした遷移規則の有•要素の追加は，P における左辺が A で右辺のラベルが要素の削除は，P における左辺が A で右辺のラベルが a限集合に対応する遷移規則の右辺の位置 i の状態を削除する操作であただし，X,Y ∈ N, a ∈Σであり，reg は N 上の正規表現である．これを，del elm tree(a, A, i) と表す．

る．X は規則の左辺，Y,a(reg) を右辺といい，a,reg をそれぞ•要素の挿入は，P における左辺が A で右辺のラベルが aに対応する遷移規則の右辺の位置 i の部分式 C を B に置換す

れこの規則のラベル，内容モデルという．

2. 2 有限木オートマトンの積演算る．更に，P に B → b(C) を追加する．これを，agg elm tree(a,TA1 =(N1 , Σ1 , s1 , P1 ) と TA2 =(N2 , Σ2 , s2 , P2 ) を有限木

A, b, B, i) と表す．

オートマトンとする．一般性を失うことなく，Σ1 =Σ2 =Σと•要素の抜き取りは，P における左辺が A で右辺のラベル仮定する．まず，N1 上の正規表現 reg 1 と N2 上の正規表現が a に対応する遷移規則の右辺の位置 i の状態 C を，左辺が C

reg 2 に対して，それらの積 reg 1 ⊕reg 2 を構成する．reg 1 ⊕reg 2の遷移規則の内容モデルに置換する．これを，ext elm tree(a,は N1 ×N2 上の正規表現である．n11 n12 ...n1i が reg 1 と一致し，

A, i) と表す．

かつ n21 n22 ...n2i が reg 2 と一致する場合に，N1 ×N2 中の状態の系列 [n11 , n21 ] [n12 , n22 ] ...

[n1i , n2i ] は reg 1 ⊕reg 2 と正確に一致する．
このとき，reg 1 と reg 2 の積を受理する正規表現の構成方法
は以下の通りである：

ここで，更新操作の例を示す．TA=({V, W, X, Y, Z}, {v,w, x, y, z}, V, P) を有限木オートマトンとする．ただし，
P = {V → v(W X), X → x(Y Z), Y → y(Z), W → w(ε), Z → z(ε)}
である．

′

1. reg 1 から reg 1 (N1 ×N2 上の正規表現) をつくる．これはN1 中の各 n を [n1 , n21 ] | [n1 , n22 ] | ... | [n1 , n2k ] で置き換える
ことで行われる．ただし，n21 , n22 , ..., n2k は N2 の列挙である．
同様にして，reg 2 から reg ′ 2 (N1 ×N2 上のもう一方の正規表現)を構成する．

1. ins elm tree(x, X, W, 2)•

X → x(Y Z) ⇒ X → x(Y W Z)

2. del elm tree(v, V, 1)•

V → v(W X) ⇒ V → v(X)

3. agg elm tree(x, X, t, T, 1)

2. reg ′ 1 と reg ′ 2 から 2 つのオートマトンを構成する．

•

3. これらの積オートマトンを構成する．

•

X → x(Y W Z) の右辺の 1 番目の状態 Y を保存

4. この積オートマトンから正規表現，すなわち reg 1 ⊕reg 2 を•

X → x(Y W Z) ⇒ X → x(T W Z)•

P={V → v(X), X → x(T W Z), Y → y(Z), W → w(ε),

構成する．
このとき，TA1 と TA2 の積のオートマトンは TA3 =(N1 ×N2 ,Σ, s1 ×s2 , P3 ) である．ただし，{V, W, X, Y, Z} ⇒ {V, W, X, Y, Z, T}

Z → z(ε), T → t(Y)}
4. ext elm tree(v, V, 1)

P3 = {[n1 , n2 ] → a(reg 1 ⊕reg 2 ) | (n1 → a(reg 1 ) ∈ P1 ，n2 →•V → v(X) の右辺の 1 番目の状態 X を保存

a(reg 2 ) ∈ P2 )}•X → x(T W Z) ⇒ V → v(T W Z)′′

∪ {[n1 , n2 ] → [n1 , n 2 ] | (n1 ∈ N1 ，n2 → n 2 ∈ P2 )}∪ {[n1 , n2 ] → [n ′ 1 , n2 ] | (n1 → n ′ 1 ∈ P1 ，n2 ∈ N2 )}3. 更 新 操 作

4. XPath 式
本章では，文献 [5] の定義を用いて，XPath 式の有限木オートマトンへの変換を定義する．

本章では，有限木オートマトンに対する更新操作を定義する．

4. 1 XPath 式

3. 1 reg 内での状態の位置

Σを要素名の集合とする．XPath 式 p’ を以下のように定義

まず，reg 内での位置集合 pos(reg) を次のように定義する．

reg は前置記法で表す．
••

reg=ϵ または reg=a(a ∈Σ) のとき，pos(reg)={λ}
上記以外の場合，pos(reg)={λ} ∪ {u | u = vw, 1<
=n,
=v <

w ∈ pos(reg v )}する．

•

p’::=/p•p::=χ::l | p/p | p[q]•χ::=child | descendant-or-self

•

q::=p

ただし，l ∈Σである．各 χ ∈ { child | descendant-or-self }を軸，q を述語という．

Np1/p2 = {[np1 , np2 ] | (np1 ∈ NO p1 ，np2 ∈ NI p2 )∨ (np1 ∈ (Np1 - NO p1 )，np2 ∈ (Np2 - NI p2 ))}4. 2 XPath 式の有限木オートマトンへの変換

また，入力状態集合は次のようになる．

XPath 式の有限木オートマトンへの変換は，前節の XPathNI p1/p2 = {[nI p1 , np2 ] | (nI p1 ∈ NI p1 ，np2 ∈ (Np2 - NI p2 ))}式の定義に従って以下のように変換を行う．まず，ロケーション

出力状態集合は，次のようになる．

ステップ χ::l を有限木オートマトンに変換する．この変換は各NO p1/p2 = {[np1 , nO p2 ] | (np1 ∈ (Np1 - NO p1 )，np2 ∈軸 χ に対して用意する有限木オートマトンを用いて行う．用意NO p2 )}

された有限木オートマトンには入力状態と出力状態があり，そ4. 3. 2 p[q] の場合

れぞれ χ::l に対するコンテキストノード，χ::l が指定するノーp，q はそれぞれ有限木オートマトン TAp ，TAq に変換済みドを出力する状態である．次に XPath 式の構文に従って，ボであるとする．TAp の出力状態と，TAq の入力状態以外の状

トムアップ的に有限木オートマトンを構成する．この際，有限態のペアや，TAp の出力状態以外の状態と，TAq の入力状態

木オートマトンの出力状態と入力状態を考慮する必要がある．

のペアが，積を取ったオートマトンの状態に現れないように積4. 2. 1 ロケーションステップに対する有限木オートマトンを取る．すなわち，積を取ったオートマトン TAp[q] の状態集合

ここでは，χ::l という形の部分式に対する有限木オートマト

は次のようになる．

ンを与える．部分式に出現する軸によって，各部分式に対する

Np[q] = {[np , nq ] | (np ∈ NO p ，nq ∈ NI q )有限木オートマトンが異なる．以下では，A →σ (…) という∨ (np ∈ (Npq - NO p )，nq ∈ (Nq - NI q ))}記述は {A →σ (…) | σ∈Σ } を表すものとする．

また，入力状態集合は次のようになる．

•

χ=child の場合

NI p[q] = {[nI p , nq ] | (nI p ∈ NI p ，nq ∈ (Nq - NI q ))}– 初期状態：B

出力状態集合は，次のようになる．

– A →σ (A*)

NO p[q] = {[nO p , nq ] | (nO p ∈ NO p ，nq ∈ NI q )}– B →σ (A* (B|C) A*)

4. 3. 3 /p の 場 合– B→CXPath 式 p の先頭のロケーションステップ χ::l では初期状– C →σ (A* D A*)

態をルートノード root に対応する状態 R とし，コンテキスト– D → l(A*)

ノードを root とする．初期状態が R の有限木オートマトンは•

絶対ロケーションパスとみなす．また，絶対ロケーションパス

χ=descendant-or-self の場合– 初期状態：B1

であるオートマトンと積を取った場合，構成されるオートマト– A →σ (A*)

ンも絶対パスとなる．

– B1 →σ (A* (B1 |C) A*)– B1 → C– C →σ (A* (B2 |D) A*)– C→D

5. XPath 式修正アルゴリズム
本アルゴリズムの方針は，更新前のスキーマと更新後のス
キーマにおいて検索結果が一致し，かつ妥当であるように入力– B2 →σ (A* (B2 |D) A*)

XPath 式 p を修正することである．ただし，更新操作が要素の– D → l(A*)

削除であった場合，必ずしも検索結果が同じになるように修正各軸に対する有限木オートマトンの状態のうち，C は部分式のできるとは限らない．そこで，以下の方針でアルゴリズムを構

コンテキストノードに対応する状態，D は部分式が指定する

成する．

ノードに対応する状態である．これらの有限木オートマトンの•入力状態は {C} であり，出力状態集合は {D} である．

– スキーマ進化前より検索される要素が増える可能性があ

4. 3 XPath 式の有限木オートマトンの構成法

るが，スキーマ進化前と同じ結果を得られるように p を修正す

XPath 式の有限木オートマトンの構成法を定義する．まず，るのは困難なため，修正を行わない．

更新操作が要素の追加の場合

p1 /p2 , p[q] それぞれの場合について構成法を定義する．次に，•絶対ロケーションステップ/p について考える．p の有限木オー– スキーマ進化前に検索される要素がスキーマ進化後もす

トマトン TAp の状態集合を Np ，入力状態集合を NI p ⊂ Np ，

べてもしくは一部が存在する場合は，それらを検索できるよう

出力状態集合を NO p ⊂ Np と表す．

に p を修正する．

4. 3. 1 p1 /p2 の場合
p1 ，p2 はそれぞれ有限木オートマトン TAp1 ，TAp2 に変換更新操作が要素の削除の場合– スキーマ進化前には p で検索されていた要素がスキーマ
進化後にすべて消失する場合，その旨を表示する．

済みであるとする．TAp1 の出力状態と，TAp2 の入力状態以外•の状態のペアや，TAp1 の出力状態以外の状態と，TAp2 の入力– スキーマ進化前と同じ結果を得られるように p を修正状態のペアが，積を取ったオートマトンの状態に現れないように積を取る．すなわち，積を取ったオートマトン TAp1/p2 の状
態集合は次のようになる．

更新操作が要素の追加・削除以外の場合する．
また，述語を含む XPath 式 p は述語を削除した式 p0 と先頭から各述語までの式 pi に展開する．展開して得られた式を入力として使用する．例えば，p=/a/b[c]/d は次の 2 つの式に展して一回のみ使用されている．90 式の内 descendant-or-self 軸

開される．

が含まれているのは，78 式である．スキーマ進化後に要素の削

p0 = /a/b/d

除により，使用できなくなる式は 5 式存在する．また，述語を

p1 = /a/b/c含む式を 4 式生成した．4 式の内，3 式が要素の削除の影響を

アルゴリズムを図 1 に示す．更新操作 op が要素の追加の場

受ける式，1 式が要素の挿入の影響を受ける式となっている．

合，アルゴリズムの構成方針より XPath 式 p に修正を行わな

上記の XPath 式を本アルゴリズムで修正した．スキーマ進い（4〜5 行目）．op が要素の削除の場合，p がスキーマ進化後化後に使用できる式は 85 式あり，更新前後のスキーマと修も使用できるかを判定し，使用できる場合は修正しない．使用

正前後の XPath 式を比較し修正後の XPath 式で修正前と同できない場合は，p が p0 ならスキーマ進化後に使用できない旨

じ要素が検索されることを確認した．また，スキーマ進化後を，p が pi ならスキーマ進化後に使用できなくなる部分式を pで使用できなくなる式は 5 式あり，スキーマ進化後に XPath

から削除する (6〜22 行目)．op が要素の挿入の場合，p に修正式が使えない旨が表示された．図 2 に修正前の 5 式 p1〜p5が必要かを判定し，必要な場合はロケーションステップを挿入を示す．p1〜p4 はそれぞれ，要素 REMARK の子要素 LIST，する位置を判定し XPath 式に新しいロケーションステップを挿NOTE，FIGURE，FORMULA が削除されたためスキーマ進

入する (23〜32 行目)．op が要素の抜き取りの場合，p に修正化後，検索対象が消失する．そのため，スキーマ進化後ではが必要かを判定し，必要な場合は抜き取るロケーションステッ

使用できない．p5 は，要素 COMPANY-DOC-INFO の子要素

プの位置を判定し XPath 式から抜き取る．このとき，抜き取

PRIVATE-CODES が削除されたため，スキーマ進化後では使られるロケーションステップ ls i が展開する前に述語を持つロ

用できない．

ケーションステップだった場合，ls i の軸が descendant-or-self
軸なら述語部分を削除する (33〜48 行目)．

XPath 式が述語を含む場合，展開した式を 1 つずつアルゴリ
ズムに入力し修正を行う．このとき，p0 から入力する．要素の述語を含む式では，p0 と p1 の共通の部分式は同じ修正が施された．述語を含む式 p6〜p9 及びそれぞれの展開した式，修正後の式を図 3，4，5，6 に示す．

•

p6 は要素 COMPANY-REVISION-INFO の子要素 RE-

削除により，スキーマ進化後に p0 が使用不可と判定された場

MARK が削除されるため，p61 の最後のロケーションステッ

合は，pi の修正は行わない．なお，展開された各式に対する修プが削除される．修正後の p61 は修正後の p60 の部分式となる

正では，p0 と pi で共通の部分式，上記例では「/a/b」に対しため，修正後の p6 は述語を含まない式となる．

ては必ず同じ修正が施される．

pi 内の述語に相当する部分を述語にし，p0 との共通の部分
式の最後の ls に述語を付与する．

6. 評

価

本章では，本アルゴリズムに対する評価について述べる．
本アルゴリズムを Ruby で実装し，実際にスキーマ進化が起•

p7 は要素 COMPANY-REVISION-INFO の子要素 RE-

MARK が削除されるため，p71 の最後のロケーションステッ
プが削除される．p71 は p7 の述語部分を展開した式であるため，p71 の最後のロケーションステップが削除された場合でもスキーマ進化後に p7 は使用できる．

•

p8 は要素 COMPANY-REVISION-INFO の子要素 RE-

MARK が削除されるため，p80 がスキーマ進化後に使用でききた DTD を用いて，スキーマ進化前の DTD に妥当な XPath

なくなる．よって，p81 の修正結果に関わらずスキーマ進化後式を本アルゴリズムでスキーマ進化後の DTD に妥当となるよでは p8 は使用できない．

う修正をした．

•

p9 は要素 P と FT・STD の間に要素 L-1 が挿入される実験に使用したスキーマは MSRMEDOC [6] のバージョン

ため，p90 と p91 でそれぞれ L-1 を指定するロケーションス

2.1.1 D とバージョン 2.2.2 D’ である．D の要素数は 185 個，

テップが挿入された．このとき，p91 では，述語部分に L-1 がD’ の要素数は 205 個，D から D’ へのスキーマ進化では，更新挿入されたとみなす．そのため，修正後の p9 では述語部分と操作の総数は 191 個，本アルゴリズムが対象とする更新操作の述語の外に L-1 を指定するロケーションステップが存在する．

数は 99 個となった．本アルゴリズムが対象とする更新操作のスキーマを木オートマトンに変換して利用しているため，本

内訳は，要素の追加が 61 個，要素の削除が 11 個，要素の挿入

稿で評価を行っていない DTD 以外の XML の主要なスキーマ

が 27 個となった．本アルゴリズムの対象外の更新操作は演算にも本アルゴリズムは適用可能であると考えられる．また，述子の追加のみであった．要素の抜き取りはこのスキーマ進化で語を含む XPath 式は展開することで対応することができた．

は行われていなかった．そのため，今回の評価実験では要素の抜き取りに関する評価は行わない．

7. む す び

XPath 式は，D に妥当な XML データから XQgen [7] で生

本稿では，木オートマトンに基づいて，スキーマに対して行成した 90 式を使用した．生成した XPath 式は，平均ロケー

われた更新操作を用いて XPath 式を修正するアルゴリズムをションステップ数は 5 ステップ，最小ロケーションステップ数

提案した．

は 4 ステップ，最大ロケーションステップ数は 7 ステップであ

今後の課題として，要素の抜き取り・述語を含む XPath 式

る．使用された軸は child 軸と descendant-or-self 軸のみ，述に対する実用性の検証・評価を行うことが考えられる．また，語は含まれない．また，descendant-or-self 軸は一つの式に対より一般的な XPath 式に対応できるようにアルゴリズムを拡入力: スキーマ進化前の DTD D，XPath 式 p
D に対する更新操作 op
出力: 妥当な XPath 式

1. D の有限木オートマトン TAD =(ND , Σ, sD , PD ) を構成する
2. p の有限木オートマトン TAp =(Np , Σ, sp , Pp ) を構成する
3. switch op
4. case ins elm tree(a, A, b, B, i)
5.

修正なし

6. case del elm tree(a, A, i)
7.

TAD に対して op を適用し，スキーマ進化後の有限木オートマトン TAD′ = (ND′ , Σ, sD′ , PD′ ) を構成する

8.

TAD′ と TAp の積オートマトン TAD′ p = (ND′ ×Np , Σ, sD′ ×sp , PD′ p ) を構成する

9.

if TAD′ p が構成された then

10.
11.

修正なし

else if XPath 式==p0 then12.

「p はスキーマ進化後では使用不可能」と出力

13.

else

14.

TAD と TAp の積オートマトン TADp = (ND ×Np , Σ, sD ×sp , PDp ) を構成する

15.

C ← PD における左辺が A かつ右辺のラベルが a の遷移規則における位置 i の状態

16.

if PDp に A から C への遷移を表す遷移規則が存在する then17.

revision ← p における上記の遷移規則に対応する ls の位置

18.

for i ← revision to m dols[i] を削除;

19.
20.
21.
22.

end
end
end

23. case agg elm tree(a, A, b, B, i)
24.

C ← PD における左辺が A かつ右辺のラベルが a の遷移規則における位置 i の状態

25.

TAD と TAp の積オートマトン TADp = (ND′ ×Np , Σ, sD′ ×sp , PD′ p ) を構成する

26.

if PDp に A から C への遷移を表す遷移規則が存在する then27.

revision ← p における上記の遷移規則に対応する ls の位置

28.

for i ← m+1 to revision+2 do
ls[i] ← ls[i-1];

29.
30.

end

31.

ls[revision+1] ← /child::b

32.

end

33. case ext elm tree(a, A, i)
34.

C ← PD における左辺が A かつ右辺のラベルが a の遷移規則における位置 i の状態

35.

TAD と TAp の積オートマトン TADp = (ND′ ×Np , Σ, sD′ ×sp , PD′ p ) を構成する

36.

if PDp に A から C への遷移を表す遷移規則が存在する then37.

revision ← p における上記の遷移規則に対応する ls の位置

38.

if ls[revision+2] から述語部開始 && χ[revision+1] == descendant-or-self thenfor i ← revision to m do

39.

ls[i] を削除;

40.
41.

end

42.

else

43.

ls[revision+1] ← χ[revision+1]::l[revision+2]

44.

for i ← revision+2 to m-1 dols[i] ← ls[i+1];

45.
46.
47.
48.

end
end
end

49. end
50. return p;
図1

アルゴリズム•

p1 = /MSRREP/MATCHING-DCIS/MATCHING-DCI/REMARK/LIST/ITEM•

p2 = /MSRREP/MATCHING-DCIS/MATCHING-DCI/REMARK/NOTE•

p3 = /MSRREP/MATCHING-DCIS/MATCHING-DCI/REMARK/FIGURE/DESC•

p4 = /MSRREP/MATCHING-DCIS/MATCHING-DCI/REMARK/FORMULA/FORMULA-CAPTION/LONG-NAME•

p5 = //ADMIN-DATA/COMPANY-DOC-INFOS/COMPANY-DOC-INFO/PRIVATE-CODES/PRIVATE-CODE
図2•

要素の削除により使用できなくなる式

修正前

p6 = //DOC-REVISION/COMPANY-REVISION-INFOS/COMPANY-REVISION-INFO[REMARK]/COMPANY-REF
p60 = //DOC-REVISION/COMPANY-REVISION-INFOS/COMPANY-REVISION-INFO/COMPANY-REF
p61 = //DOC-REVISION/COMPANY-REVISION-INFOS/COMPANY-REVISION-INFO/REMARK•

修正後

p = //DOC-REVISION/COMPANY-REVISION-INFOS/COMPANY-REVISION-INFO/COMPANY-REF
p60 = //DOC-REVISION/COMPANY-REVISION-INFOS/COMPANY-REVISION-INFO/COMPANY-REF
p61 = //DOC-REVISION/COMPANY-REVISION-INFOS/COMPANY-REVISION-INFO
図 3 p6 に対する修正•

修正前

p7 = //DOC-REVISION[COMPANY-REVISION-INFOS/COMPANY-REVISION-INFO/REMARK]/MODIFICATIONS/MODEFICATION
p70 = //DOC-REVISION/MODIFICATIONS/MODEFICATION
p71 = //DOC-REVISION/COMPANY-REVISION-INFOS/COMPANY-REVISION-INFO/REMARK•

修正後

p7 = //DOC-REVISION[COMPANY-REVISION-INFOS/COMPANY-REVISION-INFO]/MODIFICATIONS/MODEFICATION
p70 = //DOC-REVISION/MODIFICATIONS/MODEFICATION
p71 = //DOC-REVISION/COMPANY-REVISION-INFOS/COMPANY-REVISION-INFO
図 4 p7 に対する修正•

修正前

p8 = //DOC-REVISION[COMPANY-REVISION-INFOS/COMPANY-DOC-INFO/PRIVATE-CODES/PRIVATECODE]/DOC-REVISIONS/DOC-REVISION/COMPANY-REVISION-INFOS/COMPANY-REVISION-INFO/REMARK
p80 = //DOC-REVISION/COMPANY-REVISION-INFOS/COMPANY-REVISION-INFO/REMARK
p81 = //DOC-REVISION/COMPANY-REVISION-INFOS/COMPANY-DOC-INFO/PRIVATE-CODES/PRIVATECODE•

修正後

p8 はスキーマ進化後に使用できない
p80 はスキーマ進化後に使用できない
p81 は p80 がスキーマ進化後に使用できないので，修正しない
図 5 p8 に対する修正•

修正前

p9 = //P[FT]/STD
p90 = //P/FT
p91 = //P/STD•

修正後

p9 = //P[L-1/FT]/L-1/STD
p90 = //P/L-1/FT
p91 = //P/L-1/STD
図 6 p9 に対する修正張すること，例えば parent 軸など別の軸への対応することが考えられる．
更に，スキーマ進化中に更新操作のバッティングする場合，
例えば要素 a を削除した後に同じ位置に要素 a を追加する場
合，XPath 式の修正が冗長となるためその場合の最適化を検討する．また，行われたスキーマ進化がどのような意味・意図のもと行われたかについても検討する．
文

献[1] 長谷川数馬, 池田光雪, 鈴木伸崇 ： スキーマ進化に伴う XPath
式修正アルゴリズム，情報処理学会第 74 回全国大会 (2012).
[2] Z. G. Ives, A. Y. Halevy, and D. S. Weld “An XML query engine for network-bound data”, The VLDB Journal, Vol.11,
No.4, pp. 380–402, 2002.
[3] Nobutaka Suzuki： An Algorithm for Inferring K Optimum
Transformations of XML Document from Update Script to
DTD，IEICE TRANSACTIONS on Information and Systems (2010).
[4] 森本卓爾, 橋本健二, 石原靖哲, 藤原融 ： 木埋め込み関係に基づ
く XML スキーマ進化に応じた XPath 問い合わせ変換，電子情報通信学会技術研究報告 (2007).
[5] 大野敦司, 石原靖哲, 藤原融 ：XML スキーマで定義された型とXPath 式との対応の解析手法，情報処理学会報告 (2009).
[6] “MSR Download” MSR Home,
http://www.msr-wg.de/medoc/downlo.html, (accessed 201302-10).
[7] XQgen. http://sites.google.com/site/xmlqgen/, (accessed
2013-02-10).