関係問合せとXML問合せをともにサポートする
DBMSの構造

XMLデータベース
吉川正俊（京都大学）

XML programmingwith SQL/XML andXQuery by
J. E. Funderburk,
S. Malaika, B. Reinwald,
IBM Systems Journal,
Volume 41, Number 4,pp. 642-665 (2002)

XML文書のRDBへの格納
XML
programmingwith SQL/XMLand XQuery by
J. E. Funderburk,
S. Malaika,
B. Reinwald, IBM
Systems Journal,
Volume 41,
Number 4, pp.
642-665 (2002)

XML文書を分解し，既存DBMSのスキーマに写像した上で検索する方法

XML文書のRDBへの格納

 構造写像アプローチ

利用者, アプリケーション

考慮すべき点

XMLスキーマの有無
XPath, XQueryからSQLへの問合せ変換

XML文書, 木構造

XPath,
XQueryプリプロセッサ

結果の出力形式SQL– XML文書の論理構造（DTD）を表現するデー
タベーススキーマを定義 モデル写像アプローチ

問合せの処理効率
データ容量
 更新に対する頑健性


×

 RDB
 OODB– XMLデータモデルの構成要素（ノード，枝，経路など）を表現するデータベーススキーマを定義

DBMS

XML文書

1

XML文書を分解しデータベーススキーマに写像する方法 --- 関係データベースの場合考慮すべき点<emp><name>Joe Doe</name><age>30</age></emp>
構造写像アプローチ

 XPath, XQueryからSQLへの問合せ変換
 問合せの処理効率
 データ容量モデル写像アプローチ

 更新に対する頑健性

nodeemp
nameid parent nameage

12
3

Joe Doe 30
少数の文書構造（DTD）に従う大量のXML文書

11valueemp
name Joe Doeage30

DTDが不明または頻繁に更新される

木のノードラベリング手法
 設計目標– XPathの軸（特に親子，先祖/子孫関係）の高速計算– 短いラベル長– 更新に対する頑健性– XMLスキーマの考慮

木のノードラベリング手法

 ラベルの種類– Dietzの番号付け– 接頭辞ラベル– k分木への埋め込み

preorderpostorder
開始タグの出現順

終了タグの出現順

…

…
1210

7489351064978

156232

リージョン (region)

Dietzの番号付けスキーム
 (preorder, postorder)

ノード a はノード d の先祖⇔…

a.preorder < d.preorder…
(1,10)(2,5)

かつ
a.postorder > d.postorder

(7,6)
(4,4)

(8,9)
(9,7)

(10,8)

 開始タグの先頭からのバイト数と終了タグの先頭からのバイト数の対 それぞれの順序関係は，preorder, postorderと同じ 親子関係の判定は困難なので，レベル（根ノードからの距離）も合わせて記録することが多い

(3,1)

(5,2)

(6,3)

リージョン

VLEIコード [小林ら DBWS2003]<a><b><c></c></b></a>7

104

v0{0|1}* < v < v1{0|1}*
このコードによりpreorder, postorderの対で表現
ビット長を長くすることによりノード挿入に対処(1000,1111)

14

1

18
(1001,1)<a>bbb<c></c>bbbb</a>7(101,101)(11,111)(111,110)(1111,11)(10,1000)

101(110,1100)

18

接頭辞ラベル 親のラベルは子のラベルの接頭辞(1,1001)(1100,1000)

Dewey order 図書館で広く使われている分類法
1

1.1

1.2
1.1.2

1.3
1.3.1

1.3.2

1.1.1

1.1.2.1

1.1.2.2

3

ORDPATHノードラベル

ORDPATHノードラベル 最初は奇数のみを用いる
 挿入が生じた場合– 偶数をcaretとして用いる（偶数はレベルとして数えない）– 最後の数字は必ず奇数とする– 例： 3.5.5 と 3.5.7の間に挿入する場合は，3.5.6.1, 3.5.6.3, 3.5.6.5, … などを用いる

k分木への埋め込み

Unique identifier UID (Y.K.Lee, 96)– each internal nodesupposedly has the samechildren» maximal fan-out (= k)– enable computing the parentnode1

k=3

from a child node’s identifier⎢i − 2 ⎥parent (i ) = ⎢+ 1⎥⎦⎣ k5432678910111213

再帰的識別番号 (recursive UID)： 目的と設計原理

UIDの問題点
 enumerate virtual nodes
 identifiers increasing rate: max_fanout

tree_height⇒ 最悪の場合...

 ⇒ 実際に，以下の小さいXML文書でも表現できない．
Data setsize# element&attributes

max fanoutheight

Data set I(data on 20 persons)

7.6KB

201

11

11

Love’s Labor’s Lost
(plays grouped, collectionadded)

210KB

5057

434

7

 目的– overcome the node number limitation– while preserve order determination property
 設計原理– Nodes subsets managed in two levels– Global level:» these subsets identifiers are recognized.
– Local level:» nodes in each subset are managed– Global parameters: used in both levels.
» small enough» be comfortably loaded into the main memory

4

Example of 2-level UID

Parent - child determination

1,1

2,2

2,2

2,3

3,2



3,3

4,4

3,3

4,2

1.

5,5

4,3

5,2

5,3

– look at line 2 of K: local fan-out = 2– local index = ⎣ (7-2) / 2 +1 ⎦ = 3 > 1⇒ (2, 3, 0)

5,42.
2,6

Globalindex

Local
index

12345
1012345
92,7Localfanout
423232

3,8

3,10

10,9

10,2

10,3

10,4

10,6

5,8Suppose: κ = 4 and K is given
From (2,7,0) compute the parent node5,9

From (10, 9, 1) - a root
upper UID local area’s index = ⎣ (10-2) / 4 +1 ⎦ = 3
look at line 3 of K: local fan-out = 3
local index = ⎣ (9-2) / 3 +1 ⎦ = 3 > 1⇒ (3, 3, 0)––––

モデルアプローチに基づくRDBへの格納
 XMLスキーマの存在とは独立– どのような整形式 XML文書も格納可能

モデル写像アプローチ 問題– どのような関係データベーススキーマを設計するか？
» 枝アプローチ» 経路アプローチ– XML問合せからSQLへの変換をどのように行うか？

枝アプローチ XML木の枝の情報を格納するために関係を一つ設け，各枝を関係の組として格納する．
 各ノードに唯一の識別子が付与されていることを前提とする

readinglist

4courseid
CS405
isbntitle

v80-07232206-3

22booksummary

9 authorsauthors

title

Database
Management
Systems

author

26
last

first

first

Raghu

Johannes

Ramakrishnan

booktitle abstract

v24 25

10 author 15 author
last

paper

last
first

The Database...

SIGMOD’83

GehrkeThis book covers ...

GEM is a ...
Carlo

Zaniolo5枝アプローチの関係データベーススキーマ

枝アプローチの問合せ変換
 経路式の長さに比例した結合が必要

XPath:
SQL:/readinglist/book/titleSELECT e3.target
FROM Edge e1, Edge e2, Edge e3
WHERE e1.name = “readinglist”
AND e2.name = “book”
AND e3.name = “title”
AND e1.target = e2.source
AND e2.target = e3.source XPathの // を処理するためには，再帰結合が必要

経路アプローチ
XML文書内の経路を文字列として関係データベースに格納

経路アプローチ DTDの情報は利用しない– どのような整形式 XML文書も格納可能 XPathで表される経路に関する複雑な条件– SQLの文字列パターン照合と整数の比較に変換» 複雑な結合処理は不要– 通常の DBMS で提供されている索引を利用可（B+木，R木）

経路アプローチ XML木の経路を格納単位とする
 ノードのラベル付け– XML木のトポロジーの保存– 問合せ，更新処理の高速化

XRel XPathで表される経路に関する複雑な条件– SQLの文字列パターン照合と整数の比較に変換» 複雑な結合処理は不要– 通常の DBMS で提供されている索引を利用可（B+木，R木）

6

Storing XML Documents in RDB

XML文書

User, Application
XML, DOM, etc

XPath
Translation

Formatting

SQL
SQL
Element

Attribute

Text

bookauthor

Path

DBMS

XML Documents

XML文書の分解，表現の単位
book(1, 125)

単純経路式

(27, 41)

Joe
Nick(65, 67) (82, 85)/book/price
リージョン : (Start, End)

Attribute

first

last

Joe

Nick

12

Text

Path
pathname
pathID
1/book
2/book/title/book/author
3…
･Element
docID pathID pos#12
20, 49

経路ID
経路式 book/book (1, 125)
1/book/title
2/book/author
3priceauthorstyletitle
4 118)
text /book/author/first(20, 49) (50, 101) (102,5(1,125) /book/author/last/book/price612
History first
lastof Nara (58, 75) (76, 92) (109,110)
Text(27, 41)docID pathID valuepos#1
2
History 27, 41
Joe
Nick
Attribute(65, 67) (82, 85)
docID pathID attname attval pos
#1
1
style
text 1, 125

問合せ変換例(1) ~単純経路式~

検索方法~問合せの書き換え~/book/title//last//author[first=‘Joe’]Elementprice

XML文書の関係への格納方法/book/book/@stylestyletitle
authorprice
text(20, 49) (50, 101) (102, 118) /book/title(1,125)/book/author/book/author/first
History
first last
12of Nara (58, 75) (76, 92) (109,110)/book/author/last

Pathpathname

Element
pathID

1/book
2/book/title/book/author 3…
･ XPathの基本は / または // と要素型をつないだ列
 データベースでは XML 文書を単なる文字列として格納 書き換えについては, SQL のもつ文字列照合を行う述語を利用<book style=‘text’><title>History of Nara</title><author>style<first>Joe</first>
title
text
<last>Nick</last></author><price>12</price>
History</book>of NaradocID pathID/book/title
SELECT e.docID, e.position
FROM Element e, Path p
WHERE e.pathID = p.pathID
AND p.pathname = “/book/title”

#1
#1
#1･
Pathpos

1
23･

1, 12520, 4950, 101･･･

pathname

pathID

1/book2/book/title/book/author 3…
･

7

問合せ変換例(3)

問合せ変換例(2) ~あいまい経路式~~制約条件付きのあいまい経路式~//author[first=‘Joe’]Element
docID pathID//last

#1
#1.
#1

12.
5

pos
1, 12520, 49...
76, 92

SELECT e.docID, e.position
PathFROM Element e, Path pWHERE e.pathID = p.pathID
pathnamepathID
AND p.pathname like “%/last” /book
12/book/title…
･/book/author/last 5
文字列照合を行う述語

SELECT e.docID, e.position
FROM Element e, Text t,

Path p1, Path p2
WHERE p1.pathname

like “%/author”
p2.pathname
like “%/author/first”
AND t.value = “Joe”
AND t.pathID = p2.pathID
AND e.pathID = p1.pathID
AND e.docID = t.docID
AND e.pos.contain(t.pos)
ANDElement
docID pathID
pos#1
1
1, 125#1
220, 49#1
350, 101
TextdocID pathID value pos#14
Joe65, 67
Pathpathname

pathID/book/author/book/author/first34

Primary XML index (infosettab)
主キー

Microsoft SQL Server 2005

問合せの変換/BOOK[@ISBN = “1-55860-438-3”]/SECTION
引数のノードを根とする部分文書を返す

SELECT SerializeXML (N2.ID, N2.ORDPATH)
FROM infosettab N1
JOIN infosettab N2 ON (N1.ID = N2.ID)
WHERE N1.PATH_ID = PATH_ID(/BOOK/@ISBN)AND N1.VALUE = '1-55860-438-3'
AND N2.PATH_ID = PATH_ID(/BOOK/SECTION)
AND Parent (N1.ORDPATH) =Parent (N2.ORDPATH)
引数のORDPATHの親ノードのORDPATHを返す

引数の経路の経路IDを返す

8