情報学科CSコース情報システム（３年後期）
講義ノート
ー第6回ー
ＸＳＬＴ, Xlink/Xpointer, インデックス
田中克己
角谷和俊
（参考図書)S.Abiteboul, P. Buneman, and D. Suciu,
“Data on the Web – From Relations to Semistructured Data and XML –”, Morgan Kaufmann Publishers (2000).
2
ＸＭＬ文書変換
ＸＭＬ文書の変換
アプリケーション間のデータ交換 文書構造と表現の分離
ＸＳＬ（eXtensible Style Language)
構造変換指定 表示(印刷)用フォーマット指定
ＸＳＬＴ（ＸＳＬ Transformations)
ツリー構造の変換 ＸＰａｔｈによるパス式指定XSLT規格へ
XSLT ソース木 結果木 構造変換 (ツリー変換) フォーマッティング3
ＸＳＬTスタイルシート
XSLTスタイルシート =
テンプレート規則 ...テンプレート規則
テンプレート規則 = パターン + テンプレート
<xsl:template match = “/bib/*/title”>
<result> <xsl:value-of select = “.” /> </result>
</xsl:template>
<
xsl:template
match
= “/bib/*/title”>
<
result
> <
xsl:value-of
select
= “.” /> </
result
>
</
xsl:template
>
4
XSLT処理（１）
<xsl:template match=“/”> <html><xsl:apply-templates/></html> </xsl:template> <xsl:template match=“reference”> <h1>xsl:value-of select=“@kind”/></h1> <xsl:apply-templates/> </xsl:template> <xsl:template match=“magazine”> <p>xsl:value-of select=“.”/></p> </xsl:template> <xsl:template match=“/”> <html><xsl:apply-templates/></html> </xsl:template><xsl:template match=“reference”>
<h1>xsl:value-of select=“@kind”/></h1> <xsl:apply-templates/>
</xsl:template>
<xsl:template match=“magazine”> <p>xsl:value-of select=“.”/></p> </xsl:template> <reference kind=“journal”> <magazine>CACM</magazine> <magazine>IEEE Computer</magazine> </reference> <reference kind=“journal”> <magazine>CACM</magazine> <magazine>IEEE Computer</magazine> </reference> ← reference要素が処理対象 ← kindの値を文字列で取得 ← 2つのmagazine要素が処理対象 ← 文字列を取得 ← “<xsl:apply-templates/>” が無いことに注意 <html> <h1>journal</h1> <p>CACM</p> <p>IEEE Computer</p> </html> <html> <h1>journal</h1> <p>CACM</p> <p>IEEE Computer</p> </html> 再帰呼び出し
5
XSLT処理（２）
<xsl:template>
<xsl:apply-templates/>
</xsl:template>
<xsl:template match=“a”>
<A><xsl:apply-templates/></A>
</xsl:template>
<xsl:template match=“b”>
<B><xsl:apply-templates/></B>
</xsl:template>
<xsl:template match=“c”>
<C><xsl:value-of/></C>
</xsl:template>
<xsl:template>
<xsl:apply-templates/>
</xsl:template>
<xsl:template
match
=“a”>
<A><xsl:apply-templates/></A>
</xsl:template>
<xsl:template
match
=“b”>
<B><xsl:apply-templates/></B>
</xsl:template>
<xsl:template
match
=“c”>
<C><xsl:value-of/></C>
</xsl:template>
< << <aaaa> > > > < << <eeee>>>> < << <bbbb>>>> < << <cccc> 1 </> 1 </> 1 </> 1 </cccc>>>> < << <cccc> 2 </> 2 </> 2 </> 2 </cccc>>>> </ </ </ </bbbb>>>> < << <aaaa> > > > < << <cccc> 3 </> 3 </> 3 </> 3 </cccc>>>> </ </ </ </aaaa>>>> </ </ </ </eeee>>>> < << <cccc> 4 </> 4 </> 4 </> 4 </cccc>>>> </ </ </ </aaaa>>>> < << <AAAA> > > > < << <BBBB> > > > < << <CCCC> 1 </> 1 </> 1 </> 1 </CCCC>>>> < << <CCCC> 2 </> 2 </> 2 </> 2 </CCCC>>>> </ </</ </BBBB>>>> < << <AAAA>>>> < << <CCCC> 3 </> 3 </> 3 </> 3 </CCCC> > > > </ </</ </AAAA>>>> < << <CCCC> 4 </> 4 </> 4 </> 4 </CCCC>>>> </ </ </ </AAAA>>>>6
XMLのリンクの概念
ＨＴＭＬのリンク
リソースをＵＲＩで指定(<A>
…</A>
２つのリソースのうち一方で記述 （片方向）
リンクの効果は記述不可能
機能拡張
XML文書の要素や文字列もリソースとして指定
リンクの処理内容を指定
タイミングの指定(自動，ユーザ指定)
（ （（ （参考参考参考参考））））XML Linking Language (XLink) Version 1.0 W3C Recommendation 27 June 2001
7
拡張されたリンク機能
拡張機能
任意の場所指定
双方向リンク
1対多
リンク記述とリソースの分離
<A name = cat>cat</A>
……..
<title>animal</title>
……..
<p>animal</p>
8
トラバーサルとアーク
トラバーサル
リンクを使用・たどる動作（一対のリソース間）
出発点：始点リソース，到達点：終点リソース
アーク
トラバーサルの方向や、その時のアプリケー
ションの挙動
種類
外向き
(outbound)
内向き
(inbound)
第三者
(thirdparty)
9
拡張リンク
タイプ属性とXＬink要素
simple (単純型要素)
extended (拡張型要素)
resource (リソース型要素)
ローカルリソースを記述
ラベル属性
locator (ロケータ型要素)
リモートリソースを記述
ラベル属性
arc (アーク型要素)
リンク関係を記述
10
ＸＭＬのポインタ
XPointer (XML Pointer Language)
XLinkなどでXMLデータの一部を参照(アドレス）するための言語
（例）
href=“www.a.b.c/document.xml
#xpointerExpr
”
ロケーション
ノード
ルート，要素，属性，テキスト，処理命令，コメント
,
名前空間を指す
ポイント
(point)
ノードとノードの間，文字と文字の間を指す
範囲
(range)
ポイントとポイントの間にあるＸＭＬ構造を指す
11
ポイントと範囲
ポイント指定
フルフォーム
(full form)
#xpointer(id(“3652”)) ベアネーム
(bare name)
#3652 ：指し示す要素のＩＤ型属性の値 子供配列
(child sequence)
#xpointer( /1/3/2/5) ：木構造を親から子へたどる時の要素の位置 #xpointer( /bib/book[3]) 範囲指定
相当範囲（
coverage range)を指定
#xpointer(range(/doc/items)) #xpointer(//month/text()/range-to(end-point(//day)))12
ＸＭＬデータベースシステム
デーベーススキーマへの写像法
構造写像アプローチ
モデル写像アプローチ
関係データベースを用いたモデル写像アプローチ
ＸＭＬ文書をそのまま格納する方法
（ネイティブＸＭＬデータベース）
13
インデックス
半構造/XMLデータベースインデックス
XSet
Region Algebras
DataGuides
T-indexes
対象データ
木構造データ (XML)
グラフデータ
検索質問
制限つき正規表現 (XPath)
正規表現
14
XSet: a simple index for XML
各ノードはハッシュテーブル
各エントリはデータノードへのポインタのリスト(非表示)
1. part.name 2. part.supplier.name 3. part.*.subpart.name 4. *.supplier.name 問題あり16
Region Algebras
構造化文書（
XMLなど）のための代数
データは順序木
制限された正規表現によるパスだけが
region
algebraの演算子に変換可能
制限 制限制限 制限されたされたされた正規表現された正規表現正規表現：正規表現：：： r1.r2.….ri ： 各riは定数ラベルかKleene閉包（_*）data: [c1c2c3 …]
region:テキストの区間
(x,y) = [cx,cx+1, … cy] (例) <section> … </section>region set: regionの集合
すべての<section> regions (入れ子構造を許す)
region algebra: region set上の代数
s1 op s2
17
Region Algebraの演算子
s1 intersect s2 = {r | r
∈ s1, r ∈s2}
s1 included s2 = {r | r
∈s1, ∃r’ ∈ s2, r ⊆ r’}
s1 including s2 = {r | r
∈ s1, ∃r’ ∈ s2, r ⊇ r’}
s1 parent s2 = {r | r
∈ s1, ∃r’∈ s2, r is a parent of r’}
s1 child s2 = {r | r
∈ s1, ∃r’ ∈ s2, r is child of r’}
例:<subpart> included <part> = { s1, s2, s3, s5} <part> including <subpart> = {p2, p3}
x≦≦≦≦x’≦≦≦≦y’≦≦≦≦y が成立 → rはr’の祖先、r⊇r x≦≦≦≦y≦≦≦≦x’≦≦≦≦y’ が成立 → rはr’よりも左の子
18
Region Algebraの演算とパス表現
演算
(例) s1 included s2
s1 = {(x1,x1'), (x2,x2'), …} s2 = {(y1,y1'), (y2,y2'), …} (互いに素なregionを含む) アルゴリズム: if xi < yj then i := i + 1 if xi' > yj' then j := j + 1otherwise: print (xi,xi'), do i := i + 1
パス表現
part.name name child (part child root)
part.supplier.name name child (supplier child (part child root)) *.supplier.name name child supplier
part.*.subpart.name name child (subpart included (part child root))
_*.subpart:(name: X, _*.supplier.address:“Philadelphia”)
name child (subpart includes (supplier parent
19
ＤａｔａＧｕｉｄｅs
半構造/XMLデータベースインスタンスＤＢとグラフＧ
DBのすべてのパスがＧに存在（Complete Coverage)
ＧのすべてのパスがＤＢに存在（Accurate Coverage)
Ｇのすべてのパスが一意的（: ＤＦＡ）
共通のノードを一つに集約してOEMを要約 DB G DataGuide20
Ｓｔｒｏｎｇ DataGuides
ＧがDBのStrong DataGuidesになる条件：
≡
Gと
≡
DBが同関係
strong DataGuide person.project !≡DB dept.project person.project !≡G2 dept.project21
DataGuidesの生成
DataGuide G の生成
Nodes(G)={{root}}
Edges(G)=
∅
while changes do
choose s in Nodes(G), a in Labels
add s
’={y|x in s, (x -a->y) in Edges(DB)} to
Nodes(G)
add (x -a->y) to Edges(G)
22
1-Indexes
データベース: DB = (V,E,Roots)
質問: regular path expressions q(DB)
∀u∈V. Lu ⇔ {a1…an | v0 → …→ vn ∈DB, v0∈Root, vn=u}
∀u,v∈V. u ≡ v ⇔ Lu = Lv （ルートノードからのパスとして同一）
∀u∈V. [u] = {v | u ≡ v} （uを含む同クラス）
a1 an
Nodes(I) = { [u] | u in nodes(DB) }
Edges(I) = { s → s’ | ∃u ∈ s, ∃u’ ∈ s’, (u →au’) ∈ Edges(DB)}
