論文――――――――――――――――――――――――――――――――――――

情報統合支援を目的としたXMLの意味情報の抽出
Extracting Semantic Information from XML
Data to Support Information Integration

古川 夏子♥

Atsuyuki MORISHIMA

XMLはデータ交換のためのデファクトスタンダードとしての地位を既に確立している．XMLデータの量が劇的に増加するにしたがい，情報統合やデータ再構成の問題の重要性が増大するのは明らかである．我々はリバースエンジニアリング的な発想で，既存のXMLデータの情報統合の支援を行う問題に焦点を当てる．具体的には，XMLのスキーマやインスタンスから高水準の意味情報を作成する手法を提案する．
XML has become the de facto standard for datainterchange on the Internet. As the amount of XML data
grows, there are increased needs for information integration
and restructuring. We address the problem of supporting
such processes by “reverse engineering” XML data; This
paper proposes a framework for extracting high-level
semantic information from XML schemas and instances.

1. はじめにXMLはインターネットにおけるデータ交換のためのデファクトスタンダードとしての地位を既に確立している．現実に作成・管理されるXML データの量が劇的に増加するにしたがい，次のような問題の重要性が増すことは明らかである．
（ 1 ）情報統合の問題: 異なる組織が類似の種類のXMLデータを個別に持っているが，それぞれスキーマ(DTDやXMLSchemaなど) が異なる．これらを統合したい．
（ 2 ）データ再構成の問題: 情報システムの移行や拡張にともない，XMLのスキーマを変更したい．また新旧スキーマ間のマッピングとそれらの間でデータの移行を行いたい．
これらの情報統合やデータの再構成を行うには，オントロジなどの意味情報の利用が有効であることが知られている[2] [4][7]．しかし，XMLの意味情報は，リレーショナルデータベースやオブジェクト指向データベースなどに比べ，同種の情報を表すスキーマのバリエーションがより多くなるため，一般に問題が複雑になる．その理由として，(1)正規化の理論やスキーマの設計論が確立していないこと，(2)要素の入れ子構造や選択構造など多様な構成子を持つこと，(3)クラスなどの概念がなく，意味情報に1対1対応しないことなどの要因があげられる．
例えば，図1のUMLクラス図で表される情報をXMLで表現する場合を考える．このとき，例えば図2(a)(b)のようなスキーマ
学生会員 芝浦工業大学大学院工学研究科
m102186@sic.shibaura-it.ac.jp♣
正会員 筑波大学知的コミュニティ基盤研究センター
amorishima@acm.org

1で表現することが可能である．これらは同じ情報をかなり異なる方法で表現している．たとえば，(a)は教員と学生を異なる型の要素で区別しているのに対し，(b)では同じ型の要素を属性を用いて区別している．

森嶋 厚行♣

Natsuko FURUKAWA♥DBSJ Letters Vol.2, No.2

図1 UMLクラス図の例
Fig. 1 A UML class diagram

univ=(dept*)
dept=(did, dname, people)
people=(prof*,student*)
prof=(pid,name)student=(sid, name)(a)univ=(dept*,person*)dept=(@did:ID, dname)person=(pid, @type, name,@did:IDREF)(b)

図2 図1のクラス図のための2種類のスキーマ
Fig. 2 Two Different Schemas for the Class Diagram in Fig. 1
我々はリバースエンジニアリング的な発想で，既存のXMLデータの統合や再構成の支援を行うフレームワークの問題に焦点を当てる．本フレームワークでは，既存のXMLスキーマやインスタンスから図1のような意味情報を作成する．我々は，このようなフレームワークの鍵となる技術としてCX図(Class-XMLmapping Diagram)を提案する．CX図は，XMLの意味情報がXMLインスタンスにどのようにマッピングされているかを表す表現である．情報統合やデータ再構成などの応用を想定しており，XMLとのマッピング情報を維持したままCX図の操作を行うオペレータが定義されている．本稿では，CX図とそのオペレータ，CX図の作成支援システムについて説明する．このアプローチを用いたデータ再構成については[8]で議論している．

2. Class-XML mapping Diagram
CX図の構成要素はUMLのクラス図のサブセットであり，クラス，関係(関連，汎化)，属性から構成される．集約は名前has を持つ関連として表現される．これらの各構成要素には，XSBE (XML-Semantics Binding Expression)が付加されている．これは，各構成要素とXMLインスタンスの関係を表現する式である．図3はCX図の例である．
図3の(a)，(b)はそれぞれ図2(a)，(b)のスキーマで規定されるXMLデータと意味情報を結びつけるXSBEである．XSBEは各クラス，関連，属性に付加される1．本稿では，クラスのXSBEはクラスの脇に記述する．関連のXSBEは，関連の横に並べて記述している．属性のXSBEは，各属性の横に記述している．
UMLのクラス図では汎化においては上位クラスからの継承される属性を省略するが，CX図では全て記述する．
一般にXSBEは図4の構文を持ち，かつ付加対象の種類(クラ1図では一部の構成要素に対してのみ XSBE を記述している．

日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――
a0a1b1a4
b4a3
b3a2b2a5a4b4 a6
b5a0:$i 1 in /univ
a1:a4 union a5a2:$k 1 in /univ/dept/dida3:a7 union a8a4:$k 2 in /univ/dept/people/prof/pid
a5:$k 3 in /univ/dept/people/student/sid
a6:$x 1 in /univ/dept/people/prof,$v 1 in $x1/name, $k 2 in $x1/pid
a7:$x 2 in /univ/dept, $k 1 in $x2/did, $k 2 in $x2/people/prof/pid
a8:$x 3 in /univ/dept, $k 1 in $x3/did,$k 3 in $x3/people/student/sid(a)b2: $k 2 in /univ/dept/did
b1: $k 1 in /univ/person/pid
b3: $x 1 in /univ/person, $k 1 in $x1 /pid, $k 2 in univ/dept/@didwhere $x 1 /@did = $k 2
b4: $x 2 in /univ/person, $k 3 in $x 2/pid,where $x 2/@type = profb5: $x 3 in /univ/person,$v 1 in $x 3/name, $k 3 in $x 3/pid,(b)where$x 3/@type = prof

図3 CX 図の例
Fig. 3 Examples of CX diagrams
ス，関連，属性など) によって，記述に制約がある．各XSBEはリレーションを表現する．例えば，図3(a)の関連 belongsToのXSBE a3が表すリレーション(R(a3)と表記)は$k 1 , $k 2に対応する属性を持つリレーションである2．XSBEのunion演算は各XSBEが表すリレーションが和両立で無ければならない．
<xsbe>::= (<xsbe>) union (<xsbe>)￨ <expr> { , <expr> } [ <whereExpr> ]<expr>::= <var> in [ <var> ] <locationPath><whereExpr>::= where <predicates>

図4 XSBE の構文
Fig. 4 XSBE’s syntax
付加対象の種類ごとのXSBEの制約は次の通りである．
クラスのXSBE．(制約1) 変数として，ID変数($kj もしくは$ij ) を唯一つ持つ．ここで$kj はこのクラスのインスタンスのキー値に束縛される変数である．図3(a)において，クラス profのXSBEはID変数 $k 2 を持つ．また$ij は，このクラスのインスタンスのアイデンティティ要素に束縛される変数である．ここでアイデンティティ要素とは，クラスの各インスタンスと1対1対応する要素である．例えば，図3において，a0の$i 1 はクラス univのアイデンティティ要素 univに束縛される．(制約2) リレーシ
ョン Rのリレーション属性のうち，ID変数に対応するものをID(R)と表記する．このとき，あるクラスのXSBE b から求められるリレーションπID (R(b ))(R(b ))は，そのクラスのインスタンスすべてのID値(キー値もしくはアイデンティティ要素) の集合となる．例えば，図3(a)においてクラス profのリレーション π$k 2(R(a4))は，pidの集合となる．
関連のXSBE．(制約1) 変数として，接続されたクラス全てのID変数を持つ．(制約2) ある関連のXSBE b から求められるリレーション πID (R(b ))(R(b )) の各タプルは，接続されたクラス間
2 XSBE に union 演算がある場合は最初のオペランドの変数名がリレーションの属性名となる．

2

DBSJ Letters Vol.2, No.2の関連のインスタンスである．例えば，図3(a)の関連 belongsToのリレーションは，π$k 2, $k 1(R(a3)) となる．このリレーションにタプル (k,l ) が含まれる時，k で表されるpersonがl で表されるdeptに所属することを表す．
属性のXSBE．(制約1) 変数として，属性が所属するクラスのID変数と，値変数($v j )を一つ持つ．(制約2) リレーション Rのリレーション属性のうち，値変数に対応するものをV (R)と表記する．このとき，クラスc の属性a のXSBE b から求められるリレーションπID (R(b )),V (R(b ))(R(b ))は，タプル(c のID値,a の値)の集合である．例えば，図3(a)のクラス profの属性 nameは，ID変数$k 2と値変数$v 1を持ち，XSBE a6のリレーションはπ$k 2,$v 1(R(a6))となる．このリレーションにタプル(m ,n )が含まれてる時，m で表されるprofのnameがn である事を表す．キー属性の場合は，ID (R(b )) = V (R(b ))となるため，XSBEが表すリレーションは単項リレーションπID (R(b ))(R(b ))とする．
CX図は次のように定義される．
定義．CX図は4つ組(N ,R ,name ,b )である．ここでN = C ∪A，C はクラス集合，A は属性集合，R : N ×N はクラス間の関係の集合である．name : (N ∪R ) → String はクラス，属性，および関係の名前をあらわす関数である．また，b : (N ∪R ) →BE は各ノードおよび関連に付随したXSBEを求める関数である．BE は図4で規定されたXSBEの集合である．

3. オペレータ
本節では，CX図のオペレータについて説明する（図5）．これらを適用すると，CX図の構造とXSBEが変更される．
主な目的
クラスの操作関連の操作
属性の操作
その他演算子(*は複合演算子)
SupC, SubC, RC
CR, UR, NR, RR
CA, RA
Key, RN, A2R, C2A*

図5 オペレータ一覧
Fig. 5 Operators
以下の説明において，cxd = (N ,R , b ,name ),N = C ∪A とする．

3.1 クラスの操作
SupC 演算．与えられたcxd に関して，c 1 ,c 2 ∈C はクラスであるとする．SupC(c 1,c 2)→c’ (cxd )は，cxd にR(c’ ) = R(c 1)∪R(c 2)となるようなクラスを追加する演算である（図6）．形式的には，(N’ ,R’ ,b’ ,name’ ) = SupC(c 1,c 2)→c’ (cxd )と定義する．ただし，
N’ = C’ ∪A’C’ = C ∪{c’ }A’ = AR’ = R ∪{(c 1,c’ ), (c 2, c’ )}ε(x = c’ )name’ (x ) =isa
(x = (c 1 ,c’ ) or x = (c 2 ,c’ ))name (x ) otherwiseb’ (x )=b (c1 ) union b(c2 )(x = c’ )b (x )
otherwise(a) オペレータ適用前(b) オペレータ適用後
図6 SupC 演算例
Fig. 6 SupC operation

日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――
SubC 演算．与えられたcxd に関してc ∈C はクラスであるとする．また，p を条件式とする．SubC(c ,p )→c’ (cxd )は，cxd にR(c’ ) =σp (R(c ))となるようなクラスを追加する演算である．
RC 演算．与えられたcxd に関してc ∈C はクラスであるとする．RCc (cxd )は，cxd からc およびc に接続された関連および属性を除去する演算である．

3.2

関連の操作

CR 演算．与えられたcxd に関して，r 1= (c 1,c 2),r 2= (c 2,c 3)∈R は関連であるとする3．CR(r 1,r 2)→r’ (cxd )は，cxd にR(r’ ) =π￢common (R(r 1);R(r 2))(R(r 1) ⋈ R(r 2))となるような関連を追加する演算である(図7)．ここで，￢common (S ,T )はリレーション
S ,T の属性のうち，S ,T の双方には現れないものである．形
式的には，(N’ ,R’ ,b’ ,name’ ) = CR(r 1,r 2)→r ’ (cxd )と定義される．
ただし， N’ = C ∪A
R’ = R ∪{(c1 ,c3 )}ε(x = (c1 ,c3 ))name’ (x ) =name (x ) otherwiseb’ (x )
=Join (b (r 1),b (r 2),p )(x =(c 1,c 3 ))otherwiseb (x )
ここで，Join (b 1,b 2,p )はR(r 1)とR(r 2)を条件 pで結合するXSBEである．p は，R (r 1)とR (r 2)に共通のID変数 k i に関するK i=K ’i の並びである．

(a) オペレータ適用前(b) オペレータ適用後
図7 CR 演算例
Fig. 7 CR operation
UR 演算．与えられたcxd に関してc 1 ,c 2∈C はクラスであり，s は関連の名前を表す文字列とする．URs →(c 1,c 2,r’ )(cxd )は，cxdにR(r’ ) = ∪r i ∈R s R(r i )となるようなc 1とc 2間の関連 r’ を追加する演算である．ここで，R s は，名前にs を持つ関連 r s = (ck ,c l )の集合である．c k は，c 1もしくはそのサブクラスであり，c l はc 2もしくはそのサブクラスである．
NR 演算．与えられたcxd に関してc ∈C はクラスであるとする．NRc →r’ (cxd )は，c に接続されるすべてのクラスを結ぶn項
関連 r’ を作成しcxd に追加する（図8）．ここで，R(r’ ) =π￢
common (R(ri ))(⋈r i ∈R c R(r i ))となる．R c はc に接続する関連の集合である．

r’(a) オペレータ適用前(b) オペレータ適用後
図8 NR 演算例
Fig. 8 NR operation
RR 演算．与えられたcxd に関してr ∈R とする．RRr (cxd )は，cxd からr を除去する演算である．

3.3

属性の操作

CA 演算．与えられたcxd に関してc 1∈C はクラス，a ∈A は属性であるとする．a が属するクラス c 2は，c 1と1対1関連 r∈R で接続されていなければならない．この時，CAa →(c 1,a’ )(cxd )は，a をc 1の属性 a’ としてコピーする演算である(図9)．ここ
3 本論文では，関連 rk がクラス ci，cj を結ぶ時，rk = (ci,cj)と記述する．

3DBSJ Letters Vol.2, No.2

で，R(a’ ) = πK (c 1),V (a )(R(r ) ⋈ R(a ))となる．

(a) オペレータ適用前(b) オペレータ適用後
図9 CA 演算例
Fig. 9 CA operation
RA 演算．与えられたcxd に関してa ∈A とする．RAa (cxd )は，cxd からa を除去する演算である．

3.4 その他
Key 演算．与えられたcxd に関して，c ∈C はクラス，a ∈Aはc の属性であるとする．Keyc ,a (cxd )は，c のID変数を$ij から$kj に変更する．ここで$kj はa の属性値 v に束縛される．
この演算はクラス図の構造には影響を与えないが，c およびcに直接接続された全ての関連・属性のXSBEに影響を及ぼすため，やや複雑な操作となる．演算結果において，元のa に対応するものをa’，c に対応するものをc’，c に接続された属性 a iに対応するものをa’i ，c に接続された関連 r i に対応するものをr’i とする．このとき，結果のXSBEが計算するリレーションはそれぞれ次のようになる．
・R(a’ ) = δV (a )←k i (πV (a )(R(a )))・R(c’ ) = δV (a )←k i (R(a’ ))・R(a’ i ) = δV (a )←k i (π￢common (R(a ),R(a i ))(R(a ) ⋈ R(a i )))・R(r’ i ) = δV (a )←k i (π￢common (R(a ),R(r i ))(R(a ) ⋈ R(r i )))ここで，δV (a )←k i はV (a )中の属性名をキー属性名に変換する．
RN 演算．与えられたcxd に関して，x ∈N ∪R はクラス，属性，および関連のいずれかであるとする．またs は文字列であるとする．この時，RNx ,s (cxd )はx の名前をs に変更する．
A2R 演算．属性から関連を作る演算である(図10)．与えられた
cxd に関して，c 1, c 2∈C はクラス，a 1, a 2∈A はそれぞれc 1,c 2の属性であるとする．(すなわち，(c 1, a 1), (c 2, a 2)∈R である．)この時，A2R(c 1,a 1),(c 2,a 2)→r’ (cxd )は新たな関連 r’ をcxd に追加する．ただし，R(r’ ) = πK (a 1),K (a 2)(R(a 1)⋈V (a 1) = V (a 2)R(a 2))となる．

(a) オペレータ適用前(b) オペレータ適用後
図10 A2R 演算例
Fig. 10 A2R operation
C2A 演算．クラス c をクラス c’ の属性 a’ に変換する複合演算である．c , c’ ∈C ,a ∈A ,(c , a ),(c ,c’ )∈R ,name ((c ,c’ )) ≠isa , name (c ) = s とする．このとき，C2Ac →(c’ ,a’ )(cxd ) =RCc (CAa →(c’ ,a’ )(RNa ,s (cxd ))) と定義する．

4. 意味情報の作成支援
本章では，本システムを用いた意味情報の作成の概要について説明する．意味情報の作成は次の3段階から構成される．(フェイズ1)システムがXMLのスキーマを基に単純な規則を用いてデフォルトのCX図を作成する．(フェイズ2)システムがヒューリスティクスと3章で説明したオペレータを用いてフェイズ1で作成したデフォルトのCX図を変更する．(フェイズ3)利用者がオペレータを用いてフェイズ2の結果を変更する．

4.1 フェイズ1
図2(b)にフェイズ1を適用した結果(図11)を用いて説明する．

日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――
クラスの生成．スキーマに現れる各要素毎に，一つのクラスを作成する．例えば，図11のクラス personは図2(b)の要素 personに対応する．クラス personのXSBEは$i 1 in /univ/personとなる．
属性の生成．スキーマの要素属性毎にクラス属性を生成する．
例えば，図 11 のクラス person に属性 did が生成される．この属性の XSBE は$i 1 in /univ/person, $v 1 in $i 1/@did となる．
関連の生成．要素間に親子関係があるとき，それらの要素に対応したクラス間を二項関連で結び，関連名を has とする．例
えば，図2(b)の要素 univ と person間は親子関係であるため，図11のクラス univと person間に関連 hasが生成される．関連のXSBEは，$i 0 in /univ, $i 1 in $ i 0/personとなる．
d0:$i 0 in /univ
d1:$i 1 in /univ/person
d2:$i 0 in /univ,$i 1 in $i 0/person
d3:$i 1 in /univ/person,$v 1 in $i 1/@did
d4:$i 2 in /univ/person/pid,$v 2 in $i 2/text

d0d2
d1：d3

- te x t: d 4- te x t- te x t

図11 フェイズ１の出力Fig. 11 Output of phase1

DBSJ Letters Vol.2, No.2

(1)意味情報の構成要素とXMLインスタンス間との関係の記述を明示的に保持しない．(2)意味情報のオペレータが定義されていない．(3)作成される意味情報が，与えられたスキーマとほぼ1対1対応する．
C-Web [1]では，XSBEと同様，意味情報の構成要素とXMLインスタンス間とのマッピングを表すための言語を提供している．しかし言語の表現力がXSBEより小さく，XSBEでのみ記述可能なマッピングが存在する．また，C-Webでは意味情報の自動生成については議論していない．

6. おわりに
本稿では，XMLデータの意味情報の表記法および意味情報の作成支援システムについて説明した．今後の課題としては，ヒューリスティクスの適用手順の明確化，システムの実装などがある．

[謝辞]
ゼミなどでご議論いただきました芝浦工業大学工学部情報工学科古宮誠一教授に感謝いたします．本研究の一部は文部科学
省科学研究費補助金若手研究(B)(課題番号15700108) による．

4.2 フェイズ2[文献］

フェイズ2では，システムがヒューリスティクスを利用してフェイズ1の結果を変更する．変更には3章で定義したオペレータを利用する．ヒューリスティクスの一部を次に示す．
・ 同じ名前を持つID属性とIDREF属性はA2Rオペレータを用いて関連に変更する．
・ テキストノードしか持たないクラスはC2Aオペレータを用いて属性に変換する．
・ ID属性を持つクラス c は，Keyオペレータを用いてc のID変数をキー変数と変更する．
フェイズ2では図11のcxd 1に対して次の変換を行う．
cxd 2 = (Key c 2,a 6 (RA a 5 (A2R (c 1,a 5 ),(c 2,a 6 )→r’ (C2A c 5 →(c 2,a3 )(C2A c 4 →(c 1,a 2 )(C2A c 3 →(c 1,a 1 )(cxd 1)))))))
ただし，c 1はperson クラス，c 2はdept クラス，c 3はpid クラス，c 4はname クラス，c 5はdname クラス，a 5はc 1のdid 属性，a 6はc 2のdid 属性である．

[1] B. Amann, I. Fundulaki, M. Scholl, C. Beeri, Anne-Marie
Vercoustre: ”Mapping XML Fragments to Community
Web Ontologies.”, WebDB 2001: 97-102[2] S. Bergamaschi, S. Castano, M. Vincini: ”Semantic
Integrationof Semistructured and Structured DataSources.”, SIGMOD Record 28(1): 54-59 (1999)[3] R. S. Mello, C. A. Heuser: “A Rule-Based Conversion of aDTD to a Conceptual Schema.”, ER 2001: 133-148[4] R. S. Mello, C. A. Heuser: “A Bottom-Up Approach for
Integration of XML Sources.”, Workshop on Information
Integration on the Web 2001: 118-124[5] M. Mani, D. Lee, R. R. Muntz: “Semantic Data Modeling
Using XML Schemas.”, ER 2001: 149-163[6] E. Pitoura, O. A. Bukhres, A. K. Elmagarmid: “Object
Orientation in Multidatabase Systems.”, ACM
Computing Surveys 27(2): 141-195 (1995)[7] P. F. Patel-Schneider, J. Simeon: “The Yin/Yang Web:XML Syntax and RDF Semantics.”, WWW 2002: 443-453[8] 古川夏子，森嶋厚行: “意味情報を用いたXQuery問合せ作成
支援システムの開発”,情報処理学会第65回全国大会講演論文集(3): 9-10 (2003)．

4.3 フェイズ3
フェイズ3では，フェイズ2の結果に対して利用者がオペレータを適用し，最終的なCX図を得る．フェイズ2の結果から図3(b)を求めるためには，次の演算を行う必要がある．
cxd 3 = (RN r’ ,” belongsTo ” (RN c 7, ” student ” (RN c 6,” prof ” (SubC c 1→
(c 7,p 2)(SubC c 1→(c 6,p 1)(RN a 1,” id ” (Key c 1,a 1(RA a 4(cxd 2))))))))))
ただし，p 1は$k1/../@type=” prof ”，p 2は$k1/../@type=”student”，a 4はc 1のtype 属性である．

5. 関連研究
DTDやXML SchemaなどのXMLスキーマ言語から，意味情報を生成する研究はいくつか存在する．Melloらの研究[3] [4]ではDTDをConceptual Schemaに変換するための規則を定義している．また，XMLのスキーマ言語の一つである
XGrammar[5]では，EERダイアグラムとの相互変換方法が与えられている．これらが本研究と異なる点は次の通りである．

4古川 夏子Natsuko FURUKAWA

芝浦工業大学大学院工学研究科修士課程在学中． XML処理・管理，XMLの情報統合などに興味を持つ．情報処理学会，日本データベース学会各学生会員．

森嶋 厚行

Atsuyuki MORISHIMA

筑波大学知的コミュニティ基盤研究センター助教授．1998年
筑波大学大学院工学研究科修了．博士(工学)．情報統合，XMLとデータベース，Webの一貫性管理，Webアーカイブなどに興味を持つ．ACM, IEEE-CS, 情報処理学会，電子情報通信学会，日本データベース学会各正会員．

日本データベース学会 Letters Vol.2, No.2