VLDB2000報告その1 WWW，XMLとDB

VLDB2000報告
その１：WWW，XML関連
（完成版）
DBWeb2000 (SigmodJ第16回大会資料）
2000年12月6日
大森匡＠SIGMOD日本支部書記
（電気通信大学大学院
情報システム学研究科 www.is.uec.ac.jp）
VLDB2000報告とは？
• SIGMOD日本支部の活動の１つ – 最新の
データベース研究動向を会員に報告する。- ACM SIGMOD会議、 VLDB, ICDE, etc.
• 主要な目的 – DB systemsに関する
問題意識の共有 –大学と企業、日本と海外。
• VLDB2000 -- エジプト。(00Egypt, 01Italy)
--- 論文53件(投稿349),デモ16件、
パネル4つ, 企業15件、チュートリアル5つ。
会議場
論文集のアクセス
• VLDB2000の概要、プログラム
-- www.vldb.org(VLDBの公式サイト）
• 論文の概要
-- www.informatik.uni-trier.de/ley/db
(DBLP)からPDFのロード可能。(vldbから
はfree access).
-- 論文集： Proc.26th Int.Conf.VLDB2000.
Morgan Kaufmann Pub.
-- メモ、ppt  www.sigmodj.is.uec.ac.jp
(SigmodJ)
VLDB2000の全体像
• 方向１ -- 新しい情報システムにおけるイン
フラストラクチャとしてのDB的な要素技術
-- XML放送, Web分析、crawlerの
コンテンツ管理、高次元データ
• 方向２ -- DBエンジンの多様化。
-- risc db, xml管理用のdb、 DWH用の
INDEX、ICカードdb。
WWW,XMLとDB関連
1. Rethinking DB system architecture:
towards a self-tuning RISC-style db systems.
(Microsoft)
2. Efficient filtering of XML doc for selective
dissemination of info. (Maryland U., UCB)
3. Efficiently publishing relational data as
XML doc. (IBM Almaden)
4. Approximating aggregating queries about
Web pages via random walks. (UCB)
1. Rethinking DB Syst. Arch: towards a
self-tuning RISC-style DB systems
(Microsoft, vision paper)
• 現在のDBシステムは複雑すぎる。SQLは
複雑な句の集まり。最適化も性能予測も困
難。
• Gain/Pain Ratio (GPR)が小さい。特に、性
能の予測可能性（Performance
Predictability)が低い。
• 拡大するIT応用に対応できない＝現在あ
るDBシステムはもうITには使えない、かも。
RISC的なDBシステムへ
• DBシステムを、単純なコンポーネントの多層
構造へ。各コンポーネントは単純なAPIでつなぎ、
APIあたりの性能予測性、性能調整能力を明確化。
• 第１層＝単一テーブルのselect, B+木インデク
ス、レコード更新、トランザクションのみ。
SQLなし。（ただの永続データストレージ）
• 第２層＝SPJ問い合わせと集約演算、ストリー
ム並列まで。（OLAP,DSS)
• 第３層＝フルSQL。最適化の質よりも性能予測性
を重視。  OLE-DB APIではそうなるだろう。
• 性能自動調整＝各層の調整は簡単。層間の
調整は数学モデルでOK.
• OLTP,OLAP,メタデータ管理、Eメール処理、
市場取引型データサーバ、ニュースオンデマ
ンドサーバ、などでまずテストすべき。
• オープンなRISC型データ管理コンポーネント
の研究。APIの公開。
 既存のDBサーバからIT分野向けのDB的
機能サーバへ。
2. Efficient filtering of XML doc for selective
dissemination of info. (Maryland U.)
• 目的：10^3-5のユーザプロファイルにXML
データを選択的に放送したい。
データ源
XML文書
XML変換
10^5のユーザのうち
対応する人だけに
XMLデータを放送。
XML用の高速フィルタエンジン
（従来：キーワード、受信側フィルタ）
提案方法
Xpathをユーザプロファイルとする。
例： /catalog/product//msrp
//product[price/msrp<300]/name
１０＾５程度のXpathでインデクスを作る。
Query index
Xml doc.
照合した
プロファイル
Xml parser
へ
Ｘｍｌ文書を
送る。
XMLデータのparsing events
An XML document
<?xml version=1.0>
<doc>
<para>
Hello, world!
</para>
</doc>
Parser’s API events
Start document
Start element: doc
Start element: para
Character: Hello, world!
End element: para
End element: doc
End document
解き方： Xpath式を有限状態オートマトン
と見なして照合する。
Q1=/a/b//c
入力記号はXML文書のparsing event.
a
INIT
b
NULL
c
FINAL
Xpathにおけるタグつき選択述語
実装：各Xpath式のFSAを「経路ノード」で表現。
Q1=/a/b//c
Q1-1に付くフィルタ条件
Q1-1 [Q1,1,0,1]
Q1-2 [Q1,2,1,0]
Q1-3 [Q1,3,-1,-1]
経路ノードが照合
されている文書データ
のレベル（変数）
文書中のレベルで数えた、経路式の
直前ノードからの相対距離
経路式の中のノードの位置
実装：
Query Index
XMLのタグ CL： Qのうち現在照合中のノードのリスト
CL
Q1-1 Q3-1 Q5-1
a
WL
b
CL
c
WL Q1-2
d
e
Q2-1 Q4-1
照合手順：文書Xについて、適合する
経路ノードをWLからCLに移動しながら
照合を続ける。（照合後のノードはWL
へ戻す。）
２のまとめ
• Skew大の時、Prefilterなしでlist balance方
式の効果大。
フィルタ時間（msec)
18000
16000
14000
basic
12000
prefilter+basic
10000
8000
list balance
6000
prefilter+listbal
ance
4000
2000
プロファイル数（K)
0
10
50
80
100
ここまでのまとめ
• １．RISC-style DB engine
– エンジンの多層化。
• 2. XMLのデータ放送、フィルタリング
– DB的なインデクス、負荷分散が必須。
＝現状は独自に開発。
 IT応用特有の新インデクスの支援
がDB側に必要。
3. Efficiently Publishing Relational data
as XML documents (IBM)
• 対象： XMLはビジネスデータの交換プロ
トコル。データの管理はRDB。
• 課題：関係データをXML文書に変換する
時、ほとんどすべての処理をSQL文１つで
書き、SQLサーバの中でやってしまう。
• 今まで：XML文書の各フィールドからSQL
文を呼び出す。＝入れ子ループ JOIN。
<customer id=..>
XML文書の例
<name> J.Doe </name>
<accounts>
<account id=“a1”> 189</account>
<account id=….> 382</account>
</accounts>
<porders>
<porder id=..> //1st purchase order
<date> …</date>
<items>
<item id=..> shoes</item>
<item …> … </item>
</items> <payments> …</payments>
</porder>
…
• 目的：関係データをXML文書に変換する
時、ほとんどすべての処理をSQL文１つで
書き、SQLサーバの中でやってしまう。
• 方法：
SQLへの構成子の追加と
SQL文実行プランの最適化戦略。
提案方法
１．関係データからXMLの指定タグ付きの
テキストをつくる構成子、
２．XMLの同一タグのテキストデータ群を
連接する構成子XMLAGG
を入れ子SQL文で使う。
 SQL文１つでXML文書をエンジン内で生
成。（＋実行プランの最適化が重要）。
XML文書の例
<customer id=..>
<name> J.Doe </name>
<accounts>
<account id=“a1”> 189</account>
<account id=….> 382</account>
</accounts>
<porders>
<porder id=..> //1st purchase order
<date> …</date>
<items>
<item id=..> shoes</item>
<item …> … </item>
</items> <payments> …</payments>
</porder>
…
XML文書を作るSQL文
Select cust.name,
CUST( cust.id, cust.name,
(Select XMLAGG(ACCT(acct.id, acct.acctnum))
from Account acct Where acct.custId=cust.id),
(select ….from Porders where …)
)
From Customer cust;
XMLデータをスカラで返す関数と見なす。
関係表
Customer(id, name).
Account(id, custId, acctnum).
PurchOrder(id, custid, acctId, date).
Item(id, poId, desc).
Payment(id, poId, desc).
関係データからタグつきXMLを作る構成子
Define XML Constructor CUST(custId, custName,
acctList:xml, porderList:xml) AS {
<customer id=$custId>
<name> $custName</name>
<accounts>$acctList</accounts>
<porders> $porderList</porders>
</customer> }
SQLエンジン内部の実行プラン
•
•
XMLのタグづけをいつ行うか -- early or late?
XMLデータの入れ子構造化をいつ行うか
-- early or late?
＋エンジンの中・外のどこでどの処理を行う
か。
1. Early tagging, early structuring
- stored procedure – エンジンの外でxml文書から
毎回入れ子ループjoin.
- correlated CLOB – XMLデータをCLOBにして
エンジンの中で入れ子ループjoin.
- decorrelated CLOB – outerjoin
Early tagging, early structuring (CLOB)
CUST()
CLOBの処理が重い
Sort, copy
Join: cust.id=cust.id
Group by cust.id
XMLAGG(ACCT())
Group by cust.id
XMLAGG(PORDER)
右外結合
Acct.custID=cust.id
左外結合
Cust.id=porder.custid
Account
Customer
PurchaseOrder
Late tagging, late structuring
1. コンテンツの生成 + 2. Tag, structuring.
• OuterUnion法
外部和
(custid, X, Y, W, Z, ..)
(custid, X, W, Z, ..)
(custid, X,Y..)
右外結合
右外結合
Item
左外結合
左外結合
payment
(custid,…)
Account
Customer
PurchaseOrder
1. Late tagging, Late structuring
= OuterUnion法 +エンジン内・外の
ハッシュ表による構造化とタグづけ。
2. Late tagging, early structuring
= OuterUnion法の出力を,XML文書の経路
順(parent id, child id, …)をキーにしてソー
ト。
 (CustId, AcctId, POId, ItemId, PaymentId)
をキーにしてエンジンの中でソート。
* null < non-null.
* エンジンの外でソート順にタグづけ。
（一定メモリの場合）。
３のまとめ（１）
結果：DB2、約32万件からXML文書を生成：
30sec.（エンジン外、stored proc.法)
から
6sec.(エンジン内、OuterUnion法)
へ削減。
３のまとめ（２）
• 感想： XMLコンテンツ管理用に
-- SQL言語を拡張し、
-- 関係代数演算を追加(OuterUnion)して、
既存の問い合わせ最適化機構とDBエンジン
の並列処理機構を利用した。
Risc dbms
SQLの拡張
独自データ管理
4. Approximating aggregate queries about
web pages via random walks (UCB)
• WWWネットワーク(有向グラフ)のrandom
walkによるサンプリング技術
強連結
終端
開始
その他
Webグラフ
• 問題の設定：
WWWは有向グラフ
 収集が大変でしかも不完全。
Q:何％のページが.comドメインか？
Q:サーチエンジンXはWebグラフの何％をカ
バーしているか？
Q：Webページの大きさ、変更間隔、コンテン
ツの分布は？
 random walk samplingによって、短時間
の収集データから高精度に答えたい。
• 予備知識（省略）
regularな無向グラフ上のrandom walkによ
り到達可能なノードの集合は、一様分布確
率に近いサンプル集合になる。
 Random walk on regular, undirected graph
ならサンプル上で述語評価をすればよい。
(regular graph=ノードあたりの辺数が同じ）。
• WWWグラフ！＝ regular, undirected
graph。 Webグラフをrandom walk用に
変形する。
• Random walkが一様分布のサンプル集合
に近づくwalking回数は？
強連結
終端
開始
その他
Webグラフ
• WebグラフWの変形（省略）
1. リンクの後戻りを許す。
2. リンク数を自己ループを追加して等しく
する。 (d: 元の辺の最大数として重み
1-(I+O)/dの幾何分布で自己ループを追
加する。）
 Walking１回あたり12K ステップの外部
WWWアクセスでOK.
• 41K steps (in 3 walks)
FAST 39.97%, Altavista 21.13%, 重複
21.13%, image72%.
* ドメイン別分布 (146K steps, 21 walks).
.com 49％ (54), .edu 8.3％ (6.7),
.org
6.5％ (4.3), …
(数字は％。括弧内はinktomiによる同時期
の1 billion page indexの分析結果）
-- 本実験の分析時間はPC１台で２日以下。
-- mixing timeの解析、高次ノードへのバイ
アス解消が未解決。
他：WWW, XML関連
• The evolution of web and implication for an
incremental crawler. (Stanford U.)
-- crawlerのページ更新を定常的にページの
更新頻度に応じて行うincremental crawlerの解
析。バッチ更新と差分更新の時のコンテンツの
新鮮さの分析がよい。
 Web Warehousing. Data Quality Control.
• Computing Geographical Scopes of Web
resources (Columbia U., Gigabeat)
-- WWW contentsの地理的に有意義な範
囲を解析する方法。Webのリンク構造から
求める。Web wの地理的範囲とは：
地域Lに属すweb多数からｗへリンクがあ
り、かつ、それらが、Lにおいてなだらかに
分布している。この係数を計算する。
 Web世界の意思決定支援。
VLDB２KにおけるDBengine発表の流れ
XML,Web分析, DWH、E-Commerceにおける
DB的な要素技術にいかにDBエンジンが
適応するか
• RISC-style DB engine (Microsoft)
•
•
•
•
App.-tier In-Memory Data Mgt. (TimesTen)
8. Oracle8i Index-Organized Table.
3. XML作成用のSQLエンジン（IBM)
5. SQLserver2000における実体化ビュー自動選択
方式 (MS)
• 6. Integration of Data Mining and RDB (MS)
• 7. PicoDBMS (スマートカード内蔵DBエンジン）
まとめ：VLDBの感想
• VLDB = Echo, sometimes close to Source.
• DBと無関係なIT応用分野の強さ
= XML, Web analysis, E-commerce
middleware, ERP, DWH.
• DB engine vendor の積極性が目立つ。
DBエンジンのライブラリ化による、新ITミドル
ウェアへのDB coreの浸透の波。
感想２
• ディスク、ストレージサーバ、ネットワーク、
テープアーカイバの話がない。
• セキュリティの話がない。
• メタデータ、LDAPの話が出てきた。
• BioInformatics は？ -- 多数の聴衆を得ず。
 VLDB2000のEcho
= DBソフトウェアの流れを映す。
完
• 注意書き
この資料は12月6日に行われたDBWeb2000(ACM
SIGMOD 日本支部第16回大会)において行われた発表
において使用されたものに加筆･修正を加えたものです。
DBWeb2000については www.sigmodj.is.uec.ac.jpをご覧
ください。
Copyright ：大森匡

Download Report