修士論文 関係データベースを用いた XML 文書の 格納と検索手法 XRel

NAIST-IS-MT0151091
修士論文
関係データベースを用いた XML 文書の
格納と検索手法 XRel の実装とその評価
藤井 眞吾
2002 年 2 月 8 日
奈良先端科学技術大学院大学
情報科学研究科 情報システム学専攻
本論文は奈良先端科学技術大学院大学情報科学研究科に
修士 (工学) 授与の要件として提出した修士論文である．
藤井 眞吾
審査委員：
植村 俊亮 教授
松本 裕治 教授
吉川 正俊 助教授
関係データベースを用いた XML 文書の
格納と検索手法 XRel の実装とその評価∗
藤井 眞吾
内容梗概
XML はインターネット上で文書やデータを統一的に表現するためのメタ言
語である。 今後 XML で記述された文書が増大することが予想される。 そこ
で、 XML 文書をデータベースに効率良く格納・検索することが必要になる。
また関係データベースを用いることは、関係データベースが広く普及してい
ること、過去の研究成果が蓄積されて高度なものとなっていることから有利で
ある。
本論文では、まず関係データベースを用いた XML 文書の汎用的な格納およ
び検索手法である XRel を紹介する。 そして、 XRel の実装を行い、その例
として XML 文書にされたシェイクスピアの戯曲集の検索システム、マウス相
補鎖 DNA 機能注釈の検索システムを報告する。 さらに XML データベース
の性能評価手法である Xmark についても紹介し 、 Xmark を用いて XRel の
性能評価も行う。
これにより、 XRel の XML データベースとしての応用範囲の広さ、 XML
データベースとしての高性能性が確認された。
キーワード
XRel, XML データベース, 関係データベース, 性能評価, Xmark
∗
奈良先端科学技術大学院大学 情報科学研究科 情報システム学専攻 修士論文, NAIST-IS-
MT0151091, 2002 年 2 月 8 日.
i
A Method to Store and Retrieve XML
Documents Using Relational Databases XRel:
Evaluation and Implementation∗
Huzii Singo
Abstract
XML is defined as a meta language to express documents and data uniformly.
Documents described with XML are expected to increase rapidly in the near
future.
And it is advantageous to use relational database management system (RDBMS)
to manage XML documents because RDBMS is a mature technology and has
been extensively studied.
In this paper, a method called XRel to store and retrieve XML documents
using relational databases is introduced. The author then investigate that how
Xmark, a method to benchmark XML databases, is applied to XRel. Moreover,
a retrieval system of the plays of Shakespeare collection and a retrieval system
of ‘functional annotation of mouse’ are described.
From our experimens, XRel is proved to be an efficient XML database to
store and retrieve XML documents.
Keywords:
XRel, XML database, relational database, benchmark, Xmark
∗
Master’s Thesis, Department of Information Systems, Graduate School of Information
Science, Nara Institute of Science and Technology, NAIST-IS-MT0151091, February 8,
2002.
ii
目次
第1章
導入
1
1.1 はじめに . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2 本研究の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
第2章
関連研究
4
. . . . . . . . . . . . . .
4
2.2 XML データベースへの問合せ . . . . . . . . . . . . . . . . . . .
5
2.3 XML データベースの性能評価 . . . . . . . . . . . . . . . . . . .
5
2.1 構造化文書のデータベースへの格納法
第3章
XML および関連技術の概要
6
3.1 XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.1.1
XML の概要 . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.1.2
XML 文書を表現する木構造 . . . . . . . . . . . . . . . .
8
3.2 XPath 1.0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
第4章
3.2.1
指示単位 . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.2
式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.3
省略記法 . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2.4
具体例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
XML データベースの写像技術
13
4.1 XML 文書のデータベーススキーマへの写像法 . . . . . . . . . . 13
4.1.1
構造写像による方法 . . . . . . . . . . . . . . . . . . . . 13
4.1.2
構成要素写像による方法 . . . . . . . . . . . . . . . . . . 14
4.1.3
二つの方法の比較 . . . . . . . . . . . . . . . . . . . . . . 14
iii
4.1.4
関係データベースを用いた構成要素写像による方法 . . . 15
4.2 XML 文書をそのまま格納する方法 . . . . . . . . . . . . . . . . 15
第5章
XRel
16
5.1 XRel の概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.2 XML 文書の格納 . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.2.1
基本 XRel 関係スキーマ . . . . . . . . . . . . . . . . . . 17
5.3 問合せ変換 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.3.1
問合せ変換の概観 . . . . . . . . . . . . . . . . . . . . . . 21
5.3.2
XPathCore 表現から XPathCore グラフへの変換 . . . . 24
5.3.3
XPathCore グラフから SQL 問合せへの変換 . . . . . . . 30
5.4 数字データ XRel . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.5 位置条件 XPathCore グラフ . . . . . . . . . . . . . . . . . . . . 38
. . . . . . . . . . 38
5.5.1
位置条件の出現場所による意味の違い
5.5.2
XPathCore グラフにおける述語の有効範囲 . . . . . . . . 42
5.6 文書名表付き XRel スキーマ . . . . . . . . . . . . . . . . . . . . 47
5.7 XQuery から XRel 問合せへの変換 . . . . . . . . . . . . . . . . 48
5.8 更新操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
第6章
XRel の実装と応用
50
6.1 XPath 式から SQL 問合せへの変換モジュール . . . . . . . . . . 50
6.1.1
雛型 QueryGraph . . . . . . . . . . . . . . . . . . . . . . 51
6.1.2
雛型 GenerateSQL . . . . . . . . . . . . . . . . . . . . . 54
6.1.3
例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
6.2 シェイクスピア戯曲の検索システム . . . . . . . . . . . . . . . . 55
6.2.1
使用した XML データ . . . . . . . . . . . . . . . . . . . 55
6.2.2
システムの構成部品 . . . . . . . . . . . . . . . . . . . . 56
6.2.3
システムの利用方法 . . . . . . . . . . . . . . . . . . . . 56
6.3 マウス相補鎖 DNA 機能注釈の検索システム . . . . . . . . . . . 59
6.3.1
使用した XML データ . . . . . . . . . . . . . . . . . . . 59
iv
6.3.2
システムの構成部品 . . . . . . . . . . . . . . . . . . . . 60
6.3.3
システムの利用法 . . . . . . . . . . . . . . . . . . . . . . 61
評価
63
第7章
7.1 XML データベースの性能評価技術 . . . . . . . . . . . . . . . . 63
7.2 Xmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
7.2.1
Xmark の概要 . . . . . . . . . . . . . . . . . . . . . . . . 65
7.2.2
XML 文書の生成 . . . . . . . . . . . . . . . . . . . . . . 66
7.2.3
XML データベースへの問合せ . . . . . . . . . . . . . . . 67
7.3 Xmark による XRel の性能評価 . . . . . . . . . . . . . . . . . . 68
7.3.1
XML 文書の格納 . . . . . . . . . . . . . . . . . . . . . . 68
7.3.2
XQuery 式の XRel 問合せ式への変換 . . . . . . . . . . . 68
7.4 性能評価実験 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
7.4.1
実験環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
7.4.2
比較対象 . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
7.4.3
実験と考察 . . . . . . . . . . . . . . . . . . . . . . . . . 70
第 8 章 まとめと今後の課題
81
8.1 まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
8.2 今後の課題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
8.2.1
XQuery 式から SQL 問合せへの変換手法の確立 . . . . . 82
8.2.2
XML 文書の更新 . . . . . . . . . . . . . . . . . . . . . . 82
謝辞
83
参考文献
87
付録
90
A
Xmark の XQuery 式 . . . . . . . . . . . . . . . . . . . . . . . . 90
B
A.1
標準 XRel による問合せ . . . . . . . . . . . . . . . . . . 90
A.2
数字データ XRel による問合せ . . . . . . . . . . . . . . 102
XQEngine の問合せに変形した Xmark の XQuery 式 . . . . . . 106
v
B.1
XPath 式による問合せ . . . . . . . . . . . . . . . . . . . 106
B.2
XQuery 式による問合せ . . . . . . . . . . . . . . . . . . 109
vi
図目次
3.1 XML 本体 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.2 XML 木構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
5.1 単純経路表現の記法 . . . . . . . . . . . . . . . . . . . . . . . . 17
5.2 XPathCore の記法 . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3 単純正規表現と単純絶対正規表現の記法 . . . . . . . . . . . . . 23
5.4 正規表現の記法 . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.5 問合せ (2) の XPathCore グラフ . . . . . . . . . . . . . . . . . 26
5.6 ArithExpr の XPathCore グラフ
. . . . . . . . . . . . . . . . . 27
5.7 2 つの ArithExpr を比較する XPathCore グラフ . . . . . . . . . 29
5.8 SQL 問合せを生成する手順 . . . . . . . . . . . . . . . . . . . . 30
5.9 順序節を処理する手順 . . . . . . . . . . . . . . . . . . . . . . . 31
5.10 XPathCore グラフから SQL 問合せを生成する手順 . . . . . . . 32
5.11 位置条件 XPathCore グラフ . . . . . . . . . . . . . . . . . . . . 40
5.12 位置条件 XPathCore グラフの例 1 . . . . . . . . . . . . . . . . 41
5.13 位置条件 XPathCore グラフの例 2 . . . . . . . . . . . . . . . . 41
5.14 XML 木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.15 位置条件 XPathCore グラフの例 1 . . . . . . . . . . . . . . . . 44
5.16 位置条件 XPathCore グラフ . . . . . . . . . . . . . . . . . . . . 45
5.17 位置条件 XPathCore グラフの例 2 . . . . . . . . . . . . . . . . 45
6.1 XPath2SQL モジュール . . . . . . . . . . . . . . . . . . . . . . 51
6.2 XPathCore グラフの例 . . . . . . . . . . . . . . . . . . . . . . . 55
vii
6.3 XPath 式入力画面 . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.4 SQL 式表示画面 . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.5 SQL 問合せ結果表示画面 . . . . . . . . . . . . . . . . . . . . . . 58
6.6 結果表示画面 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6.7 条件入力画面 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.8 問合せ結果表示画面 . . . . . . . . . . . . . . . . . . . . . . . . 62
6.9 注釈表示画面 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7.1 Xmark スキーマ
. . . . . . . . . . . . . . . . . . . . . . . . . . 66
7.2 指定する経路数の影響 . . . . . . . . . . . . . . . . . . . . . . . 78
viii
表目次
3.1 XPath の省略記法 . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.1 要素表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2 属性表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.3 文字列表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.4 経路表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.5 (1) 数字データ XRel の属性表 . . . . . . . . . . . . . . . . . . . 38
5.6 (1) 数字データ XRel の文字列表 . . . . . . . . . . . . . . . . . . 38
5.7 (2) 数字データ XRel の数字属性表 . . . . . . . . . . . . . . . . 39
5.8 (2) 数字データ XRel の数字文字列表 . . . . . . . . . . . . . . . 39
5.9 文書名表付き XRel の文書名表 . . . . . . . . . . . . . . . . . . 48
6.1 雛型 XPath2SQL . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.2 XPath 式の分解単位 . . . . . . . . . . . . . . . . . . . . . . . . 52
7.1 格納データの詳細 . . . . . . . . . . . . . . . . . . . . . . . . . . 68
7.2 実験に使用した環境 . . . . . . . . . . . . . . . . . . . . . . . . 69
7.3 XQEngine による Xmark 問合せの実行 . . . . . . . . . . . . . . 71
7.4 実験結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.5 問合せの分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7.6 文字列照合を有する問合せ . . . . . . . . . . . . . . . . . . . . . 74
7.7 順序節を有する問合せ . . . . . . . . . . . . . . . . . . . . . . . 74
7.8 COUNT による表示 . . . . . . . . . . . . . . . . . . . . . . . . 75
7.9 経路表現に「 // 」を有する問合せ . . . . . . . . . . . . . . . . . 76
ix
7.10 表示順序による実行時間の違い . . . . . . . . . . . . . . . . . . 77
x
第1章
1.1
導入
はじめに
本論文は、関係データベースを用いた XML (Extensible Markup Language;
拡張可能なマークアップ言語) 文書の格納および検索手法である XRel の実装
とその評価に関する研究である [1]。
XML は、構造化文書を記述するためのメタ言語であり、ネットワークを通
じて交換される文書やデータの共通形式として普及している。 今後 XML で
記述された文書の増大が予想されるため大量の XML 文書を効率的に管理・運
用できる XML データベースの研究・開発が急務である。
XML データベースの実現手法としては、関係データベース、対象指向 (object
oriented) データベースや XML 専用のデータベースを用いる方法等が提案さ
れているが 、中でも関係データベースを用いる方法は 、1) 最も普及している
データベースであり稼働中のシステムが多数存在する、2) 大量のデータが関
係データベース上に蓄積されている、3) 過去 20 数年に渡る研究による、問合
せ最適化や論理作業単位 (transaction) 管理等の技術の蓄積があることなどか
ら、 XML 文書を既存の計算機資源、情報資源と連携して利用するのに有利で
ある。
XML 文書のための問合せ言語としては XML-QL, XQL, XPath1 , XQuery2
などが提案されている。 これらは次のような特徴をもつ。
XML-QL 半構造データの研究成果を基に 、データに特化した操作を考慮に
1
XPath は正確には問合せ言語ではないが 、 XML 文書の部分を指定するものであり、問
合せ言語として扱うことができる。
2
<UR: http://www.ibiblio.org/xql/xql-proposal.html>
1
入れ 、 WHERE 句において部分文書の抽出を行い、 CONSTRUCT 句
でデータの再構成または変換を行う。
XQL 簡明な表記法により、特定の要素を指したり、文字列を含む要素を検索
する。
XPath XML 文書の特定の部分を指すための経路指定言語。 XQL に非常に
よく似ている。
XQuery XML 文書の階層構造から照会の対象となる部分を特定し 、その結
果を照会条件により検索し 、さらにその結果の構造を変換しなおして最
終結果を生成する。
一方従来のデータベース問合せ言語としては SQL が標準であり、 XML デー
タと従来のデータとの統合を考慮すると、 XML データベースは SQL 界面と
XML 問合せ言語界面の両方を備えることが望ましい。 したがって両方の問合
せ言語界面を持つデータベースシステム実現のために既存の SQL データベー
スシステムに XML 問合せ言語界面を追加する手法が考えられる。
このような手法を実現するために、前述の二つの界面からの問合せ最適化、
同時実行制御などをどの段階で統合するかについて、次のような可能性がある。
(1) XML 問合せ言語の問合せを SQL 問合せに変換し 、 SQL 問合せとして実
行する。
(2) XML 問合せ言語の問合せを SQL 問合せの中間表現に変換し 、実行する。
(3) XML 問合せ言語の問合せを解釈、最適化し 、 SQL 問合せの最適化器を介
さず、直接データベースシステムの物理ファイルの操作手段を利用する。
これらのうち、上の選択肢ほど 開発が容易であり、 SQL 界面を有するデー
タベースシステム上にも実現できるため、汎用性が高い。 一方、下の選択肢は
開発工数はかかるが 、高い性能を得られる可能性がある。 XML 問合せの最適
化については SQL 問合せ最適化と重複する部分もあること、また、汎用デー
タベースシステムの問合せ最適化技術は活用すべきであることなどから我々の
研究室で提案する XRel では (1) の手法を採用した。
2
本研究ではこのような考えのもと設計された XRel をシステムとして実装
し 、さらに XML データベースとしての性能を評価することを目的とする。
XRel の実装としては、 XPath 式から SQL 問合せへの変換モジュールと、
シェイクスピアの戯曲の検索システム、マウス相補鎖 DNA 機能注釈の検索シ
ステムを作成し 、 XRel の XML データベースとしての性能評価は Xmark を
用いて行う。
1.2
本研究の構成
本稿の構成は次のとおりである。 2 章は関連研究に関する章で、 XML デー
タベース技術について概観する。 3, 4 章は XML 技術に関する章であり、3 章
では XML そのものとその関連技術である XPath について解説する。 4 章で
は XML 文書をデータベースに写像する技術について概観する。 5 章では 本
研究で扱う XRel について、基本 XRel の紹介とそれを拡張した XRel に関し
て、また 6 章では、 XRel を用いて実装した XPath から SQL 問合せへの変換
モジュール、シェイクスピアの戯曲の検索システム、マウス相補鎖 DNA 機能
注釈の検索システムについて解説をする。 7 章は XML データベースの性能評
価に関する章であり、 XML データベースの性能評価技術について概観し 、そ
の技術の一つである Xmark を紹介し 、 Xmark を用いてどのように XRel を
評価したかについて述べ、最後に 8 章でまとめと今後の課題について述べる。
3
第2章
関連研究
XML 文書のデータベースによる管理手法に関する研究は、 SGML (Standard
Generalized Markup Language) [2, 3] あるいはそれ以前から存在する構造化文
書データベースに関する研究にその源流を見ることができ、既にいくつかの研
究が存在する [4, 5]。
ここでは XML データベースに関して、格納、問合せ、性能評価について関
連研究を紹介する。
2.1
構造化文書のデータベースへの格納法
構造化文書のデータベースへの格納法をデータベーススキーマ1 の観点から
考えると次のように分類できる。
(1) 文書の構造 (SGML, XML の文書型定義など ) ごとにデータベーススキー
マを設計する方法
(2) 文書の構造に依存しない固定化されたデータベーススキーマを設計する
方法
前者に関して、文献 [6, 7] では文書型定義を独自に拡張したデータベースス
キーマに写像し 、構造化文書を格納する方法を用いている。 この方法は文書
構造に関する問合せをデータベース言語で表現できるという利点がある反面、
格納された文書がもつ論理構造のわずかな変化がデータベーススキーマに影響
を及ぼすという問題点がある。
1
「 schema 」の日本語訳として「構造表現」を提唱したい。
4
後者の方法は XRel が採用した格納方法である。 この方法による研究とし
て、文献 [8] では、構造化文書 (順序木) を関係表に分割して格納することを提
案している。 また文献 [9] では、対象指向データベースで SGML 文書を管理
する手法として、すべての文字列節点を単一の雛型 (class) NODE で管理して
いる。 XRel が提案する方法は、木構造の各節点に対して、根節点からの経路
と位置情報を関係表で管理する点がこれらの既存の研究とは異なる。
2.2
XML データベースへの問合せ
文献 [10] では 、構造化文書を単なる文字列として扱い、木構造を操作する
演算を文字列操作に置き換え、この文字列操作を行う関数をもつ抽象データ型
をデータベースに用意する手法を採用している。 この手法を用いて、構造化
文書に対する問合せについて、 SQL を拡張した界面を用いて記述し 、実行処
理部が内部的に関係データベースに対する SQL と全文検索システムに対する
命令に振り分け、それらの結果を統合する。 利用者には、データベースの中
に文書が埋め込まれているように見える。 これに対して XRel では 、 XML
文書を分解して通常のデータベースの組として格納し 、専用の全文検索システ
ムや索引機構をもたないことや、 XML 問合せを SQL 式に変換して実行する
点、 XML 文書そのものはデータベースシステムに格納する点が異なる。 た
だし XRel は専用の全文検索システムや索引機構をもたない点で性能面では劣
るものと思われる。
2.3
XML データベースの性能評価
XML データベースの性能評価としては、文献 [11, 12, 13] がある。 詳しく
は 7.1 節で述べる。
5
第3章
XML および関連技術の
概要
3.1
XML
1996 年、 W3C (World Wide Consortium)1 が賛助する標準 SGML 編集委
員会 (Generic SGML Editorial Review Board) は XML (Extensible Markup
Language) というメタ言語を発表した。
XML は次のような目標をもとに設計された。
(1) XML はインターネット上でそのまま利用可能である
(2) XML は広く多様な応用を支援する
(3) XML は SGML と互換性を有する
(4) XML 文書を処理するプログラムを書くことは容易である
(5) XML における任意の機能の数はできるだけ小さく、理想的には 0 にとど
められるべきである
(6) XML 文書は人間が読み書きでき、明解であるべきである
(7) XML の設計は迅速に準備されるべきである
(8) XML の設計は形式的かつ簡潔である
(9) XML は作成しやすくあるべき
(10) XML によるしるし付けの簡潔さは最低限の重要性をもつべき
XML は SGML の後継として、主としてネットワーク上を流通する文書の
表現形式として開発されたが 、情報交換の形式として XML が有効であること
が明らかになるにつれて、それをデータベースに保存したいという要求が強く
1
<URL: http://www.w3.org/>
6
なってきた。
3.1.1
XML の概要
XML 文書は大きく分けると 、 XML 宣言、文書型定義 (Document Type
Definition; DTD) 、 XML 本体2 の三つの部分から構成される。 なお、 XML
宣言と文書型定義は XML 文書に必須ではない。 XML 宣言では XML の版
と符号化方式を指定する。 文書型定義はどのような XML 本体を許容するか
を表すスキーマ (schema) であり、文脈自由文法にほぼ相当する。 本論文では
XML 宣言と文書型定義の詳細は省略する。
XML 本体は要素の階層構造であり、要素は開始標識 (tag) と終了標識の対
によって区切られる。 開始標識と終了標識の間にある文字データが要素の内容
である。 題名 (title) が「 XML and Database 」、著者 (author) が「 NAIST 所
属 (affiliation) 、32 歳 (age) の Yamada Taro 」、
「 RAIST 所属、30 歳の Sugita
Ziro 」、要約 (summary) が「 XML stands for Extensible Markup Language 」
であるような本 (book) についての XML 本体の例を図 3.1 に示す。 開始標識
は < と > とで要素型を囲んだ文字列で、終了標識は < / と > とで要素型を
囲んだ文字列である。 開始標識と終了標識の対はいくらでも入れ子にするこ
とができ、この標識の入れ子が XML 本体を表現している。 また開始標識に
おいて、要素型と > の間には属性名と属性値を = でつなげたものをいくつか
記述することができる。
開始標識と終了標識の対応がとれており、親子関係にある要素の標識が正し
い入れ子になっているなど 、 XML で規定された標識付け規則にしたがってい
る XML 文書を整形式 (well-formed) の XML 文書という。 特に、文書型定義
と XML 本体の両方を持ち、 XML 本体が文書型定義に適合している文書を検
証済み (valid) XML 文書という。
本論文において対象とする XML 文書は XML 処理装置により整形式また
は検証済みであることが保証されているものとする。
2
XML 本体という用語は XML の仕様書には現れないが 、本論文では XML 宣言と文書型
定義を除く文書データという意味でこの用語を用いる。
7
<book>
<title>XML and Database</title>
<authors>
<author affiliation=“NAIST” age=“32”>Yamada Taro</author>
<author affiliation=“RAIST” age=“30”>Sugita Ziro</author>
</authors>
<summary>XML stands for Extensible Markup Language</summary>
<price>2000</price>
</book>
図 3.1 XML 本体
3.1.2
XML 文書を表現する木構造
XML 文書のための問合せ言語では通常 XML 文書を木で表現する。 本論
文でも XML 文書を標示付き (labeled) 順序木として扱う。 本論文で扱う木構
造の節点は次に示す根節点、要素節点、属性節点、文字列節点の四つの節点で
ある。
根節点 (Root Node) 木構造の根となる節点。
要素節点 (Element Node) 子の節点をいくつかもつことができ、子の節点と
なる型は三つ (要素、属性、文字列) のうちいずれか一つである。 標示
(label) は要素型を示す。
属性節点 (Attribute Node) 子の節点をもたない。 標示は属性名、属性値を
示す。 なお、複数の属性が存在するときには、属性間の順序は区別しな
い3 。
文字列節点 (Text Node) 子の節点をもたない。 標示は連続した XML で規
定された文字データを示す。
例として図 3.2 に、図 3.1 の XML 文書を表現する木構造を示す。
3
これは XML において属性の順序が問われないことによる。
8
1
Root
Element
Attribute
book
2
Text
16
price
17
2000
title
3
14
authors
5
4
XML stands for Extensible
Markup Language
XML and Database
author
6
affiliation
7
NAIST
summary
15
age
9
8
32
author
10
affiliation
11
Yamada Taro
age
12
RAIST
13
30
Sugita Ziro
図 3.2 XML 木構造
3.2
XPath 1.0
XPath (XML Path langage) 1.04 (以下、XPath という) は、XML 文書の特
定の部分を指し示すために考案された経路指定言語である。 XSLT や XPointer
などで共有されている機能について共通の文法と意味論を用意するための言語
であり、いわゆる問合せ言語ではない。 しかし 、その設計には XQL の成果が
取り入れられており、両者はよく似ている。 また XPath は W3C 勧告となっ
ているのでデータ形式、文法ともによく整備されており、完全な実装も多数存
在する。
XPath では 3.1.2 小節で示したように XML を木構造として形式化する。 節
には要素節、属性節、文字列節といった型がある。 XPath はそれぞれの型の
節についてその文字列値を計算する方法を定義する。
4
<URL: http://www.w3.org/TR/1999/PR-xpath-19991008>
9
3.2.1
指示単位
XPath 式は、 XPath のデータ形式上の目的の節を指し示すために零個以上
の指示単位 (step) と呼ばれる記法を使用する。 たとえば 、次の XPath 式
/child::book/child::authors/child::author[position()=2]/child::title
は次の四つの指示単位からなる。
(1) child::book
(2) child::authors
(3) child::author[position()=2]
(4) child::title
一つの指示単位は次の三つの指定項目からなる。
軸 (axis) 次の節を探す方向
節の種類 (node test) 節の型と節の名前
述語 (predicate) 条件による絞り込み
たとえば上記指示単位「 child::author[position()=2] 」を上の三つの指定項目
に分解すると次のようになる。
軸 子 (child)
節の種類 ”author” という名前をもつ要素
述語 author 要素として 2 番目
3.2.2
式
XPath において主たる文法構造は式である。 式とは生成規則 Expr に合致
するものである。 式は評価されて「節集合」、
「真偽値」、
「数値 (浮動小数点
「文字列」の４つの基本形のうち一つをとる。 式の評価は文脈との関
数) 」、
係で発生する。 文脈は次のものからなる。
10
(1) 一つの節 (文脈節)
(2) 一対の自然数 (文脈位置と文脈の大きさ)
(3) 変数束縛の集合
(4) 関数ライブラリ
(5) 式の有効範囲内にある名前空間宣言の集合
変数束縛は変数名から変数値への割り付け関係からなり、関数ライブラリは
関数名から関数への割り付け関係からなる。 また、これらのうち文脈節とい
う概念が重要である。 指示単位の軸は、文脈節に対しての相対位置を指示す
る。 軸で指定された位置にある節集合は節の種類によって型や名前が選別さ
れ、述語によってさらに絞り込まれる。
指示単位によって選択された節集合は、その各々の節を新たな文脈節として
続く指示単位を評価する。
3.2.3
省略記法
XPath には、軸を表す単語と節の種類の組合せに対して表 3.1 に示す省略記
法が用意されている。
表 3.1 XPath の省略記法
問合せ番号
状況
child::
(省略してなにも書かない)
attribute::
@
/descendant-or-self::node()/
//
self::node()
.
parent::node()
..
この記法により可読性のよい XPath 式を表記することができる。 たとえば
次の二つの XPath 式は等価である。
/child::book/child::authors/child::author[position()=2]/child::title
11
/book/authors/author[position()=2]/title
3.2.4
具体例
本論文においては XPath を省略記法を用いた表記について、具体的には 5.3
節で紹介する XPathCore の記法にしたがう XPath のみを考える。
図 3.2 で表される XML 木について考える。
「根節点の子である book 節点の子である title 節点」は次のような XPath
式により表される。
/book/title
また XPath では経路表現だけでなく述語によっても部分を指定できるので、
「著者が ’Yamada Taro’ である本の題名」は次のような XPath 式により表さ
れる。
/book[authors/author=’Yamada Taro’]/title
12
第4章
XML データベースの写像
技術
XML 文書を格納し 、検索、更新などの操作をするためのデータベースシステム
は、研究用、商用ともに開発が行われている。 XML 文書のデータベースへの
格納法は大きく分けて、 XML 文書を分解してデータベーススキーマ (Schema)
に写像する方法と XML 文書をそのまま格納する方法の二通りに分けることが
できる。
4.1
XML 文書のデータベーススキーマへの写像法
XML 文書を分解し 、データベーススキーマに写像する方法としては、構造
写像による方法、構成要素写像による方法の二つの方法が考えられる。
4.1.1
構造写像による方法
データベーススキーマは、 XML 文書の論理構造 (あるいは文書型定義が存
在する場合は文書型定義) を表現する。 初期の研究では 、対象指向 (Object
Oriented) データベースが木構造や参照関係を自然に表現できることを利用し 、
基本的に各要素型に対して雛型 (class) を定義することにより、 SGML 文書
を対象指向データベースで管理する手法が提案された。 より洗練された手法
としては、文書型定義をグラフ1 で表現し 、子要素の数などに応じて適当な部
分グラフごとに関係スキーマを生成するものも提案されている。
1
「 graph 」の日本語訳として「線図」を提唱したい。
13
構造写像による方法では、文書型定義が存在する場合は文書型定義ごとに、
そうでない場合は XML 文書ごとにデータベースが定義される。
4.1.2
構成要素写像による方法
データベーススキーマは XML データの構成要素を表現する。 この方法で
は、任意の XML 文書の木構造を格納するために固定したデータベーススキー
マを用いる。 この方法の初期のものとしては、 SGML 文書を対象指向データ
ベースに格納するために、すべての文字列節点を NODE という雛型で管理す
る手法 [14] がある。
4.1.3
二つの方法の比較
4.1.1 小節、4.1.2 小節の二つの方法を比較すると次のようになる。
(1) XML データには関係データベースや対象指向データベースでは表現でき
ない構成要素 (例えば 、要素間の順序など ) がある。 このことは、これら
の構成要素をそのまま自然にデータベーススキーマに写像するような構
造写像による方法は存在しないことを意味する。 問題の解決のためには、
データベースの表現能力の拡張が必要となる。 したがって、通常のデー
タベース管理システムは利用できない。
(2) 少数の文書型定義または文書構造にしたが う大量の XML 文書の管理が
必要で、またこのような文書型定義または文書構造が安定している場合に
は、構造写像による方法は適している。 逆に文書型定義が不明であるよ
うな整形式 XML 文書や文書型定義が頻繁に更新されるような XML 文
書の格納のためには構成要素写像による方法が適している。
これらより、既存のデータベース管理システムを用いた汎用性の高い XML
データベースシステムを実現するには構成要素写像による方法を用いることが
よいと思われる。
14
4.1.4
関係データベースを用いた構成要素写像による方法
この方法の目的を抽象化すると、任意の順序木を格納する固定した関係デー
タベーススキーマを開発することとなる。 文献 [15, 16] では、この方法に対
していくつかの手法を提案し 、比較している。 これらの手法は、木構造の節
点に識別子が付与されていることを仮定している点で制約がある。 文献 [17]
では 、木構造の根節点から各節点までの経路を基本単位とし 、経路自身を文
字列として関係表に格納し 、経路と領域によって木構造情報を表現する方法
である XRel を提案している。 関係表は 、経路に識別子を与える Path の他
に、 XML 文書の木構造の節点の種類 (要素、属性、文字列) ごとにそれぞれ
Element, Attribute, Text がある。 また、使用する関係データベースにも特に
条件が設けられていない。
4.2
XML 文書をそのまま格納する方法
XML を格納するデータベースとして関係データベースや対象指向データ
ベースを使用すると両者のデータベース仕様の差を吸収しなければならない。
そのためには計算量が増大したり、格納できる XML の構造に制限がつくの
で、 XML のデータ仕様をもとにして新しいデータベースを構築することが考
えられる。
XML 文書をそのまま格納する方法を採用するデータベースは 、直接解釈
XML データベース (Native XML Database) と呼ばれることもある。 関係デー
タベースシステムの場合は、基本的に大型文字列 (Character Large Object) と
して格納されることが多い。 例えば Oracle 9i では、論理的には新たに XML
型が導入されている。 XML 型は大型文字列データをもとに定義されており、
操作関数 (Method) を用いて検索を行う。
15
第5章
XRel
本章では、XML 文書の汎用的な格納および検索手法である XRel について述
べる。 まず、5.1–5.3 節では文献 [17] で紹介された XRel 技術について述べ
る。 次に 5.4, 5.5, 5.6 節では、それぞれ本論文で提案する数字データ XRel 、
位置情報 Query グラフ、文書名付き XRel についてのべる。 さらに 5.7 節で
は XQuery から XRel 問合せへの変換について、5.8 節では XML 文書の更新
による XRel への影響について述べる。
5.1
XRel の概要
XRel は関係データベースを用いた XML 文書の汎用的な格納と検索の手法
である。 格納については、 XML 文書を構文解析して得られる木構造を節点
単位で分割し 、節点の型に応じてデータベースの関係表に格納する。 この手
法を用いると、 XML 文書の文書型定義や要素型に依存することなく、あらゆ
る XML 文書を格納し 、データベース管理システムで提供されている B+ 木、
R 木などの索引機構を利用することができる。 検索については、現在いくつ
か提案されている XML のための問合せ言語の一つを利用して、多くの XML
文書から所望の検索結果を得るための枠組について示す。 提案される格納手
法は関係データベースを拡張することなく実現でき、また検索手法については
問合せ言語の前処理器を付加することで実現できる。
16
XML 文書の格納
5.2
この節では XRel による XML 文書格納のためのデータベーススキーマにつ
いて述べる。 基本 XRel スキーマは SQL-92 データ型に基づいている。
5.2.1
基本 XRel 関係スキーマ
経路表現はしばしば XML 問合せに表れるので 、 XML 木の分解単位とし
て経路を用いる。 XML データ木における根節点を除くそれぞれの節点につい
て、根節点からその節点に至る経路の情報を格納する。
根節点から要素 (もしくは属性) 節点にいたる経路を「単純経路表現」と呼
ぶ。 単純経路表現 (SimplePathExpr) の構文規則を図 5.1 に示す。 また文字列
節点の単純経路表現はその親の要素節点の単純経路表現と同じである。 単純
経路表現では、指示の区切り記号として XPath 表現で用いられる「 / 」の代わ
りに「 #/ 」を用いることに注意されたい。 その理由は 5.3.1 小節で説明する。
図 5.1 単純経路表現の記法
XML 文書中の各節点を単純経路表現で表現しようとすると、一つ以上の節
点が同じ単純経路表現で共有されることになり、単純経路表現における節点間
の順序関係が失われてしまう。 このため単純経路表現は XML 木の構造を復
元するのに十分ではない。 そこで、節点間の先行および 先祖・子孫関係を保
持するために、以下のように節点の領域 (region) を定義する。
定義１ ( 節点の領域 ) 要素または文字列節点の領域は、節点の XML 文書に
おける始めと終わりの位置 (何バイト目か ) を表す数字の対である。 属
17
性節点の領域は親要素節点の始めの位置に 1 を足した同一の数字の対で
ある。
属性節点の領域の定義をこのようにした理由は次の二つである。 (i) 同じ親
要素節点を持つ属性節点について順序は関係ない。 (ii) 要素節点が属性節点の
親のかど うかは、それらの節点領域の一つ目の数字の「 ≤ 」ではなく「 < 」に
よる比較をすることで判定できるという技術的な理由による。 XRel における
格納のスキーマの重要な考え方は、単純経路表現と XML 木における節点の領
域の組合せを関係表として保持していることであり、これにより XML 木の位
相情報を保持している。
例えば 、図 3.2 におけるいくつかの節点の単純経路表現と領域は次のように
表される。
node 7
#/book#/authors#/author#/@affiliation
(57, 57)
node 14
#/book#/summary
(190, 248)
基本 XRel のスキーマでは、それぞれの節点形式に対して一つの関係スキー
マ (schema) を与える。 関係表には単純経路表現、領域や文字列値などの付加
的な情報の組を格納する。 異なる XML 文書を同じ 関係表に格納するために
文書識別子も組にして格納される。 このようにして根節点を除く三種類の節
点 (要素 : Element 、属性 : Attribute 、文字列 : Text) に対して三つの関係ス
キーマを作成する。
同じ文書型定義にしたがう複数の XML 文書を単一のデータベースに格納す
る場合や似た構造を持つ XML 文書を格納するとき、同じ単純経路表現は何回
も関係表に表れる。 格納空間を節約するために、三つの関係表の単純経路表
現を経路識別子に置き換え、経路識別子と単純経路表現の対を格納する第四の
関係表を作成する。
したがって、基本 XRel スキーマは次の四つの関係スキーマからなる。
Element (docID, pathID, start, end, index, reindex)
Attribute (docID, pathID, start, end, value)
Text (docID, pathID, start, end, value)
Path (pathID, pathexp)
18
データベース属性 docID, pathID, start, end, value はそれぞれ文書識
別子、経路識別子、領域の開始位置、領域の終了位置、文字列値を表す。 要
素節点であるか文字列節点であるかはその領域により一意に特定できるので、
データベース属性 docID, start, end は関係要素 (Element) 、関係文字列 (Text)
のキーになる。 共通の親要素節点を持つ各々の属性節点を特定するには 、属
性名が必要となる。 属性節点の単純経路表現の接尾辞が属性名であるから 、
データベース属性 docID, start, end, pathID が関係属性 (Attribute) の
キーとなる。 関係要素におけるデータベース属性 index, reindex は要素節
点の出現順を表し 、それぞれ兄弟要素節点の文書中での順、逆順である。 実
際、 index, reindex 値は元の XML 文書を再構築するのに不可欠ではない
が 、これらの値は XML 問合せを効率的に処理するのに有用である。 関係経
路 (Path) におけるデータベース属性 pathexp は単純経路表現を格納する。
図 3.1 の XML 文書を格納した、基本 XRel スキーマのデータベースの例を
表 5.1–5.4 に示す。
表 5.1 要素表
docID
pathID
start
end
index
reindex
1
1
1
1
1
1
1
1
2
3
4
4
7
8
0
9
43
56
117
190
252
279
39
186
112
173
248
270
1
1
1
1
2
1
1
1
1
1
2
1
1
1
表 5.2 属性表
docID
pathID
start
end
value
1
1
1
1
5
6
5
6
57
57
118
118
57
57
118
118
NAIST
32
RAIST
30
19
表 5.3 文字列表
docID
pathID
start
end
value
1
1
1
1
1
2
4
4
7
8
16
93
154
199
259
31
103
164
238
262
XML and Database
Yamada Taro
Sugita Ziro
XML stands for ...
2000
表 5.4 経路表
pathID
pathexp
1
2
3
4
5
6
7
8
#/book
#/book#/title
#/book#/authors
#/book#/authors#/author
#/book#/authors#@affiliation
#/book#/authors#@age
#/book#/summary
#/book#/price
基本 XRel スキーマの特徴は次の通りである。
(1) XML 木の位相は単純経路表現と領域の組により表される
(2) それぞれの節点の型に対して関係が作成される
(3) データベースの大きさを小さくするために、単純経路表現は別の関係に格
納される
文献 [17] では上記基本 XRel の他に XRel の変形として、それぞれの節点の
親節点情報を保持するもの、領域情報を文書の先頭からのバイト数以外の情報
により表すもの、 TEXT 型を利用するもの、領域情報として領域型を定義する
ものを紹介している。
20
5.3
問合せ変換
XRel システムにおいては、関係スキーマは利用者から見えない。 利用者は
例えば図 3.2 のような XML 木により表された XML 文書を見て、その XML
木に対して XML 問合せを行う。 そしてシステムが XML 問合せを SQL 問合
せに変換する。 本節ではこの問合せ変換について述べる。
XML における重要な問合せ構造は経路表現であり、 XPath は経路表現に
より XML 文書の部分を指し示す言語である。 XPath 自身は問合せ言語では
ないが 、その記法と意味論は提案されている多くの問合せ言語で使用されてい
る。 そこで XRel における XML 問合せ言語として XPath の核となる部分を
XPathCore1 と名付け、 XPathCore 表現から SQL 問合せへの変換に焦点を
当てる。 XPathCore の記法を図 5.2 に示す。
5.3.1
問合せ変換の概観
5.2.1 小節で紹介した関係スキーマを用いて格納した XML 文書に対する
XML 問合せから SQL 問合せへの変換処理について述べるにあたり、まずは
次の XPathCore 表現を考える。
(1) /issue//family
XML 木で与えられた節点 n に対して、 XPath 1.0 の「 // 」は節点 n とそ
のすべての子孫の節を選択する。 ゆえに (1) はあらゆる issue 節の子孫である
すべての family 要素節を選択する。 SQL の文字列照合を用いることで XRel
データベースにおける family 要素節を容易に見つけられることは重要であ
る。 より一般的な表現を与えるために、 XPathCore における正規表現 (図 5.2
の RegularExpr) の一部を表す二つの表現である単純正規表現 (図 5.3 の Sim-
pleRegularExpr) と単純絶対正規表現 (図 5.3 の SimpleAbsoluteRegularExpr)
1
XPath 表現は基本的に XPath 1.0 の非終端記号 PathExpr と Quilt の非終端記号
PathExpr の共通部分である。 XPathCore の記法は Quilt の非終端記号 PathExpr の簡
略記法の形式による。 本論文では XPathCore の問合せが PathExpr の形式で与えられるこ
とを前提とする。 XPathCore の意味論は XPath 1.0 にしたがう。
21
図 5.2 XPathCore の記法
を定義する。
XRel データベースにおいて、根節からすべての節への単純経路表現が格納
される (図 5.1 で与えられる単純経路表現の記法を参照) 。 単純絶対正規表現と
単純経路表現の唯一の違いは、前者が指示の区切り記号を「 / 」と「 // 」として
いるのに対し 、後者は「 #/ 」としていることである。 単純絶対正規表現 s 中の
「 // 」を「 #%/ 」に置き換え、関係「経路」における pathexp
「 / 」を「 #/ 」に、
属性について、置き換えた後の文字列を用いた SQL 文字列照合を行うことで
節が単純絶対正規表現 s を満たすことが分かる。したがって XPathCore 表現
(1) は次の SQL 問合せに変換される。
SELECT
FROM
WHERE
AND
e1.docID, e1.start, e1.end
Element e1, Path p1
p1.pathexp LIKE ’#/issue#%/family’
e1.pathID = p1.pathID
22
図 5.3 単純正規表現と単純絶対正規表現の記法
ORDER BY e1.docID, e1.start, e1.end
関係「経路」に格納される単純経路表現の区切り記号としてなぜ「 / 」の代
わりに「 #/ 」を用いたかを説明する。もし /issue/family という形式で経路表
現を格納するならば 、問合せ (1) を上記の SQL 問合せに変換するには、３行
目を次の WHERE 節条件文に置き換えることになる。
WHERE
p1.pathexp LIKE ’/issue%/family’
この SQL 問合せは誤った答えを返す、というのも文字列パターン「 /issue%/family 」
「 /issues/family」、
「 /issuelist/family」
は経路表現「 /issue/family 」だけでなく、
といった他の経路表現にも一致するからである。
次に、下記のようなより複雑な XPathCore 表現について考えてみる。
(2) /article[summary/keyword = ’XML’]//author/family
この問合せは、要約が「 XML 」というキーワード を含んだ記事の著者の苗字
を検索する。 この問合せを SQL 問合せに変換するために、問合せ中における
経路表現の失われた接頭語を補う必要がある。 例えば 、 XRel データベースを
用いた問合せにおいて summary/keyword = ’XML’ という比較を処理するた
めに、 //article/summary/keyword という単純絶対正規表現を満たす単純経路
表現を持った要素節が存在するかを確認する必要がある。 同様に、 SQL の文
字列パターン #%/article#%/author#/family に変換される単純絶対正規表現
//article//author/family を得るために、経路表現 //article と //author/family
を結びつける必要がある。 この例により、一般に 、単純正規表現は問合せに
現われることが示唆される。 また、 XRel データベースの関係「経路」にお
23
いて、単純経路表現が格納されているために、長い単純絶対正規表現は述語に
より小部分に分割されるかもしれない。 ゆえに XPathCore による経路表現の
一般的な形式を処理するために、与えられた問合せを小部分経路に「切断し 」、
単純絶対正規表現の完全な形式に「繋ぎ 合わせる」必要がある。 我々はこの
「切断、繋合せ」処理の明確な表現及び手引きを与えるために XPathCore グ
ラフを導入する。
XPathCore 表現から SQL 問合せへの変換は次の二つの手順により行われる。
(1) 第１の手順では、 XPathCore グラフが XPathCore 表現の中間表現とし
て生成される。 XPathCore 表現が単純 (絶対) 正規表現に分割される。こ
の処理において、述語、グループ分け、比較演算子は句読点の役割を果た
す。 XPathCore における節と枝はそれぞれ経路表現と関係を表す。
(2) 第２の手順では SQL 問合せが XPathCore グラフから生成される。 SQL
節は XPathCore グラフの節と枝ごとに生成される。
これらの二手順についてそれぞれ 5.3.2 小節、5.3.3 小節で詳細な説明をする。
5.3.2
XPathCore 表現から XPathCore グラフへの変換
標準 XPathCore グラフ
5.3.1 節における議論から、まず、与えられた問合せにおける最も長い単純正
規表現と単純絶対正規表現とを発見しなければならない。そのために、 XPath-
Core 表現の補助的な構文規則を紹介する。 RegularExpr の構文規則は図 5.4
に見られるように書き直すことができる。 この図において、
「 + 」は「１また
はそれ以上」を表すメタ記号である。この図 5.4 の構文規則より、一般的に 、
次の手順で RegularExpr を表すことができる。
S0 {P1 } + A1 {P2 } + · · · {Pn−1 } + An−1 {Pn }∗
ここで n ≥ 0 である。また、 S0 , Ai (i = 0, · · · , n − 1), Pj (j = 1, · · · , n) は
それぞれ図 5.2 における非終端記号 SimpleRegularExpr, SimpleAbsoluteReg-
24
ularExpr, Predicate の言語を表す。
「 {}+ 」と「 {}∗ 」はメタ記号であり、それ
ぞれ「１回以上の出現」と「０回以上の出現」を表す。
図 5.4 正規表現の記法
例１ 問合せ (2) は、 A0 を //article 、 P1 を [summary/keyword = ’XML’] 、
A1 を //author/family とすると A0 , P1 , A1 の連続と見ることができる。
与えられた問合せにおける単純正規表現、単純絶対正規表現と述語の間の関
係を明確にするために、我々は XPathCore グラフと呼ばれるグラフを導入す
る。 XPathCore グラフの形式的な定義は次のようになる。
定義２ ( XPathCore グラフ ) XPathCore グラフは以下の制約を満たす有向グ
ラフ G(N, E) である。
(1) すべての節は次の７つの非終端記号のうちの一つの節型を持っている。
BasicExpr, Predicate, SimpleRegularExpr, SimpleAbsoluteRegularExpr,
Literal, Number, Boolean
(2) Boolean 型以外のすべての節は値を持っている。節型 T とすると、節の
値は T の言語である。
(3) N は互いに素な２つの節、順序節 ( ordinal nodes ) と索引節 (index nodes
) の集合の結合である。順序節は実線円で、索引節は破線円で表される。
(4) N には G の出力節と呼ばれる唯一の節がある。出力節は影付円で表さ
れる。
(5) E は互いに素な２つの枝、 Et ( 枝 (tree edges ) ) と Ec ( 比較枝 (comparison edges ) ) の集合の結合である。枝は実線で表され 、比較枝は破線
で表される。
(6) グラフ (N, Et ) は根を持った木である。 (N, Et ) には、節の子が順序づけ
られている。親 n からその i 番目の子 m への枝は (n, i, m) と示される。
25
(7) 比較枝は標示として CompareOp を有している。標示 θ を有した n から
m への比較枝は (n, θ, m) と示される。
例えば 、問合せ (2) の XPathCore グラフは図 5.5 のようになる。この図に
おいて、節の値は、 Boolean 節である n2 を除いて、それぞれの節の外側の近
くに表示されている。
//article
n1
1
2
n2
1
n5
//author/family
2
=
n3
n4
Summary/keyword
‘XML’
図 5.5 問合せ (2) の XPathCore グラフ
XPathCore 表現を与える XPathCore グラフを産み出すための主要な手順
である「 生成 QG ( GenerateQG ) 」について説明する。 図 5.2 の構文規則
から 、非終端記号 PathExpr と Comparison は相互に再帰的な方法で定義さ
れていることが分かる。 簡単のため、手順「生成 QG 」は Comparison の言
語を一入力として設計する。 Comparison は主要な構成要素であり、非終端
記号 ArithExpr を有しているから、与えられた言語 ArithExpr に対して初期
XPathCore グラフを返す手順である「生成初期 QG ( CreateInitialQG ) 」を
26
まず与える。 言語 ArithExpr は次のように表される。
A0 {P0 } + A1 {P1 } + · · · {Pn−2 } + An−1 {Pn−1 }∗
手順「生成初期 QG 」は CreateQG(E) と表され 、入力を ArithExpr E とし
て、出力を図 5.6 のような XPathCore グラフ G とする。順序節と索引節の２
種類の P 節があることに留意されたい。
A0
k0+1
1
2
k0
A1
P00
P01
… P02
1
P10
2
P11
k1
.
.
.
… P1k
1
An-1
1
P(n-1)0
2
kn-1
P(n-1)1 … P(n-1)kn-1
図 5.6 ArithExpr の XPathCore グラフ
手順「生成 QG 」は GenerateQG(C) と表され 、具体的には次のようになる。
手順 GenerateQG(C)
Input : Comparison C
Output : An XPathCore Graph G
Algorithm :
27
(1) もし C が ArithExpr E なら :
(i) G := CreateInitialQG(E)
(ii) もし G 中に P 節があれば次の処理をする:
/∗ P は出力節ではないことに注意 ∗/
C を Comparison として P = [C ] とする
P の内部枝の先を GenerateQG(C ) に変えて P を削除する
より正確には、次の通りの処理をする
(a) G := GenerateQG(C )
(b) もし P が G 中の索引節であれば 、 G の根節を索引節とする
(c) G を次のように代える
(I) P の内部枝の先を G の根節に代える
(II) P を削除する
(III) G の出力節は代わらない (G の出力節は無視する)
(iii) G を返す
(2) もし C の形式が E1 CompareOp E2 なら (E1 , E2 は ArithExpr):
次の XPathCore グラフ G を生成し 、 G を返す (図 5.7 参照)
(i) G の根節は新しく生成された Boolean 節 nb
(ii) G1 を GenerateQG(E1 ) 、G2 を GenerateQG(E2 ) とし 、次のような枝
を生成する:
(a) nb から G1 の根節への (順序標示が 1 の) 枝
(b) nb から G2 の根節への (順序標示が 2 の) 枝
(iii) G1 の出力節を O1 、 G2 の出力節を O2 とし 、 O1 から O2 への標示が
CompareOp の枝を生成する
(iv) G の出力節を nb とする
この手順はまず図 5.6 における XPathCore グラフか図 5.7 における XPath-
Core グラフを生成する。 手順はさらに再帰的に BasicExpr と Predicate の
s 出現を XPathCore グラフに置き換えて、最後に 、次の５つの節型を含んだ
XPathCore グラフを生成する。
(1) SimpleRegularExpr, (2) SimpleAbsoluteRegularExpr, (3) Literal, (4)
Number, (5) Boolean
手順「生成 QG 」により XPathCore グラフを生成した後、我々は XPathCore
グラフについて経路連結を行う。この過程では我々は、完全経路表現を得るた
めに、単純正規表現節と単純絶対正規表現節の値を XPathCore グラフの根節
28
から枝に沿って連結する。
nb
1
2
GenerateQG(E1)
GenerateQG(E2)
CompareOp
O1
O2
図 5.7 2 つの ArithExpr を比較する XPathCore グラフ
定義３ n を XPathCore グラフ G における単純正規表現節または単純絶対正
規表現節とする。( G における ) n の連結された値は次のように再帰的
に定義される。
(1) もし n が単純正規表現または単純絶対正規表現節の先祖を有していない
ならば 、 n の値は n の連結された値である。
(2) その他の場合、 na を単純正規表現又は単純絶対正規表現節の最も近い先
祖とする。 n の連結された値は次の二つに分類される。
(i) na の連結された値、
「 / 」、 n の値の連結 ( もし n が単純正規表現型の
とき )
(ii) na の連結された値、 n の値の連結 ( もし n が単純絶対正規表現型の
場合 )
29
例２ 図 5.5 における n1 , n3 , n5 節の連結された値は、それぞれ //article, //ar-
ticle/summary/keyword, //article//author/family である。
5.3.3
XPathCore グラフから SQL 問合せへの変換
この節では XPathCore グラフから SQL 問合せを生成する手法を紹介する。
図 5.8 に SQL 問合せ生成の主要な手順を示す。
図 5.8 SQL 問合せを生成する手順
XPathCore グラフから SQL 問合せを生成するための手順は、 XPathCore
グラフが１つ以上の Number 型の順序節を含んでいるときには複雑になる。な
ぜなら、索引節と違い、我々は SQL 問合せを生成するために関係属性 Index
を使用することができないからである。 代わりに 、 SQL の EXIST と NOT
EXIST 節を使う必要がある。 図 5.8 に示すように、(1) では図 5.10 に示す手
順「生成単純 SQL ( GenerateSimpleSQL ) 」を呼ぶ。 生成単純 SQL 手順は
Number 型の順序節を無視して、 XPathCore グラフの残りに対する SQL 問
い合わせを生成する。 手順「 生成 SQL ( GenerateSQL ) 」は 、 XPathCore
グラフにおける Number 型の順序節についての必要な SQL 条件を加えるため
に図 5.9 に示す手順「順序節処理 ( ProcessOrdinalNodes ) 」を呼ぶ。
手順「生成単純 SQL 」において、我々は節が SimpleRegularExpr か Sim-
pleAbsoluteRegularExpr 型である場合のみ、節を Expr 型と呼んでいる。 5.3.1
小節の問合せ (1) によって証明したように、経路表現における「 / 」 ( または
「 // 」 ) の出現は「 #/ 」 ( または「 #%/ 」 ) に置き換えられ、 SQL 文字列一致
のパターンとして用いられる。置換えを形式的に表現するために、関数 f% を導
30
図 5.9 順序節を処理する手順
31
図 5.10 XPathCore グラフから SQL 問合せを生成する手順
32
入する。与えられた SimpleRegularExpr または SimpleAbsoluteRegularExpr
の値を p とすると、 f% (p) は、 (i) p におけるすべての「 / 」を「 #/ 」に、 (ii)
p におけるすべての「 // 」を「 #%/ 」に置き換えることにより得られる文字列
を返す。
例３ 5.3.1 小節で述べた XPathCore 問合せ (2) は次の SQL 問合せに変換さ
れる。
SELECT
FROM
e5.docID, e5.start, e5.end
Path p1, Element e1, Path p3, Text t3,
Path p5, Element e5
WHERE
p1.pathexp LIKE ’#%/article’
AND
p3.pathexp LIKE ’#%/article#/summary#/keyword’
AND
p5.pathexp LIKE ’#%/article#%/author#/family’
AND
e1.pathID = p1.pathID
AND
e5.pathID = p5.pathID
AND
t3.pathID = p3.pathID
AND
e1.start < t3.start
AND
e1.end > t3.end
AND
e1.docID = t3.docID
AND
e1.start < e5.start
AND
e1.end > e5.end
AND
e1.docID = e5.docID
AND
t3.value = ’XML’
ORDER BY e5.docID, e5.start, e5.end
次に要素の順序が指定された XPathCore 表現の２つの例に戻る。次に示す
XPathCore 表現は author 要素の２番目の子となる family 要素を検索する。
//author/family[2]
XPathCore グラフにおいて、 Number 型の索引節が作られる。そして、次
の SQL 問合せが生成される。この SQL 問合せにおいて、関係属性 index に
ついての条件は要素の出現順序を処理するために指定される。
33
SELECT
FROM
WHERE
AND
AND
ORDER BY
e1.docID, e1.start, e1.end
Path p1, Element e1
p1.pathexp LIKE ’#%/author#/family’
e1.pathID = p1.pathID
e1.index = 2
e1.docID, e1.start, e1.end;
次の XPathCore 表現は前の表現とよく似た構文であるが 、異なる意味で
ある。
(//author/family)[2]
この XPathCore 表現は次のことを意味する。
(1) author 要素の子であり、
(2) 条件 (1) を満たす要素のうち文書の順序で２番目となる
family 要素を検索する。
この XPathCore グラフにおいて、 Number 型の順序節が作られる。 この場
合は次のように、変換された SQL 問合せにおいて EXISTS と NOT EXISTS
節を使う必要がある。
SELECT
e1.docID, e1.start, e1.end
FROM
Path p1, Element e1
WHERE
p1.pathexp LIKE ’#%/author#/family’
AND
e1.pathID = p1.pathID
AND EXISTS (
SELECT *
FROM
Path p11, Element e11
WHERE p11.pathexp LIKE ’#%/author#/family’
AND
e11.pathID = p11.pathID
AND
e11.docID = e1.docID
AND
e11.start < e1.start
)
AND NOT EXISTS (
SELECT *
FROM
Path p11, Element e11,
34
WHERE
AND
AND
AND
AND
AND
AND
AND
)
ORDER BY
5.4
Path p12, Element e12
p11.pathexp LIKE ’#%/author#/family’
p12.pathexp LIKE ’#%/author#/family’
e11.pathID = p11.pathID
e12.pathID = p12.pathID
e11.docID = e1.docID
e12.docID = e1.docID
e11.start < e12.start
e12.start < e1.start
e1.docID, e1.start, e1.end;
数字データ XRel
基本 XRel では以下に示すように、数字データを用いた問合せを処理できな
い場合があることが分かった。 そこで本節では数字データを用いた問合せが
可能な数字データ XRel を提案する。
XML 文書の文字列として数字データと数字以外の文字列データを有したも
のがある2 。 このような XML 文書について 、 XML 文書中の数字データに
対して算術演算を行うような SQL 式で問合せを行うと、データベースの SQL
最適化機構により意図しない順序で SQL 式が実行されるため、文字列データ
に対し算術演算を行おうとし 、妥当でない数字である旨で実行不可となること
がある3 。
例えば 、
「最後の増加 (increase) が最初の増加の 2 倍以上であるような開催
中の競売について、最初と最後の増加を返す」ということを意味する、次のよ
うな XQuery 式を考える。
FOR $b IN document ("auction.xml")/site/open_auctions/open_auction
WHERE $b/bidder[1]/increase/text() * 2 <=
$b/bidder[last()]/increase/text()
RETURN <increase first=$b/bidder[1]/increase/text()
2
例えば 7.2 節で紹介する Xmark における XML 文書。
3
Oracle9i では 「 ORA-01722: invalid number 」との表示がなされる。
35
last=$b/bidder[last()]/increase/text() />
上記 XQuery 式は XRel では次のような SQL 式に変換される。
SELECT ’<increase first="’||t2.value||’" last="’||t4.value||’" />’
FROM element e0, pth p0, element e1, pth p1, txt t2, pth p2,
element e3, pth p3, txt t4, pth p4
WHERE p0.pathexp LIKE ’#/site#/open_auctions#/open_auction’
AND e0.pathid = p0.pathid
AND p1.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder’
AND e1.pathid = p1.pathid
AND e1.idx = 1
AND e0.st < e1.st
AND e0.ed > e1.ed
AND p2.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder#/increase’
AND t2.pathid = p2.pathid
AND e1.st < t2.st
AND e1.ed > t2.ed
AND p3.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder’
AND e3.pathid = p3.pathid
AND e3.reidx = 1
AND e0.st < e3.st
AND e0.ed > e3.ed
AND p4.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder#/increase’
AND t4.pathid = p4.pathid
AND e3.st < t4.st
AND e3.ed > t4.ed
AND to_number(t2.value) * 2 <= to_number(t4.value)
ORDER BY t2.st;
この SQL 式は正常に実行することができる。
さらに「終了した競売で値段が 40 以上である競売を数える」ことを意味す
る、次のような XQuery 式について考える。
COUNT (
FOR $i IN document("auction.xml")
/site/closed_auctions/closed_auction
WHERE $i/price/text() >= 40
36
RETURN $i/price
)
この XQuery 式は XRel では次のような SQL 式に変換される。
SELECT count(t0.value)
FROM txt t0, pth p0
WHERE p0.pathexp LIKE ’#/site#/closed_auctions#/closed_auction#/price’
AND t0.pathid = p0.pathid
AND to_number(t0.value) >= 40;
しかしながらこの SQL 式を実行すると
AND to_number(t0.value) >= 40
*
ERROR at line 5:
ORA-01722: invalid number
との表示がなされる。
この不具合は 3,4 行目の実行を終えてから 5 行目の文の実行を行うことを
意図して SQL 式を作成したのが 、システムによる SQL 実行の最適化によっ
て実行順序がそのように行われなかったことによる。 このような不具合を解
決するための一つの手段として本節で提案する「数字データ XRel スキーマ」
が挙げられる。 これは次の二つの手法により実現できる。 また同様の不具合
は属性についても起こり得る。
(1) 文字列表に数字データを格納する関係属性を付加する
(2) 数字表を作成する
(1) の数字データ XRel の属性表、文字列表の関係スキーマは次のように
なる。
Attribute (docID, pathID, start, end, value, number)
Text (docID, pathID, start, end, value, number)
また (2) の数字データ XRel の数字属性表、数字文字列表の関係スキーマは
次のようになる。
37
NumberAttribute (docID, pathID, start, end, number)
NumberText (docID, pathID, start, end, number)
(1) の数字データ XRel スキーマによるデータベースの例の属性表、文字列
表をそれぞれ表 5.5, 5.6 に 、 (2) の数字データ XRel スキーマによるデータ
ベースの例の数字属性表、数字文字列表をそれぞれ表 5.7, 5.8 に示す。 前者は
「表拡張数字データ XRel 」、後者は「別表数字データ XRel 」と呼ぶことがで
きる。
表 5.5 (1) 数字データ XRel の属性表
docID
pathID
start
end
value
1
1
1
1
5
6
5
6
57
57
118
118
57
57
118
118
NAIST
32
RAIST
30
number
32
30
表 5.6 (1) 数字データ XRel の文字列表
5.5
5.5.1
docID
pathID
start
end
value
number
1
1
1
1
1
2
4
4
7
8
16
93
154
199
259
31
103
164
238
262
XML and Database
Yamada Taro
Sugita Ziro
XML stands for ...
2000
2000
位置条件 XPathCore グラフ
位置条件の出現場所による意味の違い
述語には大きく分けて
(1) 位置による条件付け
38
表 5.7 (2) 数字データ XRel の数字属性表
docID
pathID
start
end
number
1
1
6
6
57
118
57
118
32
30
表 5.8 (2) 数字データ XRel の数字文字列表
docID
pathID
start
end
number
1
8
259
262
2000
(2) 属性の存在やその値による条件付け
(3) 要素の存在やその値による条件付け
の三種類のものが存在し 、5.3 節で紹介した XPathCore グラフは一つの指示
単位に対してすべての述語は並列に並べられる。
しかし 、 XPath における位置条件は同じ指示単位内にあっても出現位置に
よってかかる場所が異なる。 すなわち
//author[family=”Yamada”][2]/given
は //author[family=”Yamada”] で指示される節のうち二番目のものを指す
//author の given であるのに対して、
//author[2][family=”Yamada”]/given
は //author で指示される節のうち二番目の節で family=”Yamada” を満たす
節の given 節を指す。 このように XPath で位置条件を複数含んだものは述語
の順序によって意味が異なる。 また XPathCore では位置条件を整数のみで指
定する、すなわち XPath における [position()>2] といった条件の指定はしな
いことになっているので、一つの指示単位内で二つ以上の位置条件を指定する
ことは無意味である。
そこで位置による条件付けをその他の述語とは区別し、次のように初期 XPath-
Core グラフを定義する。
39
A0 Plist0 A1 Plist1 · · · An−1 Plist(n−1) ?
ここで Ai (i = 0, · · · , n − 1) は SimpleAbsoluteRegularExpr を、 Plisti (i =
0, · · · , n − 1) は述語列を表す。 述語列 Plist は、位置条件を Pposition 、その他
の述語列を Pcommon
list
として次のように表す。
Plist := Pcommon
list ?
(Pposition Pcommon
list ?)?
位置条件 XPathCore グラフは図 5.11 のようなグラフとなる。 図 5.11 中の
Ai は SimpleAbsoluteRegularExpr を、 Plisti は位置条件の前の述語列を指す
節を、 Pi は位置条件の前の述語を、 Pposition は位置条件を、 Qlisti は位置条
件の後の述語列を指す節を、 Qi は位置条件の後の述語を表す。
A0
Plist0
P00
…
P0p0
Q00
An-1
…
Plist(n-1)
Ppostion0
Qlist0
…
A1
P(n-1)0
P(n-1)pn-1
Q(n-1)0
Q(n-1)qn-1
Pposition(n-1)
…
Q0q0
…
Qlist(n-1)
P10
Plist1
…
P1p1
…
Q1q1
Pposition1
Q10
Qlist1
図 5.11 位置条件 XPathCore グラフ
//author[family=”Yamada”][2]/given 、//author[2][family=”Yamada”]/given
の 初期 XPathCore グラフの例はそれぞれ図 5.12, 5.13 のようになる。
40
//author
//author/given
A0
A1
P00
Plist0
[//author/family=‘Yamada’]
Ppostion0
[2]
図 5.12 位置条件 XPathCore グラフの例 1
//author
//author/given
A0
A1
Ppostion0
[2]
Qlist0
Q00
[//author/family=‘Yamada’]
図 5.13 位置条件 XPathCore グラフの例 2
41
このように位置条件に基づいて定義した XPathCore グラフを位置条件 XPath-
Core グラフと呼ぶ。 しかしこのグラフは位置条件の有効範囲が表現できてい
ないという問題点がある。 そこで次にその問題点と解決手法について述べる。
5.5.2
XPathCore グラフにおける述語の有効範囲
位置情報 XPathCore グラフの問題点
5.3.3, 5.5.1 小節で述べたように、順序を指定した (すなわち位置条件を有す
る) XPathCore 式については XPathCore グラフで表現することができないも
のがある。 例として図 5.14 のような XML 木に対する次の４つの XPathCore
式について考える。
(1) /a/b[2]
(2) /a/b[c][2]
(3) (/a/b)[2]
(4) (/a/b)[c][2]
これら (1)–(4) 式のそれぞれの意味は次の通りである。
(1) それぞれの要素節点 a の子の要素節点のうち、要素節点 b の２番目のもの
(2) それぞれの要素節点 a の子の要素節点のうち、子に要素節点 c を持つ要
素節点 b の２番目のもの
(3) /a/b で表される経路のうち、２番目のもの
(4) /a/b で表される経路のうち、子の要素節点 c を持つ経路の２番目のもの
これらはそれぞれ次のように言い換えることができる。
(1) 要素節点 a を有効範囲とする、２番目の要素節点 b
(2) 要素節点 a を有効範囲とする、２番目の、子に要素節点 c を持つ要素節点
b
(3) 根節点 / (すなわち文書全体) を有効範囲とする、２番目の経路
(4) 根節点 / (すなわち文書全体) を有効範囲とする、２番目の、子に要素節
42
点 c を持つ経路
/
a
b
b
a
b
c
b
b
c
c
a
b
b
c
b
b
c
(1)
(2)
(3)
(4)
図 5.14 XML 木
これらより次のことが分かる。
(1) (1), (2) のように「 (, ) 」による節点のまとめがない場合、位置条件の述語
を有する指示単位の節点の親要素節点を有効範囲とする
(2) (3), (4) のように「 (, ) 」による節点のまとめがある場合、位置条件は文書
全体を有効範囲とする
このように 5.3.3, 5.5.1 小節で述べた XPathCore グラフでは位置条件の有効
範囲を明示的に示すことができない。
43
有効範囲を表示した位置情報 XPathCore グラフ
位置条件を有した節点に関してはその親要素節点を有効範囲として指定する
ことにより、位置条件のかかる範囲が分かる。有効範囲が分かるように (1)–(4)
を XPathCore グラフにしたものを図 5.15 に示す。 破線矢印は有効範囲を、、
A0 は有効範囲を示す節点をそれぞれ表す。 なお、(1) と (2) 、(3) と (4) をそれ
「 (/a/b)[.][2] 」と置き
ぞれ統一的に扱うため、(1),(3) はそれぞれ「 /a/b[.][2] 」、
換えた。
/a
A’0
/a/b
A0
/a
A’0
/a/b
A0
[.]
(1) /a/b[2]
(= /a/b[.][2])
/
A’0
[2]
[/a/b/c]
(2) /a/b[c][2]
/a/b
A0
[2]
/
A’0
[.]
(3) (/a/b)[2]
(= (/a/b)[.][2])
[2]
/a/b
A0
[/a/b/c]
(4) (/a/b)[c][2]
[2]
図 5.15 位置条件 XPathCore グラフの例 1
有効範囲を考慮した位置情報 XPathCore グラフを図 5.16 に示す。 図のよ
うに新たに節点 A0 をグラフに追加することになったが 、(1),(2) については節
点 A0 に相当する要素節点がある場合は新たに追加しなくてもよい。 すなわ
ち「 /a[d]/b[c][2] 」のような XPathCore 式は図 5.17 のような XPathCore グラ
フで表すことができる。
44
A’ 0
…
A0
A’ n-1
An-1
Plist0
Plist(n-1)
Ppostion0
Pposition(n-1)
Qlist(n-1)
Qlist0
図 5.16 位置条件 XPathCore グラフ
/a
A0
[/a/d]
/a[d]/b[c][2]
/a/b
A1
[/a/b/c]
[2]
図 5.17 位置条件 XPathCore グラフの例 2
45
(1)–(4) の４つの XPathCore 式のうち、図 5.15(1) の XPathCore グラフに
基づいて SQL 問合せに変換したものを次に示す。
(1) /a/b[2] (= /a/b[.][2])
SELECT e1.docID, e1.st, e1.ed
FROM element e0, pth p0, element e1, pth p1
WHERE p0.pathexp LIKE ’#/a’
AND e0.pathid = p0.pathid
AND p1.pathexp LIKE ’#/a#/b’
AND e1.pathid = p1.pathid
AND e0.docid = e1.docid
AND e0.st < e1.st
AND e0.ed > e1.ed
AND EXISTS (
SELECT *
FROM element e10, pth p1e
WHERE p10.pathexp LIKE ’#/a#/b’
AND e10.pathid = p10.pathid
AND e0.docid = e10.docid
AND e0.st < e10.st
AND e0.ed > e10.ed
AND e10.st < e1.st
)
AND NOT EXISTS (
SELECT *
FROM element e10, pth p10, element e11, pth p11
WHERE p10.pathexp LIKE ’#/a#/b’
AND e10.pathid = p10.pathid
AND e0.docid = e10.docid
AND e0.st < e10.st
AND e0.ed > e10.ed
AND p11.pathexp LIKE ’#/a#/b’
AND e11.pathid = p11.pathid
AND e0.docid = e11.docid
AND e10.st < e11.st
AND e0.ed > e11.ed
46
AND e11.st < e1.st
)
ORDER BY e1.docid, e1.st, e1.ed;
しかしながらこの XPathCore 式は要素表のデータベース属性 index を用い
て次のような SQL に変換することができる。
SELECT e0.docID, e0.st, e0.ed
FROM element e0, pth p0
WHERE p0.pathexp LIKE ’#/a#/b’
AND e0.pathid = p0.pathid
AND e0.index = 2
ORDER BY e1.docid, e1.st, e1.ed;
ただし「 /a//b[2] 」といった XPathCore 式については注意が必要である。と
いうのは「 b 」の親要素が指定されていないため、位置条件 [2] は節点 b の親
とは限らない先祖要素節点 a の有効範囲にあるため、後者のような SQL 問合
せは誤りとなるからである。 この XPathCore 式を SQL に変換したものは前
者の SQL 問合せ式中の文字列「 #/a#/b 」を「 #/a#%/b 」に置き換えたもの
になる。
5.6
文書名表付き XRel スキーマ
XRel に複数の XML 文書を格納する場合、問合せに文書名を用いることが
ある。 そのような場合、要素表、属性表、文字列表におけるデータベース属
性「 docid 」に対応する文書名のデータを保持する必要がある。 文書名表の関
係スキーマは次のようになる。
DocName (docID, docname)
文書名表の例を表 5.9 に示す。
47
表 5.9 文書名表付き XRel の文書名表
5.7
docID
docname
1
2
3
4
5
a and c.xml
all well.xml
as you.xml
com err.xml
coriolan.xml
XQuery から XRel 問合せへの変換
現時点ではまだ XQuery を XRel 問合せに機械的に変換する手法は開発さ
れていない。 XQuery 式を XRel 問合せに変換するには、まず XQuery 式か
ら XPathCore グラフに準ずるグラフ表現を描き、その後、 XPathCore グラ
フを SQL 式に変換する手法を参考にして SQL 式を求めることになる。
5.8
更新操作
基本 XRel では XML 文書木の節点の接続関係 (topology) を領域 (region)
、すなわちある節点の XML 文書中での開始位置と終了位置からなる整数値の
組により保存している。 この領域により節点の親子関係、兄弟関係を判定す
ることができるだけでなく、元の文書があれば対応する XML 文書断片を適当
な操作関数を用いて容易に求めることができる。 一般に、分解した XML 文
書から元の XML 文書 (断片) を復元する処理は計算量が大きくなるため、領
域を用いる手法は他の手法に対して有利である。
ところが 、領域は文書の更新に対しては有利であるとは言えない。 すなわ
ち、領域の値が正確な節点の位置を記録しているため、更新によって XML 文
書内での位置がずれてしまうと、多くの領域の値を修正しなくてはならない場
合がある。 この問題点に対して、 Kha らは、文書の先頭を起点とする相対的
な領域によって節点を表現する手法を提案している [18]。 他にも天笠らが開
48
発中の手法 (未発表) もある。
49
第6章
XRel の実装と応用
XRel の実装として、 XPath 式から SQL 問合せへの変換モジュールの実装
を行った [1]。 また応用として、シェイクスピア戯曲の検索システム、マウス
相補鎖 DNA 機能注釈の検索システムを構築した。 本節ではそれらの紹介を
行う。
6.1
XPath 式から SQL 問合せへの変換モジュール
XPath 式を SQL 問合せへ変換するモジュールである XPath2SQL について
説明する。
プログラム言語は Java を用いた。モジュール本体の雛型 (class) 名は XPath2SQL
で、入力は XPath 式で与えられる。 出力のための操作関数 (method) は表 6.1
の通り、入力された XPath 式を返す String getXPath() 、 XPathCore グラ
フを返す String getXPathCoreGraphExp() 、 SQL 式を返す String getSQL()
の三つである。
表 6.1 雛型 XPath2SQL
返り値型
String
String
String
操作関数名
getXPath()
getXPathCoreGraphExp()
getSQL()
意味
入力された XPath 式を返す
入力された XPath 式の XPathCore グラフを返す
入力された XPath 式から変換した SQL 問合せを返す
モジュール XPath2SQL は与えられた XPath 式を XPathCore グラフ表現
に変換する雛型 QueryGraph と QueryGraph により生成された XPathCore
50
グラフ表現を SQL 式に変換す雛型 GenerateSQL とからなる。このモジュー
ルのデータ処理の流れは図 6.1 のようになる。
XPath2SQL
XPath
getXPath( )
XPath
XPath
QueryGraph
XPathCore
Graph
XPathCore
Graph
SQL
getQueryGraphExp( )
getSQL( )
GenerateSQL
SQL
図 6.1 XPath2SQL モジュール
6.1.1
雛型 QueryGraph
雛型 QueryGraph では、与えられた XPath 式を区切り記号や単語毎に分解
するのに JavaCC (Java Compiler Compiler) 2.0 を用いた。 JavaCC は字句
解析・構文解析を行うための雛型のプログラムを自動生成するための道具であ
り、 Sun Microsystems が開発して無償で公開1 している。
雛型 QueryGraph では XPath 式を表 6.2 に示す単位で分解するために JavaCC
を用いる。
ま雛型 QueryGraph では、 XPath 式の分解単位をこのように定めて XPath
式を節、述語ごとに分解し 、 XPathCore グラフ表現を構築する。
XPathCore グラフ表現は次のような表示方法による。
1
<URL: http://www.webgain.com/products/java cc/>
51
表 6.2 XPath 式の分解単位
記号
識別子
備考
[
]
(
)
’
”
/
//
@
LBRACKET
RBRACKET
LPAREN
RPAREN
QUOT
DQUOT
SLASH
DSLASH
ATTRIBUTE
==
=
!==, !=
EQUAL
INCLUDE
NEQUAL
.
..
DOT
DDOT
,
!
?
\’
COMMA
DASH
EXCLAM
QUESTION
ESCQUOT
読点
[0-9]+ (. [0-9]+)?
NUMBER
数字
述語の始まりの区切り
述語の終りの区切り
まとまりの始まりの区切り
まとまりの終りの区切り
単一の文字列を表す区切り
単一の文字列を表す区切り
親子関係にある要素間の区切り
先祖・子孫関係にある要素間の区切り
属性を表す記号
左辺で指示される要素の文字列が右辺の文字列と等しい
左辺で指示される要素の文字列が右辺の文字列を含む
左辺で指示される要素の文字列が右辺の文字列と異なる
文脈節、句点
親節
横棒 (dash)
感嘆符
疑問符
文字列中で「 ’ 」を避難させたもの
52
(1) XPathCore グラフにおける Ai 節を「 A[i] 」、 Pij 節を「 P[i][j] 」、 Ppositioni
節を「 Pos[i] 」、 Qij 節を「 Q[i][j] 」と表す。
(2) 節 X が節 Y の有効範囲にあることを「 X scope of Y 」と表す。
(3) 述語が属性の存在 (例、[@age] など ) のとき、述語節への辺の標示を「 attr exist 」
とする。
(4) 述語が要素の存在 (例、[summary] など ) のとき、述語節への辺の標示を
「 exist 」とする。
(5) 述語が属性の値と文字列との比較 (例、[@affiliaion=’NAIST’] など ) であ
るとき、述語の左辺節への辺の標示を「 attr compare 」とする。
(6) 述語が要素の値と文字列との比較 (例、[author=’Yamada’] など ) である
とき、述語の左辺節への辺標示を「 text compare 」とする。
(7) 述語が属性または要素の値と文字列との比較でありかつ右辺が文字列で
あるとき、左辺節から右辺節への辺の標示の一つ目を「 litr 」とし 、二つ
目の標示は比較演算子が「 == 」、
「 = 」、
「 !== 」、
「 != 」のときそれぞれ
「 include 」、
「 nequal 」、
「 ninclude 」とする。
「 equal 」、
(8) 述語が属性または要素の値と文字列との比較であり、右辺が文字列でない
とき。
(i) 右辺が属性であるとき、左辺節から右辺節への辺の標示の一つ目を「 attr 」
とする。
(ii) 右辺が要素であるとき、左辺節から右辺節への辺の標示の一つ目を「 text 」
とする。
(iii) 二つ目の標示は比較演算子が「 = 」、
「 != 」のときそれぞれ「 include 」、
「 ninclude 」とする。
このようにして得られた XPathCore グラフ表現をもとに雛型 GenerateSQL
の実体が SQL 問合せを生成する。
53
6.1.2
雛型 GenerateSQL
XPathCore グラフ表現を頭から変換していくことで SQL 問合せを得ること
ができる。 変換手順は 5.3 節や文献 [17] を参照されたい。
6.1.3
例
モジュール XPath2SQL を用いた変換例を見る。
「著
例えば次の XPath 式は、図 3.1 で表されるような XML 文書に対して、
者が ’Yamada Taro’ であるような本の題名」を指す。
/book[authors/author=’Yamada Taro’]/title
この XPath 式は図 6.2 のような XPathCore グラフに表現でき、雛型 Query-
Graph の実体により次のように表現される XPathCore グラフ表現に変換さ
れる。
A[0] : ’#/book’
P[0][0] : compare
’#/book#/authors#/author’
literal equal
’Yamada Taro’
A[1] : ’#/book#/title’
scope of
’#/book’
scope of
’#/book’
さらに雛型 GenerateSQL の実体により次のような SQL 問合せに変換さ
れる。
SELECT DISTINCT e1.docid, e1.start, e1.end
FROM element e0, path p0, text t00, path p00, element e1, path p1
WHERE p0.pathexp LIKE ’#/book’
AND e0.pathid = p0.pathid
AND p00.pathexp LIKE ’#/book#/authors#/author’
AND t00.pathid = p00.pathid
AND e0.docid = t00.docid
AND e0.st < t00.st
AND e0.ed > t00.ed
AND t00.value LIKE ’Yamada Taro’
AND p1.pathexp LIKE ’#/book#/title’
54
AND e1.pathid = p1.pathid
AND e0.docid = e1.docid
AND e0.st < e1.st
AND e0.ed > e1.ed
ORDER BY e1.docid, e1.st;
/book/title
/book
scope of
A0
A1
scope of
Plist0
P00
compare
equal
/book/authors/author
‘Yamada Taro’
図 6.2 XPathCore グラフの例
6.2
6.2.1
シェイクスピア戯曲の検索システム
使用した XML データ
シェイクスピアの戯曲を Jon Bosak が標識付けした XML 文書2 を用いて、
XRel によるシェイクスピア戯曲の検索システムを実現した。 このデータは 37
の XML 文書からなり、大きさは総計約 7.65MB である。
2
<URL: http://metalab.unc.edu/bosak/xml/eg/sahkes200.zip>
55
6.2.2
システムの構成部品
このシステムは次の部品によりなる。
シェイクスピア戯曲のデータベース 全 37 文書を格納したデータベースと、37
文書のうちの 3 文書3 を格納した実験時間を短縮するためのデータベー
スの二つのデータベース。 PostgreSQL による。
ハイパーテキスト ウェブ閲覧ソフトウェアに表示するための部品。
Perl プログラム やり取りされるデータを変換するための部品。
XPath2SQL 入力された XPath 式を SQL 式に変換する部品。 Java による。
Display SQL 問合せの結果として指定される文書部分を XML 文書から抜き
出す部品。 Java による。
6.2.3
システムの利用方法
次にこのシステムの利用法を示す。
(1) 初期画面の「 XPath 」の文字列入力欄 (text input field) に XPath 式を入
力し 、
「変換」ボタンを押す。 (図 6.3 参照。)
(2) SQL 式表示画面になるので、全 37 文書に対する検索か、 3 文書に対す
る検索かを項目選択欄 (radio button) で選択し 、
「問合せ」ボタンを押す。
(図 6.4 参照。)
(3) SQL 問合せ結果表示画面になる。 XML 文書の部分を切り出すには「表
示」ボタンを押す。 (6.5 図参照。)
(4) XML 文書の XPath 式による問合せ箇所の部分文書が表示される。 (1) に
戻る。 (図 6.6 参照。)
3
「アントニーとクレオパトラ」、
「終りよければすべてよし 」、
「お気に召すまま」の 3 文
書。
56
図 6.3 XPath 式入力画面
図 6.4 SQL 式表示画面
57
図 6.5 SQL 問合せ結果表示画面
図 6.6 結果表示画面
58
6.3
マウス相補鎖 DNA 機能注釈の検索システム
XRel を用いてマウス相補鎖 DNA 機能注釈 (FANTOM) [19] の検索システ
ムを実現した。 このシステムでは次の検索を行うことができる。
(1) 識別子を用いた検索
(2) 検索語 (keyword) による検索 (複数の索引語に対して和積を組み合わせて
問合せをすることが可能である。 すべての注釈付け機関による注釈から
検索する。)
(3) 検索語による検索 (複数の検索語は和積のいずれかによる問合せを行う。
すべての注釈付け機関による注釈から検索する。)
(4) 検索語と注釈付け機関の指定による検索 (複数の検索語は和積のいずれか
による問合せを行う。)
(2)–(4) についての結果の表示は、問合せ結果の識別子のみを表示する簡易
表示と詳細情報を表示する通常表示とを選択できる。
6.3.1
使用した XML データ
理化学研究所ゲノム化学総合研究センターが完全長相補鎖 DNA (comple-
mentary DNA : mRNA ( メッセンジャ RNA (messenger RNA)) 分子の二本鎖
DNA の複製) の塩基配列を公開するにあたり、塩基配列だけでなく、注釈付
けを伴う形で公開することにより、全世界の研究者がより効果的、効率的にマ
ウス完全長相補鎖 DNA の情報を活用でき、生命科学分野の発展に貢献できる
と考えられた。 そこで、相補鎖 DNA に対する機能注釈の世界標準を確立し 、
2000 年 7 月末までに配列決定された 21076 個の相補鎖 DNA に対して機能注釈
を行なうために、つくば市の理化学研究所筑波研究所において 2000 年 8 月 28
日から 9 月 8 日にかけてマウス相補鎖 DNA 機能注釈 (Functional Annotation
of Mouse; FANTOM) 会議が開催された。 会議では 、マウス相補鎖 DNA 機
能注釈入力システムにより表示されるタンパク質データをはじめさまざまな遺
伝子情報のデータに対する解析結果に基づいて、会議に参加した研究者により
59
各相補鎖 DNA の注釈付けが行われた。 会議の結果 21076 個の相補鎖 DNA
のうち約 13000 個がマウス新規遺伝子であり、そして約 8000 個の遺伝子が哺
乳類におけるまったく新しい遺伝子であることが判明した。 また会議におい
て、種々の生物 (ショウジョウバエ、酵母、マウス、シロイヌナズナ、線虫) に
関連する集団が構成している Gene Ontology (GO) 協会とも協調し 、 GO の
語彙を用いた機能注釈付けを行われた。 これらの詳細な解析結果については
2001 年 2 月に Nature 誌 [20] において報告されると同時に 21076 個の相補鎖
DNA 塩基配列およびその機能注釈が理化学研究所のウェブサイト 4 より公開
された。
マウス相補鎖 DNA 機能注釈は XML により記述されており、本研究ではそ
のデータを使用した。 データは理化学研究所のウェブサイトから取り込んだ。
このデータは 21076 の XML 文書からなり、大きさは総計約 35.8MB である。
6.3.2
システムの構成部品
このシステムは次の部品によりなる。
マウス相補鎖 DNA 機能注釈データベース 全 21076 文書を格納したデータ
ベース。
ハイパーテキスト ウェブ閲覧ソフトウェアに初期画面として表示するための
部品。
Perl プログラム 問合せ結果を表示するための部品。
Search 問合せを SQL 式に変換し 、データベースに問合せを行う部品。 Java
による。
4
<URL: http://www.gsc.riken.go.jp/e/FANTOM/>
60
6.3.3
システムの利用法
本システムでは４種類の検索ができるがここではそのうち、
「複数の索引語
に対する和積を組み合わせた問合せ」による検索について説明する。
(1) 条件入力画面の「 Search by keywords (All Qualifiers) 」の文字列入力欄
(text input field) に索引語を入力し 、
「 submit 」ボタンを押す。 (図 6.7
参照。)
(2) 問合せに適合する XML 文書の識別子の一覧が表示されるので、注釈を見
たい識別子の「 annotations 」欄の「 View 」を押す。 (図 6.8 参照。)
(3) 指定した識別子に対して付与された注釈が表示される。 (図 6.9 参照。)
図 6.7 条件入力画面
61
図 6.8 問合せ結果表示画面
図 6.9 注釈表示画面
62
第7章
評価
本章では、まず 7.1 節で XML データベースの性能評価技術の概要ついて、次
に 7.2 節で XML データベースの性能評価指標 Xmark について述べる。 そ
の後、7.4 節では Xmark を用いて行った XRel の性能評価実験について述べ
る [1]。
7.1
XML データベースの性能評価技術
XML データベースを実現するための多くの手法が提案されているため、そ
れらの性能を定量的に比較するための性能評価指標が開発されつつある。 文
献 [11] は XML 性能評価指標が備えるべき測定基準を次のようにまとめている。
(1) 一括格納 (bulk loading)
(2) 再構成 (reconstruction) : 一括格納の逆の概念である。 もとの XML 文書
を再構成する。
(3) 経路横断 (path traversal) : 冗長性、データ量、断片化の二律背反を表す。
(4) 型変換 (casting) : 文字列から整数、浮動小数点数、利用者定義型への型
変換。 文字列演算は非常に遅い。
(5) 失要素 (missing element) : ある種の写像では、多くの無 (NULL) 値が生
じる。 無値を小容量に記憶する戦略とは別に、しばしば興味の対象とな
る無値を効率的に問合せを行なう方法も必要である。
(6) 順序接続 (ordered access) : 順序が不要な場合は、それを無視して問合せ
処理を高速化するなどの柔軟性が必要である。
(7) 参照 (references) : 参照を処理するには、文書に渡って無作為接続を効率
的に支援する方法が必要である。
63
(8) 結合 (joins) : データ中心の応用における、要素や属性の内容に基づく結
合を表す。
(9) 包含、全文検索 (containment, full-text search)
XML 問合せ処理器の性能評価の枠組として、次節で説明する Xmark [12]
が開発されている。 このような問合せ処理器以外の面の評価項目としては次
のものがある [11]。
システム基盤 (infrastructure) データベースの入力側 (front end) と出力側
(back end) が密接に統合されていなければ通信費用がかかり、問合せ処
理器の性能が十分に発揮されない。 したがって 、以下の問題点が挙げ
られる。 また、主としてシステムに焦点を当てた性能評価指標である
XMach-1 [13] では、これらのいくつかを取り上げている。
接続規約 (access protocol) HTTP, OLEDB, ODMG, ODBC, native
APIs など 。
結果の表示 DOM, SAX, 一次元 XML 化など 。
応答性と完全性 最初のおよび完全な問合せ結果の利用可能性。
問合せ言語の表現能力 XPath にはない再構成の能力が問合せ機関 (en-
gine) が与えられた応用の台本 (scenario) に適合するかど うかを決
める。
複数利用者応用台本におけるデータ処理能力 (throughput)
所有の費用 ソフトウェア自身よりもその所有の費用の方が高価になりつつあ
るため、次の点が重要である。
(1) 導入 (install)
(2) スキーマ (schema) 情報とともに 、あるいは 、スキーマ情報なしに
文書を格納できるか否か。
(3) 入ってきた文書を、あるスキーマあるいは他の制約に関して妥当性
を検査できるか否か。
64
(4) 文書を格納する前にどのような写像および スキーマ定義が必要とな
るか。
(5) 訓練
(6) 対話の範例 (paradigm) : 直接対話のための手段をもつ単独の (standalone) 文書管理システムか、入力側の応用のための技術か。
(7) 細粒度更新機能を提供するか否か。 あるいは文書全体の置換えに限
られているか。
7.2
Xmark
本節では本研究において XRel の性能評価を行うために用いた、 XML デー
タベースの性能評価指標である Xmark について説明する。
7.2.1
Xmark の概要
既存のデータベース性能評価指標は、問合せ最適化から論理作業単位 (トラ
ンザクション ) 管理までに及ぶ、データ管理に関する伝統的なあらゆる側面を
網羅している。しかしながら XML 文書を格納し処理するといった確立した技
術を利用する場合であっても、これらの技術に対して半構造データが性能上の
問題に影響を与えるか否かは不明である。 また関係データベースの発展とは
異なり、 XML は早期の段階から合意された標準があったこので、性能評価に
ついて天下り的な (top-down) 考え方をすることになった。 したがって XML
処理システムにおいては、伝統的な特徴と新たな特徴との結合による新たな性
能評価指標が必要となる。 そこで Xmark 計画では XML データベースの性能
評価指標のために、規模変更可能な (scalable) XML 文書の生成と、 XQuery
による問合せの集合を提供している。 ただし 、従来の XML 性能評価指標は
データの更新に関する性能も評価しているが 、データの更新の正確な意味や標
準、さらに同意がないことから更新については扱っていない。
65
7.2.2
XML 文書の生成
XML 性能評価指標を作るためには、問合せの振舞を予測でき、自然で簡潔
な問合せの形式となるようなデータベースの例を設計する必要がある。 Xmark
で想定する XML 文書は 、インターネットの競売サイトで実施されるデータ
「開催
ベースを模倣した文書構造となっている。 主な実体は「人 (person) 」、
中の競売 (open auction) 」、
「終了した競売 (closed auction) 」、
「物品 (item) 」、
「種類 (category) 」である。 階層スキーマは図 7.1 のようになっている。
site
regions
open_auctions
people
{africa, asia, …}
closed_acutions
person
homepage
catgraph
categories
category
closed_acution
creditcard
annotation
price itemref
description
name profile
description
item
income
edge
description
reserve
mailbox
name
from
open_acution
to
mail
annotation
description
bidder initial itemref
increase
図 7.1 Xmark スキーマ
生成される XML 文書中の単語の現れ方は 、シェイクスピアの戯曲で最も
よく現れる 17000 の単語の出現頻度分布を模倣している。 また、次のような
XML 文書の処理に最低限必要な条件のみを有している。
(1) 注釈を含まない
66
(2) 名前空間を利用しない
(3) 7 ビット ASCII 文字集合で構成される
Xmark では 上記のような XML 文書を生成するための xmlgen という XML
文書生成器を設計、公開している。 xmlgen の特徴としては次の３点が挙げら
れる。
プラット フォームに非依存 ハード ウェアや OS によらず同一の文書が生成さ
れる。
規模変更因子 生成する文書の大きさを決めるための因子。 0 以上でシステム
の許容量による限界まで設定することができる。1
資源の割当が一定 生成する文書の大きさは主記憶装置の大きさに依存しない。
7.2.3
XML データベースへの問合せ
XQuery は明示的にはデータベース問合せ言語として設計されていないが 、
データベース管理システムが XML のデータ管理をすることには疑いがない
ので、 Xmark では問合せ言語として XQuery を選択している。 また、 XML
データベースとしての性能を総合的に評価するための 20 の問合せを提案して
いる。 例えば XML データベースに対して「順序関係を伴った問合せの処理」
を評価するための問合せとしては、この 20 の問合せのうち 3 つが該当する。
この問合せの一つである「すべての開催中の競売の最初の増加 (increase) を返
す」という問合せは次のような XQuery で与えられる。
FOR $b
IN document("auction.xml")/site/open_auctions/open_auction
RETURN <increase>$b/bidder[1]/increase/text()</increase>
1
最
小
の
文
書
の
大
き
さ
は
規
模
変
更
因
子
が 0 以上 0.00007843137254901960323102624861313358906045323237776756287 未満のとき
で 26713 バイト
67
7.3
Xmark による XRel の性能評価
Xmark で用意されたすべての XQuery 式による問合せを XRel で行うには
5.4 節で提案した数字データ XRel を用いる必要がある。 しかし本研究では
XRel の XML データベースとしての性能を評価するために基本 XRel を用い、
数字データ XRel を用いる必要のある問合せは行わない。
7.3.1
XML 文書の格納
7.2.2 小節で説明した Xmark において用意された XML 文書を、 XRel に
より関係データベースに格納した。 表 7.1 に格納データの詳細を示す。 XML
文書を生成する際の規模変更因子は 0.01 とした。
表 7.1 格納データの詳細
文書数
文書の大きさ (バイト )
要素節点数
属性節点数
文字列節点数
経路数
7.3.2
1
1161652
17132
3819
12154
454
XQuery 式の XRel 問合せ式への変換
現時点では XQuery による問合せを XRel の問合せに機械的に変換する一般
的な手法はない。 したがって、 Xmark で用意された問合せは手作業で XRel
問合せに変換することになる。 たとえば前節における XQuery による問合せ
である「すべての開催中の競売の最初の増加を返す」という問合せを XRel 問
合せに変換したものは次のように示される。
SELECT ’<increase>’||t1.value||</increase>’
FROM element e0, pth p0, txt t1, pth p1
68
WHERE p0.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder’
AND e0.pathid = p0.pathid
AND e0.idx = 1
AND p1.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder#/increase’
AND t1.pathid = p1.pathid
AND e0.st < t1.st
AND e0.ed > t1.ed
ORDER BY t1.st;
規模変更因子を 0.01 としたため不適切となった問合せがある。 Q4 は「識
別子が (personid) が person10487 である人の前に person18829 である人が値
をつけた開催中の競売 (open auction) の予約 (reserve) を返す」という問合せ
であるが 、規模変更因子が 0.01 となったため person10487, person18829 とい
う personid が XML 文書に表れない。 そこで person10487, person18829 は
それぞれ person175, person251 と変更する。
付録 A に XQuery 式を XRel の SQL 問合せ式に変換した式を掲載する。
7.4
性能評価実験
7.2 節で紹介した Xmark を用いて XRel の性能評価を行った。
7.4.1
実験環境
実験に使用した計算機および環境を表 7.2 に示す。
表 7.2 実験に使用した環境
中央演算装置
主記憶容量
基本ソフトウェア
データベース
Pentium 4 (1.8GHz)
1GB
MIRACLE LINUX Standard Edition Version2.0
Oracle9i Database Standard Edition Release1 (9.0.1) for Linux
69
XML 文書は、規模変更因子を 0.012 として xmlgen によって生成した。XML
文書の大きさは 1161652 バイト (約 1.2M バイト ) である。
また、問合せは Xmark で提供されている 20 の問合せのうち、基本 XRel
で実行可能な 15 の問合せについて実験を行った。
7.4.2
比較対象
比較対象としては、 XML 文書の問合せ処理器である XML Query Engine3
(以下、XQEngine という。) を用いた。 XQEngine は、 Java により記述され、
XPath, XQL, XQuery による問合せを行うことができる。 ただし 、XQuery
の規格に完全には対応しておらず、 Xmark で用意された 20 の問合せすべて
を実行することはできない。 表 7.3 にこの問合せの実行の状況を示す。 これ
らのうち Q18, Q19 はそれぞれ利用者定義関数を用いる能力、整列 (sort) を
行う能力を測定する問合せである。 XQEngine はこの二つの機能に対応して
おらず、本実験ではこれらの機能を用いずに問合せを行ったため参考程度の結
果である。 なおこれらの詳細は付録 B を参照のこと。
7.4.3
実験と考察
表 7.4 に実験結果を示す。 表は各問合せの実行時間を表しており、それぞれ
10 回の平均値である。 正規化値については次小節で述べる。
次に実験結果について、 XRel を単独で、また XRel と XQEngine とを比
較して考察を行う。
2
規模変更因子を 0.01 とした理由は、 XQEngine で処理可能な要素数が 32768 までとい
う制約があったため。
3
<URL: http://www.fatdog.com/>
70
表 7.3 XQEngine による Xmark 問合せの実行
問合せ番号
状況
Q1
XPath 式による準じた問合せを行う
Q2
XPath 式による問合せを行う
Q3
問合せ不可能
Q4
問合せ不可能
Q5
問合せ不可能
Q6
XPath による準じた問合せを行う
Q7
問合せ不可能
Q8
問合せ不可能
Q9
問合せ不可能
Q10
問合せ不可能
Q11
問合せ不可能
Q12
問合せ不可能
Q13
XQuery による準じた問合せを行う
Q14
問合せ不可能
Q15
XQuery による準じた問合せを行う
Q16
XPath による準じた問合せを行う
Q17
問合せ不可能
Q18
(XPath による準じた問合せを行う)
Q19
(XQuery による準じた問合せを行う)
Q20
問合せ不可能
71
表 7.4 実験結果
問合せ番号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
XRel (ms)
XQEngine (ms)
6.8
73.2
599.7
56.0
–
8.8
33.2
257.7
4383.0
–
–
–
18.2
245.8
14.6
95.0
256.1
13.9
2807.4
–
48.5
3509.3
(XRel)/(XQEngine)
0.140
0.0209
–
–
–
–
–
–
2761.9
0.00319
–
–
–
–
–
–
–
–
–
–
–
–
129.9
0.140
–
–
214.6
226.8
0.0680
0.419
–
(2647.3)
(2837.6)
–
–
(0.00525)
(0.989 )
–
72
正規化値
(XQEngine)/(XRel)
2.06
0.307
–
–
–
0.0469
–
–
–
–
–
–
2.06
–
1
6.16
–
(0.0772)
(14.5 )
–
7.13
47.9
–
–
–
314
–
–
–
–
–
–
7.14
–
14.7
2.39
–
(190 )
(1.01)
–
XRel 単独の考察
XRel の問合せは、指定する節点に対応する経路を検索し 、節点同士の包含
関係を調べ、文字列照合、順序節などの条件に合致するかを調べる、といった
手順で行われる。 そこでそれぞれの問合せについて、経路数、包含関係の数、
文字列照合の数、順序節の数その他の特徴を表 7.5 に示す。
表 7.5 問合せの分析
問合せ
時間 (ms)
経路
包含関係
文字列照合
順序節
その他の特徴
1
6.8
3
1
1
0
2
73.2
2
1
0
1
3
599.7
5
4
0
2
数字の大小を比較が 1 つ
4
56.0
4
3
2
0
先行関係
文字列照合は属性表
文字列照合は属性表
6
8.8
1
0
0
0
経路表現に「 // 」
数え挙げた結果を表示
7
33.2
3
0
0
0
すべての経路表現に「 // 」
数え挙げた結果を表示
8
257.7
4
1
0
1
文字列の比較が 1 つ
9
4383.0
9
5
0
2
文字列の比較が 2 つ
13
18.2
3
2
0
0
14
245.8
4
3
1
0
すべての経路表現に「 // 」
文字列照合は文字列表
15
14.6
1
0
0
0
16
95.0
3
2
0
0
17
256.1
3
2
0
0
18
13.9
1
0
0
0
19
2807.4
3
2
0
0
「 NOT EXISTS 」を利用
すべての経路表現に「 // 」
整列
73
条件に文字列照合を有する問合せ
条件に文字列照合を有する問合せは Q1,
Q4, Q14 である。 これらの問合せについて文字列照合の条件が問合せ実行に
与える影響をみるために、条件をなくした問合せの実行時間と比較したものを
表 7.6 に示す。
表 7.6 文字列照合を有する問合せ
条件付き (ms)
条件無し (ms)
条件無し / 条件付き
1
6.8
103.8
15.3
4
56.0
1217.4
21.7
14
245.8
2003.0
8.15
問合せ番号
特に、 Q1 は属性表について「 @person=’person0’ 」を満たす一つの組に絞
られるため、 Q4 は二つの節点について文字列照合が行われるため、実行時間
が大幅に減少すると考えられる。 これより、文字列照合により文字列表 (属性
表) で候補となる組が絞られるため、表同士で結合される組数が減少するため
計算量が少なくなるからと考えられる。
条件に順序節を有する問合せ
条件に順序節を有する問合せは Q2, Q3 である。
Q2 Q2 について順序節の条件が問合せ実行に与える影響をみるために 、順
序節の条件をなくした問合せの実行時間と比較したものを表 7.9 に示す。
表 7.7 順序節を有する問合せ
問合せ番号
2
条件付き (ms)
条件無し (ms)
条件無し / 条件付き
73.2
264.1
3.61
このように Q2 は文字列表について「 e0.index = 1 」を満たす組に絞られる
ため、表同士で結合される組数が減少するため計算量が少なくなると考えら
れる。
74
Q3 Q3 では数字の大小比較を行うため、本来数字データ XRel を用いる必要
がある。 すなわち 基本 XRel により問合せを行うと「 to number(t2.value) ∗
「 t2.value 」、
「 t4.value 」が数字でない
2 <= to number(t4.value) 」に関して、
として実行不可能となるが 、 Q3 についてはその他の条件により数字データの
みが選択された後に「 to number() 」の関数が適用されるため、実行可能とな
る。 すなわち文字列表 (属性表) の文字列同士の比較が生じるために計算量が
多くなる。 これにより順序節の条件を有したことによる計算量の減少が打ち
消されて実行時間が長くなると考えられる。
COUNT による表示 COUNT で数えた結果のみを表示する問合せは Q6,
Q7 である。 COUNT で結果を数えるだけの問合せと節点の内容を表示する
問合せとの実行時間を比較したものを表 7.8 に示す。
表 7.8 COUNT による表示
結果の数の表示 (ms)
節点内容の表示 (ms)
結果の数 / 節点内容
6
8.8
20.1
0.438
7
33.2
36.2
0.917
問合せ番号
これより節点の内容を表示することよりも COUNT により結果の数のみを
表示する方が計算量が少ないことが分かる。
経路表現に「 //」を有する問合せ
経路表現に「 // 」を有する問合せは Q6,
Q7, Q14, Q19 である。 Q6, Q7 は COUNT により結果の数のみを表示する問
合せであり、問合せに対する「 // 」の影響を調べることができない。 そこで
前述の「 COUNT による表示」で行った、結果の節点内容を表示する問合せを
用いる。 Q6, Q7 はともに節点間の包含関係の演算はない。 そこで同じく包
含関係の演算がない Q15 と比較する。 また Q14, Q19 はそれぞれ包含関係の
数が 3, 2 つであるから、それぞれ包含関係の数が同じである Q4, Q16 と比較
する。
75
表 7.9 経路表現に「 // 」を有する問合せ
実行時間 (ms)
比較問合せ (ms)
Q# / 比較
0
20.1
14.6
1.37
7
0
36.2
14.6
2.48
14
3
245.8
56.0
4.39
19
2
2807.4
95.0
29.6
問合せ番号
包含関係数
6
これより経路指定に「 // 」を含む問合せに関しては XRel は不得意であると
いえる。 これは経路の数に比例した結合演算が必要なこと、また「 // 」の文
字列照合に SQL のワイルド カード 機能 (%) を用いており、これらの処理に要
する計算量が多くなることによると考えられる。
表示順序による影響
XQuery では問合せ結果の表示順序は XQuery 式によ
り決定される。 しかし問合せの結果のみが必要でその順序に意味がない場合
や、得られた結果に対してシステムが改めて順序の並べ代えを行う場合につい
ては XRel 問合せの結果の順序について考慮する必要はない。 そこで結果の
順序を考慮する場合と無視する場合との実行時間の比較を表 7.10 に示す。
文字列の比較
文字列の比較を有する問合せは Q3, Q8, Q9 である。 これら問
合せは二つの Text 表の文字列のデータベース属性同士の比較 (Q3:大小比較、
Q8,Q9:文字列の一致) を行う。 これらの問合せの実行時間が大きくなるのは
文字列同士の比較により表の結合が行われるからと考えられる。
指定する経路数の影響
問合せにおける指定する経路数の影響をみるために、
指定する経路数を横軸に、実行時間の対数を縦軸にとったグラフを図 7.2 に示
す。 このグラフのみから経路数と実行時間の直接の関係はいうことが難しい
が 、前述の特殊な条件 (文字列照合の有無、順序節の有無、表示に要する計算
量、経路指定の「 // 」の有無、結果の表示順序など ) も考慮すると、経路数の
増加に伴い実行時間は指数的に増大するといえる。 このことは経路数に比例
76
表 7.10 表示順序による実行時間の違い
問合せ番号
1
2
3
4
6
7
8
9
13
14
15
16
17
18
19
検索結果の数
順序を考慮 (ms)
順序を無視 (ms)
無視 / 考慮
考慮 / 無視
1
106
22
1
217
661
55
28
22
17
7
7
138
64
217
6.8
73.2
599.7
56.0
(20.1)
(36.2)
257.7
4383.0
18.2
245.8
14.6
95.0
256.1
13.9
2807.4
6.6
31.4
202.1
52.2
8.8
33.2
251.3
1011.9
8.2
239.2
14.5
95.2
17.1
10.8
(839.8)
0.971
0.429
0.337
0.932
0.438
0.917
0.975
0.231
0.451
0.692
0.993
1.00
0.0668
0.777
(0.299)
1.03
2.33
2.96
1.07
2.28
1.09
1.03
4.33
2.22
1.03
1.01
0.998
15.0
1.29
(3.34)
77
した回数、関係データベースにとって不利である関係表の結合演算が行われる
ことが原因と思われる。
10000.0
Q9:compare
Q19:「//」
1000.0
実行時間
Q17:
NOT EXISTS
Q3:compare
Q8:compare
Q14:「//」, matching
100.0
Q7:「//」, COUNT
Q13
Q15, 18
Q6:
「//」, COUNT
10.0
Q4:matching
Q16
Q2
Q1:matching
1.0
0
1
2
3
4
5
6
7
8
9
10
指定する経路数
図 7.2 指定する経路数の影響
XRel 単独の考察のまとめ
有利な問合せ
前述の考察より、以下の問合せは XRel にとって有利にはた
らく。
(1) 指定する経路数が少ない問合せ
(2) 条件に文字列照合を有する問合せ
(3) 条件に順序節を有する問合せ
(4) 検索結果の表示の計算量が少ない問合せ
78
(5) 結果の表示順序が拘束されていない問合せ
不利な問合せ
以下の問合せは XRel にとって不利にはたらく。
(1) 指定する経路数が多い問合せ
(2) 条件に文字列の比較を有する問合せ
(3) 指定する経路表現に「 // 」を有する問合せ
(4) 検索結果の表示の計算量が大きい問合せ
(5) 結果の表示順序が拘束された問合せ
XRel と XQEngine との比較による考察
XRel, XQEngine の両方について意味のある実験が行うことができた問合せ
は Q1, Q2, Q6, Q13, Q15, Q16 の 6 つの問合せである。 これら 6 つの問合せ
についてはすべてにおいて XRel の方が XQEngine よりも高速に処理してい
る。 ここではさらに、それぞれについて、得意不得意な問合せの特徴をみる
ために、実行時間の正規化を行った上で考察を加える。
一般に XML 文書の問合せは経路指定を基本としてなされる。 そこで経路
を指定した検索である Q15 の問合せを基準とする。 そこで Q15 の XRel と
XQEngine の実行時間の比を 1 として正規化した比が表 7.4 の「正規化値」の
欄の値である。 なお、正規化のために Q15 を基準としたが 、この問合せに関
する実行時間の比は 0.068 である。 このことは XRel は XQEngine に対して
15 倍程度性能がよいことを示す。 XRel が得意とする問合せかど うかを正規
化値が 1 より小さいかど うかにより分類して考察する。
XRel が得意とする問合せ 正規化値が 1 より小さい問合せは、経路を指定
した問合せを基準として、 XQEngine が問合せに対して有する傾向に対して
XRel が得意であると言える。 この傾向を有する問合せは Q2, Q6 である。 Q2
は順序節を用いた問合せであり、順序節を有する問合せが XQEngine に比べ
て得意であることが分かる。 この理由は 、 XRel では要素表に順序に関する
データ (index, reindex) も格納しており、このデータを有効に利用できたから
79
と考えることができる。 Q6 は「 // 」を用いて経路を指定した問合せであり、
指定する経路中に「 // 」を有した問合せが XQEngine に比べて得意であるこ
とが分かる。 この理由は、 XRel では経路指定が単なる文字列照合になって
おり、
「 // 」についてはワイルド カード (%) を用いた文字列照合により実現さ
れている4 からと考えることができる。
XRel が不得意とする問合せ 正規化値が 1 より大きい問合せは 、経路を指
定した問合せを基準として、 XQEngine が問合せに対して有する傾向に対し
て XRel が不得意であると言える。 この傾向を有する問合せは Q1, Q13, Q16
である。 Q1, Q13, Q16 はともに指定する経路が三つの問合せであり、指定す
る経路が一つである Q15 とは異なり表の結合が必要となり、計算量が大幅に
増えることにより実行時間が増大すると考えることができる。
4
経路中の「 // 」はワイルド カード (%) を用いた文字列照合により実現していることにつ
いては 5.3.1 小節参照。
80
第 8 章 まとめと今後の課題
8.1
まとめ
本論文では関係データベースを用いた XML 文書の格納および検索手法であ
る XRel の実装とその評価について述べた。
XRel の実装については、 XPath 式から SQL 問合せへの変換モジュール 、
シェイクスピアの戯曲の検索システム、マウス相補鎖 DNA 機能注釈の検索
システムの実装を行った。 XPath 式から SQL 問合せへの変換モジュールを
実現することにより、利用者から与えられた問合せ式をシステム側で自動的に
SQL 式に変換し 、関係データベースへの問合せをすることができる。 シェイ
クスピアの戯曲の検索システム、マウス相補鎖 DNA 機能注釈の検索システム
を実現することにより、 XML 文書の検索システムとして汎用的に XRel を用
いることができる可能性があることが分かった。
さらに、 XRel の XML データベースとしての有効性を示すために、 Xmark
により性能評価の実験を行った。実験の結果、 指定する経路の増加にともな
い検索効率が指数的に悪化するものの、他の XML データベース検索システ
ムである XQEngine と比較するときわめて高効率の検索を行うことが示せた。
これより XRel の XML データベースとしての性能が高いことが分かった。
本研究により、 XRel は汎用性に優れていること、および XRel によって検
索効率のよいシステムの構築が可能であることが示せた。
81
8.2
8.2.1
今後の課題
XQuery 式から SQL 問合せへの変換手法の確立
SQL 式を駆使することにより XML 文書に対し多種多様な問合せが可能で
ある。 実際、本論文では Xmark の XQuery による問合せを手作業により SQL
問合せに変換した。 しかし XRel がより汎用的に XML データベースシステ
ムとして用いられるには、 XQuery 式を SQL 問合せに自動的に変換する手法
を開発する必要がある。
8.2.2
XML 文書の更新
また，現在提案されている XRel では， XML 文書の各要素、属性、文字列
の文書内での位置を「ファイルの先頭から何バイト目か」という情報を用いて
格納している。 したがって、文書内容の更新により多くのデータを変更する
必要がある。 しかしこのことは、更新が頻繁におこるシステムでは不利であ
る。 そこで文書内容の更新があった場合でも、更新箇所を最小にとど めるこ
とのできる手法の開発が必要である。
82
謝辞
本研究の遂行にあたって多くの方々のご指導ならびにご協力を得ることができ
ました。 以下にその方々への謝意を記します。
植村俊亮教授には研究の進めかた、論文の書きかたなど 研究のあらゆる面に
おけるご指導、ご指摘を賜わりました。 また日常生活においても、広く深い
教養に基づくお話によって常に筆者によい刺激を与えていただきました。 こ
こに心からの謝意を記します。
松本裕治教授には、ご多忙中にも関わらず、修論発表会等において的確なご
指導、ご助言を賜わりました。 ここに心からの謝意を記します。
吉川正俊助教授には、本研究の遂行にあたってその方向性を明確に示してい
ただき、たびたび設けていたきました研究の進捗状況の報告会では常に的確な
ご指導、ご助言を賜わりました。 また日常生活においても、機知に富んだお
話により心に爽快な風を送っていただきました。 ここに心からの謝意を記し
ます。
天笠俊之助手には、本研究での XRel の実装、実験等に関して、また計算機
の環境設定や問題の解消に関して、数多くの的確なご指導、ご助言を賜わりま
した。 また日常生活においても、難波や三宮に連れていっていただくなど生活
を有意義にしていただくことができました。 ここに心からの謝意を記します。
波多野賢治助手には、本研究の遂行にあたって、全体研究会等において的確
なご 指導、ご助言を賜わりました。 また日常生活においても、特に水曜日に
文献調査に協力していただくなど 心に余裕を持たせていただきました。 ここ
に心からの謝意を記します。
秘書の今田薫氏には、本研究の遂行にあたって縁の下でのご協力を賜わりま
83
した。 また日常生活における心なご むお話によって、間接的に研究の効率を
向上させていただくことができました。 ここに心からの謝意を記します。
前秘書の小林園子氏には、１ヵ月でしたが同じく本研究の遂行にあたって縁
の下でのご協力を賜わることができました。
本研究室の先輩の絹谷弘子氏、今城哲二氏、福原智宏氏には、特に全体研究
会で発表される姿勢を通じて、研究のありかたを示していただきました。 こ
こに心からの謝意を記します。
本研究室の先輩の三宮健氏には、特に全体研究会で発表される姿勢およびそ
の洗練された発表術を通じて研究のありかたを示していただきました。 また
特に学際領域特論 A (情報考古学) の報告書を書く際におおいにお世話になっ
たことはかけがえのないない思い出となっております。 ここに心からの謝意
を記します。
My seniors, Ms. Fatiha Sadat and Mr.Dao Dinh Kha, has shown me how to
research through their presentation. And for my research, they kindly checked
my abstract in English. I show devout thanks.
本研究室の先輩の鈴木優氏には、研究室の計算機環境を維持していただくこ
とによる間接的なご協力、研究に関する議論を通してのご指導、ご助言をいた
だきました。 また日常生活においても、おいしい店に関する豊富な知識で筆
者の舌とお腹を満足させていただきました。 ここに心からの謝意を記します。
本研究室の先輩の羅勇氏には、研究室の計算機環境を維持していただくこと
による間接的なご協力、研究に関する議論を通してのご指導、ご助言をいただ
きました。 また日常生活においても、中国文化に関して色々教えていただく
ことができました。 ここに心からの謝意を記します。
本研究室の先輩の木村文則氏には、研究室の計算機環境を維持していただく
ことによる間接的なご協力、研究に関する議論を通してのご指導、ご助言をい
ただきました。 また夏合宿の帰りの車中では助手席で色々なお話をしていた
だいたことはかけがえのない思い出となっております。 ここに心からの謝意
を記します。
本研究室の先輩の杉山一成氏には、本研究の遂行にあたって、特に本論文を
84
点検していただきご 指導、ご助言をいただきました。 また日常生活において
も、その人柄により楽しい気分にさせていただくことはたびたびでした。 こ
こに心からの謝意を記します。
本研究室の先輩の竹内さおり氏には、特に全体研究会で発表される姿勢を通
じて、研究のありかたを示していただきました。 また日常生活でも、その風流
な人柄により日本のよさを再確認させていただくこともたびたびでした。 こ
こに心からの謝意を記します。
本研究室の先輩の上田隆正氏には、特に全体研究会において的確なご指導、
ご助言をいただきました。 また商店にはたびたびお世話になりました。 ここ
に心からの謝意を記します。
本研究室の先輩の大田智数氏には、特にプログラムにおいて的確なご指導、
ご助言をいただきました。 またその超越された人柄によりおおいに感心させ
られたことはたびたびです。 ここに心からの謝意を記します。
本研究室の先輩の高野正樹氏には、特にプログラム、計算機の問題解決にお
いていただいた多大かつ的確なご指導、ご助言なしには、本研究はありえませ
んでした。 また日常生活においても、その独特な人柄により楽しませていた
だいたこともたびたびでした。 ここに心からの謝意を記します。
本研究室の先輩の田上純子氏には、特に生物情報学に関して的確なご指導、
ご助言をいただきました。 また本論文の印刷の際に印刷機がカートリッジの交
換をしなければいけなくなったとき、その交換をしていただけたときには感動
のあまり涙が出そうになったことはかけがえのない思い出となっております。
ここに心からの謝意を記します。
本研究室の先輩の的場登氏には、本研究の遂行にあたって議論を通してご指
導、ご助言をいただきました。 また特に電子メールでの独特の終りかたに励
まされることはたびたびでした。 ここに心からの謝意を記します。
本研究室の先輩の渡邉正裕氏には、本研究の遂行にあたって、特に全体研究
会で発表される姿勢を通じて、研究のありかたを示していただきました。 ま
た日常生活においては、特に本学についての豊富な知識により教えていただい
たことにより充実した生活を送ることができました。 ここに心からの謝意を
85
記します。
本研究室の先輩の石川正敏氏には、本研究の遂行にあたって、特に学生室で
研究される姿勢を通じて、研究のありかたを示していただきました。 また食
事の早さに驚かされたことはかけがえのない思い出となっております。 ここ
に心からの謝意を記します。
My senior Mr. Le Anh Cuong has shown me how to research through his
presentation. I show devout thanks. I wish he always listens to the CD ’The
very best of Unicorn’ which is my present for him.
本研究室の同輩の江田毅晴氏には、本研究の遂行にあたって、特に本論文を
点検していただきご指導、ご助言をいただき、学生生活においても授業につい
て多大なご 協力をいただきました。 また日常生活においても、その実直な人
柄により心が癒されることはたびたびでした。 大阪中之島で行われた知的財
産権取引業育成支援研修会に一緒に出席したことはかけがえのない思い出と
なっております。 ここに心からの謝意を記します。
本研究室の同輩の兵清弘氏には、本研究の遂行にあたって、議論を通してご
指導、ご助言をいただき、学生生活においても授業について多大なご協力をい
ただきました。 また研究に行きづまったときに気分転換のために話しかけた
とき、お忙しくても嫌な顔せずに話相手になっていただいたことはたびたびで
した。 夏合宿の行きの車中では助手席で色々なお話をしていただいたことは
かけがえのない思い出となっております。 ここに心からの謝意を記します。
特許審査第一部調整課の担当官の方には、筆者が本学で学ぶにあたり様々な
事務手続きのため多大なご尽力をいただきました。 ここに心からの謝意を記
します。
特許庁審査第二部部長、首席審査長、および動力機械審査長、室長、主任を
はじめ審査官 (補) の皆様には、業務が大変な状態にも関わらず快く国内留学
に来させていただきました。 ここに心からの謝意を記します。
86
参考文献
[1] 藤井眞吾, 天笠俊之, 吉川正俊, 植村俊亮. XML データベース XRel の
実装とその評価. 電子情報通信学会第 13 回データ工学ワークショップ
(DEWS2002), 3 2002.
[2] JIS. 文書記述言語 SGML, 1992. JIS X 4151.
[3] ISO. Information Processiong - Text and Office System - Standard Generalized Markup Language (SGML), 1986. ISO 8879.
[4] R. Baeza-Yates and G. Navarro. Integrating Contents and Structure in
Text Retrieval. ACM SIGMOD Record, Vol. 25, No. 1, pp. 67–79, 1996.
[5] R. Sacks-Davis, T. Arnold-Moore, and J. Zobel. Database Systems for
Structured Documents. Proc. of the International Symposium on Advanced Database Technologies and Their Integration, pp. 272–283, 1994.
[6] V. Christophides, S. Abiteboul, S. Cluet, and M. Scholl. From Structured
Documents to Novel Query Facilities. Proc. ACM SIGMOD International
Conference on Management of Data, pp. 313–324, 1994.
[7] S. Abiteboul, S. Cluet, V. Christophides, T. Milo, G. Moerkotte, and
J. Siméon. Querying Documents in Object Databases. International
Journal of Digital Libraries, Vol. 1, No. 1, pp. 5–19, 1997.
[8] E. Horowits and R. C. Williamson. SODOS: A Software Documentation
87
Support Environment - Its Definition. IEEE Trans. on Software Engineering, Vol. SE-12, No. 8, pp. 849–859, 1986.
[9] J. Zhang. Application of OODB and SGML Techniques in Text Database:
An Electronic Dictionary System. SIGMOD Record, Vol. 24, No. 1, pp.
3–8, 1995.
[10] G. E. Blake, M. P. Consens, I. J. Davis, P. Kilpeläinen, E. Kuikka, P. A.
Larson, T. Snider, and F. W. Tompa. Application of OODB and SGML
Techniques in Text Database: An Electronic Dictionary System. SIGMOD Record, Vol. 24, No. 1, pp. 3–8, 1995.
[11] A.R. Schmidt, F.Waas, M.L. Kersten, D. Florescu, I. Manolescu, M.J.
Carey, I. Manolescu, and R. Busse. Why And How To Benchmark XML
Database. ACM SIGMOD Record, Vol. 30, No. 3, pp. 27–32, September
2001.
[12] A.R. Schmidt, F.Waas, M.L. Kersten, D. Florescu, I. Manolescu, M.J.
Carey, and R. Busse. The XML Benchmark Project. Technical report,
Centrum voor Wiskunde en Infomatica, April 2001.
[13] T. Böhme and E. Rahm. XMach-1: A Benchmark for XML Data Management. Technical report, In BTW 2001, 2001.
[14] J. Zhang. Application of OODB and SGML Techniques in Text Database:
An Electronic Dictionary System. SIGMOD Record, Vol. 24, No. 1, pp.
3–8, 3 1995.
[15] D. Florescu and D. Kossmann. A Performance Evaluation of Alternative Mapping Schemes for Storing XML Data in a Relational Database.
Technical report, Technical Report 3680, INRIA, May 1999.
[16] D. Florescu and D. Kossmann. Storing and Querying XML Data using
an RDBMS. IEEE Data Engineering Bulletin, Vol. 22, No. 3, pp. 27–34,
88
September 1999.
[17] M. Yoshikawa, T. Amagasa, T. Shimura, and S. Uemura. XRel: A PathBased Approach to Storage and Retrieval of XML Documents Using Relational Databases. ACM Transactions on Internet Technology, Vol. 1,
No. 1, pp. 110–141, 2001.
[18] D. D. Kha, M. Yoshikawa, and S. Uemura. An Efficient Storage for XML
Data using Relative Region Coordinate. Proc. of IEEE 17th International
Conference on Data Engineering, pp. 313–320, 2001.
[19] 古野正朗, 大城戸利久, 坂井勝呂, 林崎良英. ゲノムから個体へ 生命シス
テムの理解に向けて , 第 1 章. 中山書店, 6 2001.
[20] The RIKEN Genome Exploration Research Group Phase II and the FANTOM consortium. Functional annotation of a full-length mouse cDNA
collection. Nature, Vol. 409, p. 685, 2001.
89
付録
Xmark の XQuery 式
A
Xmark で用意されている XQuery による 20 の問合せを XRel での問合せ
に変換した。
A.1
標準 XRel による問合せ
20 の問合せのうちまずは標準 XRel により実行可能な 14 の問合せ1 につい
て、 XQuery 式と変換後の SQL 式を掲載する。
Query Q1: Return the name of the person with ID ‘person0’.
XQuery
FOR $b IN document("auction.xml")/site/people/person/[@id="person0"]
RETURN $b/name/text()
SQL
SELECT t2.value
FROM element e0, pth p0, attribute a1, pth p1, txt t2, pth p2
WHERE p0.pathexp LIKE ’#/site#/people#/person’
AND e0.pathid = p0.pathid
AND p1.pathexp LIKE ’#/site#/people#/person#/@id’
AND a1.pathid = p1.pathid
1
Q1, Q2, Q4, Q6–9, Q13–19 の 14 の問合せ。
90
AND a1.value LIKE ’person0’
AND e0.st = a1.st - 1
AND p2.pathexp LIKE ’#/site#/people#/person#/name’
AND t2.pathid = p2.pathid
AND e0.st < t2.st
AND e0.ed > t2.ed
ORDER BY t2.st;
Query Q2: Return the initial increases of all open auctions.
XQuery
FOR $b IN document("auction.xml")/site/open_auctions/open_auction
RETURN <increase> $b/bidder[1]/increase/text() </increase>
SQL
SELECT ’<increase>’||t1.value||’</increase>’
FROM element e0, pth p0, txt t1, pth p1
WHERE p0.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder’
AND e0.pathid = p0.pathid
AND e0.index = 1
AND p1.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder#/i
ncrease’
AND t1.pathid = p1.pathid
AND e0.st < t1.st
AND e0.ed > t1.ed
ORDER BY t1.st;
Query Q3: Return the IDs of all open auctions whose current increase is at least twice as high as the initial increase.
XQuery
FOR $b IN document("auction.xml")/site/open_auctions/open_auction
WHERE $b/bidder[0]/increase/text() * 2 <=
$b/bidder[last()]/increase/text()
91
RETURN <increase first=$b/bidder[0]/increase/text()
last=$b/bidder[last()]/increase/text()/>
この Xmark で用意されている上記 XQuery 式は誤りで、正しい XQuery 式
は次のとおりである。
FOR $b IN document("auction.xml")/site/open_auctions/open_auction
WHERE $b/bidder[1]/increase/text() * 2 <=
$b/bidder[last()]/increase/text()
RETURN <increase first=$b/bidder[0]/increase/text()
last=$b/bidder[last()]/increase/text()/>
この問合せは数字データの大小比較を行うため、数字データ XRel を用い
る必要があるが 、本研究の実験環境では標準 XRel でも問合せを行うことがで
きた。
SQL
SELECT ’<increase first="’||t2.value||’" last="’||t4.value||’" />’
FROM element e0, pth p0, element e1, pth p1, txt t2, pth p2,
element e3, pth p3, txt t4, pth p4
WHERE p0.pathexp LIKE ’#/site#/open_auctions#/open_auction’
AND e0.pathid = p0.pathid
AND p1.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder’
AND e1.pathid = p1.pathid
AND e1.index = 1
AND e0.st < e1.st
AND e0.ed > e1.ed
AND p2.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder#/inc
rease’
AND t2.pathid = p2.pathid
AND e1.st < t2.st
AND e1.ed > t2.ed
AND p3.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder’
AND e3.pathid = p3.pathid
AND e3.reindex = 1
92
AND e0.st < e3.st
AND e0.ed > e3.ed
AND p4.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder#/inc
rease’
AND t4.pathid = p4.pathid
AND e3.st < t4.st
AND e3.ed > t4.ed
AND to_number(t2.value) * 2 <= to_number(t4.value)
ORDER BY t2.st;
Query Q4: List the reserves of those open auctions where a certain
person issued a bid before another person.
XQuery
FOR $b IN document("auction.xml")/site/open_auctions/open_auction
WHERE $b/bidder/personref[id="person18829"]
BEFORE $b/bidder/personref[id="person10487"]
RETURN <history> $b/reserve/text() </history>
この Xmark で用意されている上記 XQuery 式は誤りで、正しい XQuery 式
は次のとおりである。
FOR $b IN document("auction.xml")/site/open_auctions/open_auction
WHERE $b/bidder/personref[@person="person18829"]
BEFORE $b/bidder/personref[@person="person10487"]
RETURN <history> $b/reserve/text() </history>
SQL
SELECT ’<history>’||t3.value||’</history>’
FROM element e0, pth p0, attribute a1, pth p1, attribute a2, pth p2,
txt t3, pth p3
WHERE p0.pathexp LIKE ’#/site#/open_auctions#/open_auction’
AND e0.pathid = p0.pathid
AND p1.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder#/p
ersonref#/@person’
93
AND a1.pathid = p1.pathid
AND a1.value LIKE ’person18829’
AND e0.st < a1.st
AND e0.ed > a1.ed
AND p2.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder#/p
ersonref#/@person’
AND a2.pathid = p2.pathid
AND a2.value LIKE ’person10487’
AND e0.st < a2.st
AND e0.ed > a2.ed
AND a1.st < a2.st
AND p3.pathexp LIKE ’#/site#/open_auctions#/open_auction#/reserve’
AND t3.pathid = p3.pathid
AND e0.st < t3.st
AND e0.ed > t3.ed
ORDER BY t3.st;
Query Q6: How many items are listed on all continents?
XQuery
FOR $b IN document("auction.xml")/site/regions
RETURN COUNT ($b//item)
SQL
SELECT count(*)
FROM element e0, pth p0
WHERE p0.pathexp LIKE ’#/site#/regions#%/item’
AND e0.pathid = p0.pathid;
Query Q7: How many pieces of prose are in our database?
XQuery
FOR $p IN document("auction.xml")/site
RETURN count($p//description) + count($p//annotation) + count($p//e
94
mail)
SQL
SELECT count(*)
FROM element e0, pth p0
WHERE ( p0.pathexp LIKE ’#/site#%/description’
OR p0.pathexp LIKE ’#/site#%/annotation’
OR p0.pathexp LIKE ’#/site#%/email’ )
AND e0.pathid = p0.pathid;
Query Q8: List the names of persons and the number of items they
bought. (joins person, closed auction)
XQuery
FOR
$p IN document("auction.xml")/site/people/person
LET
$a := FOR $t
IN document("auction.xml")/site/closed_auctions/closed_auction
WHERE $t/buyer/@person = $p/@id
RETURN $t
RETURN <item person=$p/name/text()> COUNT ($a) </item>
SQL
SELECT ’<item person="’||t3.value||’">’|| COUNT(a2.value)||’</item>’
FROM element e0, pth p0, attribute a1, pth p1,
attribute a2, pth p2, txt t3, pth p3
WHERE p0.pathexp LIKE ’#/site#/people#/person’
AND e0.pathid = p0.pathid
AND p1.pathexp LIKE ’#/site#/people#/person#/@id’
AND a1.pathid = p1.pathid
AND e0.st = a1.st - 1
AND p2.pathexp LIKE ’#/site#/closed_auctions#/closed_auction#/buyer
#/@person’
AND a2.pathid = p2.pathid
AND a1.value = a2.value
95
AND p3.pathexp LIKE ’#/site#/people#/person#/name’
AND t3.pathid = p3.pathid
AND e0.st < t3.st
AND e0.ed > t3.ed
GROUP BY a1.value, t3.value;
Query Q9: List the names of persons and the names of the items
they bought in Europe. (joins person, closed auction, item)
XQuery
FOR $p IN document("auction.xml")/site/people/person
LET $a := FOR $t
IN document("auction.xml")/site/closed_auctions/closed_auction
LET $n := FOR $t2
IN document("auction.xml")/site/regions/europe/item
WHERE $t/itemref/@item = $t2/@id
RETURN $t2
WHERE $p/@id = $t/buyer/@person
RETURN <item> $n/name/text() </item>
RETURN <person name=$p/name/text()> $a </person>
SQL
SELECT ’<preson name="’||t8.value||’"><item>’||t7.value||’</item></
person>’
FROM element e0, pth p0, attribute a1, pth p1, element e2, pth p2,
attribute a3, pth p3, attribute a4, pth p4, element e5, pth p5,
attribute a6, pth p6, txt t7, pth p7, txt t8, pth p8
WHERE p0.pathexp LIKE ’#/site#/people#/person’
AND e0.pathid = p0.pathid
AND p1.pathexp LIKE ’#/site#/people#/person#/@id’
AND a1.pathid = p1.pathid
AND e0.st = a1.st - 1
AND p2.pathexp LIKE ’#/site#/closed_auctions#/closed_auction’
AND e2.pathid = p2.pathid
96
AND p3.pathexp LIKE ’#/site#/closed_auctions#/closed_auction#/buyer
#/@person’
AND a3.pathid = p3.pathid
AND e2.st < a3.st
AND e2.ed > a3.ed
AND a1.value = a3.value
AND p4.pathexp LIKE ’#/site#/closed_auctions#/closed_auction#/itemr
ef#/@item’
AND a4.pathid = p4.pathid
AND e2.st < a4.st
AND e2.ed > a4.ed
AND p5.pathexp LIKE ’#/site#/regions#/europe#/item’
AND e5.pathid = p5.pathid
AND p6.pathexp LIKE ’#/site#/regions#/europe#/item#/@id’
AND a6.pathid = p6.pathid
AND e5.st = a6.st - 1
AND a4.value = a6.value
AND p7.pathexp LIKE ’#/site#/regions#/europe#/item#/name’
AND t7.pathid = p7.pathid
AND e5.st < t7.st
AND e5.ed > t7.ed
AND p8.pathexp LIKE ’#/site#/people#/person#/name’
AND t8.pathid = p8.pathid
AND e0.st < t8.st
AND e0.ed > t8.ed
ORDER BY t8.st;
Query Q13: List the names of items registered in Australia along
with their descriptions.
XQuery
FOR $i IN document("auction.xml")/site/regions/australia/item
RETURN <item name=$i/name/text()> $i/description </item>
本来この問合せに対しては、 XML 文書中の選択された description 要素の
97
部分を item 要素により囲んだ答えが返されるが 、 XRel では XML 文書の再
構築の計算量が大きいため、この問合せに対する SQL 式は XML 文書中の選
択された description 要素の部分の開始位置と終了位置を返すこととした。
SQL
SELECT t1.value, e2.st, e2.ed
FROM element e0, pth p0, txt t1, pth p1, element e2, pth p2
WHERE p0.pathexp LIKE ’#/site#/regions#/australia#/item’
AND e0.pathid = p0.pathid
AND p1.pathexp LIKE ’#/site#/regions#/australia#/item#/name’
AND t1.pathid = p1.pathid
AND e0.st < t1.st
AND e0.ed > t1.ed
AND p2.pathexp LIKE ’#/site#/regions#/australia#/item#/description’
AND e2.pathid = p2.pathid
AND e0.st < e2.st
AND e0.ed > e2.ed
ORDER BY e0.st;
Query Q14: Return the names of all items whose description contains the word ‘gold’.
XQuery
FOR $i IN document("auction.xml")/site//item
WHERE CONTAINS ($i/description,"gold")
RETURN $i/name/text()
SQL
SELECT t2.value
FROM element e0, pth p0, txt t1, pth p1, txt t2, pth p2
WHERE p0.pathexp LIKE ’#/site#%/item’
AND e0.pathid = p0.pathid
AND (p1.pathexp LIKE ’#/site#%/item#/description’
98
OR p1.pathexp LIKE ’#/site#%/item#/description#/%’)
AND t1.pathid = p1.pathid
AND t1.value LIKE ’%gold%’
AND e0.st < t1.st
AND e0.ed > t1.ed
AND p2.pathexp LIKE ’#/site#%/item#/name’
AND t2.pathid = p2.pathid
AND e0.st < t2.st
AND e0.ed > t2.ed
ORDER BY e0.st;
Query Q15: Print the keywords in emphasis in annotations of closed
auctions.
XQuery
FOR $a IN document("auction.xml")/site/closed_auctions/closed_aucti
on/annotation/description/parlist/listitem/parlist/listitem/text/emph
/keyword/text()
RETURN <text> $a </text>
SQL
SELECT ’<text>’||t0.value||’</text>’
FROM txt t0, pth p0
WHERE p0.pathexp LIKE ’#/site#/closed_auctions#/closed_auction#/ann
otation#/description#/parlist#/listitem#/parlist#/listitem#/text#/bol
d’
AND t0.pathid = p0.pathid
ORDER BY t0.st;
Query Q16: Return the IDs of those auctions that have one or more
keywords in emphasis.
XQuery
99
FOR $a IN document("auction.xml")/site/closed_auctions/closed_auction
WHERE NOT EMPTY ($a/annotation/description/parlist/listitem/text/emph
/keyword/text())
RETURN <person id=$a/seller/@person />
SQL
SELECT ’<person id="’||a2.value||’" />’
FROM element e0, pth p0, txt t1, pth p1, attribute a2, pth p2
WHERE p0.pathexp LIKE ’#/site#/closed_auctions#/closed_auction’
AND e0.pathid = p0.pathid
AND p1.pathexp LIKE ’#/site#/closed_auctions#/closed_auction#/annotat
ion#/description#/parlist#/listitem#/parlist#/listitem#/text#/emph#/key
word’
AND t1.pathid = p1.pathid
AND e0.st < t1.st
AND e0.ed > t1.ed
AND p2.pathexp LIKE ’#/site#/closed_auctions#/closed_auction#/seller#
/@person’
AND a2.pathid = p2.pathid
AND e0.st < a2.st
AND e0.ed > a2.ed
ORDER BY e0.st;
Query Q17: Which persons don’t have a homepage?
XQuery
FOR $p IN document("auction.xml")/site/people/person
WHERE EMPTY($p/homepage/text())
RETURN <person name=$p/name/text()/>
SQL
SELECT ’<person name="’||t1.value||’" />’
FROM element e0, pth p0, txt t1, pth p1
WHERE p0.pathexp LIKE ’#/site#/people#/person’
100
AND e0.pathid = p0.pathid
AND NOT EXISTS (
SELECT *
FROM txt t2, pth p2
WHERE p2.pathexp LIKE ’#/site#/people#/person#/homepage’
AND t2.pathid = p2.pathid
AND e0.st < t2.st
AND e0.ed > t2.ed
)
AND p1.pathexp LIKE ’#/site#/people#/person#/name’
AND t1.pathid = p1.pathid
AND e0.st < t1.st
AND e0.ed > t1.ed
ORDER BY e0.st;
Query Q18: Convert the currency of the reserve of all open auctions
to another currency.
XQuery
FUNCTION CONVERT ($v)
{
RETURN 2.20371 * $v -- convert Dfl to Euro
}
FOR $i IN document("auction.xml")/site/open_auctions/open_auction/
RETURN CONVERT($i/reserve/text())
SQL
SELECT t0.value*2.20371
FROM txt t0, pth p0
WHERE p0.pathexp LIKE ’#/site#/open_auctions#/open_auction#/reserve’
AND t0.pathid = p0.pathid
ORDER BY t0.st;
101
Query Q19: Give an alphabetically ordered list of all items along
with their location.
XQuery
FOR $b
LET $k
RETURN
SORTBY
IN document("auction.xml")/site/regions//item
:= $b/name/text()
<item name=$k> $b/location/text() </item>
(.)
SQL
SELECT ’<item name="’||t1.value||’">’||t2.value||’</item>’
FROM element e0, pth p0, txt t1, pth p1, txt t2, pth p2
WHERE p0.pathexp LIKE ’#/site#/regions#%/item’
AND e0.pathid = p0.pathid
AND p1.pathexp LIKE ’#/site#/regions#%/item#/name’
AND t1.pathid = p1.pathid
AND e0.st < t1.st
AND e0.ed > t1.ed
AND p2.pathexp LIKE ’#/site#/regions#%/item#/location’
AND t2.pathid = p2.pathid
AND e0.st < t2.st
AND e0.ed > t2.ed
ORDER BY t2.value;
A.2
数字データ XRel による問合せ
次に、 20 の問合せのうち数字データ XRel2 により実行可能な 5 の問合せ
3
について、 XQuery 式と変換後の SQL 式を掲載する。
2
ここでは二種類の数字データ XRel のうち、別表数字データ XRel を用いる。
3
Q3, Q5, Q11, Q12 の 4 の問合せ。
102
Query Q3: Return the IDs of all open auctions whose current increase is at least twice as high as the initial increase.
XQuery
FOR $b IN document("auction.xml")/site/open_auctions/open_auction
WHERE $b/bidder[1]/increase/text() * 2 <=
$b/bidder[last()]/increase/text()
RETURN <increase first=$b/bidder[0]/increase/text()
last=$b/bidder[last()]/increase/text()/>
この問合せは本研究での実験環境では標準 XRel でも問合せを行うことがで
きた。
SQL
SELECT ’<increase first="’||n2.value||’" last="’||n4.value||’" />’
FROM element e0, pth p0, element e1, pth p1, number n2, pth p2,
element e3, pth p3, number n4, pth p4
WHERE p0.pathexp LIKE ’#/site#/open_auctions#/open_auction’
AND e0.pathid = p0.pathid
AND p1.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder’
AND e1.pathid = p1.pathid
AND e1.index = 1
AND e0.st < e1.st
AND e0.ed > e1.ed
AND p2.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder#/inc
rease’
AND n2.pathid = p2.pathid
AND e1.st < n2.st
AND e1.ed > n2.ed
AND p3.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder’
AND e3.pathid = p3.pathid
AND e3.reindex = 1
AND e0.st < e3.st
AND e0.ed > e3.ed
AND p4.pathexp LIKE ’#/site#/open_auctions#/open_auction#/bidder#/inc
103
rease’
AND n4.pathid = p4.pathid
AND e3.st < n4.st
AND e3.ed > n4.ed
AND n2.value * 2 <= n4.value
ORDER BY n2.st;
Query Q5: How many sold items cost more than 40?
XQuery
COUNT (FOR $i IN document("auction.xml")/site/closed_auctions/closed_
auction
WHERE $i/price/text() >= 40
RETURN $i/price)
SQL
SELECT COUNT(*)
FROM number n0, pth p0
WHERE p0.pathexp LIKE ’#/site#/close_auctions#/close_auction#/price’
AND n0.pathid = p0.pathid
AND n0.value >= 40;
Query Q11: For each person, list the number of items currently on
sale whose price does not exceed 0.02% of the person’s income.
XQuery
FOR $p IN document("auction.xml")/site/people/person
LET $l := FOR $i
IN document("auction.xml")/site/open_auctions/open_auction/initial
WHERE $p/profile/@income > (5000 * $i/text())
RETURN $i
RETURN <items name=$p/name/text()> COUNT ($l) </items>
104
SQL
SELECT ’<items name="’||t3.value||’">’||COUNT(a1.value)||’</items>’
FROM element e0, pth p0, attr_number a1, pth p1, number n2, pth p2,
txt t3, pth p3
WHERE p0.pathexp LIKE ’#/site#/people#/person’
AND e0.pathid = p0.pathid
AND p1.pathexp LIKE ’#/site#/people#/person#/profile#/@income’
AND a1.pathid = p1.pathid
AND e0.st = a1.st - 1
AND p2.pathid LIKE ’#/site#/open_auctions#/open_auction#/initial’
AND n2.pathid = p2.pathid
AND a1.value > n2.value * 5000
AND p3.pathexp LIKE ’#/site#/people#/person#/name’
AND t3.pathid = p3.pathid
AND e0.st < t3.st
AND e0.ed > t3.ed
GROUP BY t3.value
ORDER BY e0.st;
Query Q12: For each person with an income of more than 50000, list
the number of items currently on sale whose price does not exceed
0.02% of the person’s income.
XQuery
FOR $p IN document("auction.xml")/site/people/person
LET $l := FOR $i
IN document("auction.xml")/site/open_auctions/open_auction/initial
WHERE $p/profile/@income > (5000 * $i/text())
RETURN $i
WHERE $p/profile/@income > 50000
RETURN <items name=$p/name/text()> COUNT ($l) </items>
SQL
SELECT ’<items name="’||t3.value||’">’||COUNT(a1.value)||’</items>’
105
FROM element e0, pth p0, attr_number a1, pth p1, number n2, pth p2, t
xt t3, pth p3
WHERE p0.pathexp LIKE ’#/site#/people#/person’
AND e0.pathid = p0.pathid
AND p1.pathexp LIKE ’#/site#/people#/person#/profile#/@income’
AND a1.pathid = p1.pathid
AND e0.st = a1.st - 1
AND a1.value > 50000
AND p2.pathid LIKE ’#/site#/open_auctions#/open_auction#/initial’
AND n2.pathid = p2.pathid
AND a1.value > n2.value * 5000
AND p3.pathexp LIKE ’#/site#/people#/person#/name’
AND t3.pathid = p3.pathid
AND e0.st < t3.st
AND e0.ed > t3.ed
GROUP BY t3.value;
XQEngine の問合せに変形した Xmark の XQuery
B
式
Xmark で用意されている XQuery による 20 の問合せのうち 8 つを XQEngine
での問合せに変形した。
B.1
XPath 式による問合せ
20 の問合せのうち、まずは XPath により実行可能な 5 の問合せ 4 につい
て、 Xmark の XQuery 式と変形後の XPath 式を掲載する。
Query Q1: Return the name of the person with ID ‘person0’.
Xmark
4
Q1, Q2, Q6, Q16, Q18 の 5 の問合せ。
106
FOR $b IN document("auction.xml")/site/people/person/[@id="person0"]
RETURN $b/name/text()
元の XQuery 式は name 要素を返す式であるが 、 XQEngine は text() に対
応していないため XPath による準じた問合せに変形した。
XQEngine
/site/people/person[@id="person0"]/name
Query Q2: Return the initial increases of all open auctions.
Xmark
FOR $b IN document("auction.xml")/site/open_auctions/open_auction
RETURN <increase> $b/bidder[1]/increase/text() </increase>
XQEngine
/site/open_auctions/open_auction/bidder[1]/increase
Query Q6: How many items are listed on all continents?
Xmark
FOR $b IN document("auction.xml")/site/regions
RETURN COUNT ($b//item)
元の XQuery 式は条件に該当する item 要素を数える式であるが、XQEngine
は COUNT に対応していないため、単に item 要素を表示する準じた問合せ
に変形した。
XQEngine
/site/regions//item
107
Query Q16: Return the IDs of those auctions that have one or more
keywords in emphasis.
Xmark
FOR $a IN document("auction.xml")/site/closed_auctions/closed_auction
WHERE NOT EMPTY ($a/annotation/description/parlist/listitem/text/emph
/keyword/text())
RETURN <person id=$a/seller/@person />
元の XQuery 式は NOT EMPTY, text() および属性を用いた式であるが 、
XQEngine はこれらに対応していないため、準じた問合せに変形した。
XQEngine
/site/closed_auctions/closed_auction[annotation/description/parlist/l
istitem/text/emph/keyword]/seller/@person
Query Q18: Convert the currency of the reserve of all open auctions
to another currency.
Xmark
FUNCTION CONVERT ($v)
{
RETURN 2.20371 * $v -- convert Dfl to Euro
}
FOR $i IN document("auction.xml")/site/open_auctions/open_auction/
RETURN CONVERT($i/reserve/text())
元の XQuery 式は利用者定義関数を用いた式であるが 、 XQEngine は利用
者定義関数に対応していないため、準じた問合せに変形した。 この問合せは
利用者定義関数を用いる能力を測定するためのものであるから、この問合せを
行うことは参考程度の意味しかない。
108
XQEngine
/site/open_auctions/open_auction/reserve
B.2
XQuery 式による問合せ
次に XQuery により実行可能な 3 の問合せ5 について、 Xmark の XQuery
式と変形後の XQuery 式を掲載する。
Query Q13: List the names of items registered in Australia along
with their descriptions.
Xmark
FOR $i IN document("auction.xml")/site/regions/australia/item
RETURN <item name=$i/name/text()> $i/description </item>
元の XQuery 式は name の文字列節点と description 要素節点を所定の形式
で表示する式であるが 、 XQEngine は返り値に二つ以上の節点を持つことが
できないので、 name の文字列節点を WHERE の条件とする準じた問合せに
変形した。
XQEngine
FOR $i IN /site/regions/australia/item
WHERE $i/name
RETURN <item>$i/description</item>
Query Q15: Print the keywords in emphasis in annotations of closed
auctions.
Xmark
5
Q13, Q15, Q19 の 3 の問合せ。
109
FOR $a IN document("auction.xml")/site/closed_auctions/closed_auction
/annotation/description/parlist/listitem/parlist/listitem/text/emph/key
word/text()
RETURN <text> $a </text>
元の XQuery 式は keyword の文字列を text 標識で囲んだ節点を返す式であ
るが 、 XQEngine は text() に対応していないため、準じた問合せに変形した。
XQEngine
FOR $a IN /site/closed_auctions/closed_auction/annotation/description
/parlist/listitem/parlist/listitem/text/emph/keyword
RETURN <text>$a</text>
Query Q19: Give an alphabetically ordered list of all items along
with their location.
Xmark
FOR $b
LET $k
RETURN
SORTBY
IN document("auction.xml")/site/regions//item
:= $b/name/text()
<item name=$k> $b/location/text() </item>
(.)
元の XQuery 式は整列 (SORT) および text() を用いた式であるが、XQEngine
はこれらに対応していないため、準じた問合せに変形した。 この問合せは整
列の能力を測定するためのものであるから、この問合せを行うことは参考程度
の意味しかない。
XQEngine
FOR $b IN /site/regions//item
LET $k := $b/name
RETURN <item> $b/location </item>
110