VLDB2000報告 その1:WWW,XML関連 (完成版) DBWeb2000 (SigmodJ第16回大会資料) 2000年12月6日 大森 匡@SIGMOD日本支部書記 (電気通信大学大学院 情報システム学研究科 www.is.uec.ac.jp) VLDB2000報告とは? • SIGMOD日本支部の活動の1つ – 最新の データベース研究動向を会員に報告する。- 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の全体像 • 方向1 -- 新しい情報システムにおけるイン フラストラクチャとしてのDB的な要素技術 -- XML放送, Web分析、crawlerの コンテンツ管理、高次元データ • 方向2 -- 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あたりの性能予測性、性能調整能力を明確化。 • 第1層=単一テーブルのselect, B+木インデク ス、レコード更新、トランザクションのみ。 SQLなし。(ただの永続データストレージ) • 第2層=SPJ問い合わせと集約演算、ストリー ム並列まで。 (OLAP,DSS) • 第3層=フル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 10^5程度のXpathでインデクスを作る。 Query index Xml doc. 照合した プロファイル Xml parser へ Xml文書を 送る。 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 へ戻す。) 2のまとめ • 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 ここまでのまとめ • 1.RISC-style DB engine – エンジンの多層化。 • 2. XMLのデータ放送、フィルタリング – DB的なインデクス、負荷分散が必須。 = 現状は独自に開発。 IT応用特有の新インデクスの支援 がDB側に必要。 3. Efficiently Publishing Relational data as XML documents (IBM) • 対象: XMLはビジネスデータの交換プロ トコル。 データの管理はRDB。 • 課題: 関係データをXML文書に変換する 時、ほとんどすべての処理をSQL文1つで 書き、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文1つで 書き、SQLサーバの中でやってしまう。 • 方法 : SQLへの構成子の追加と SQL文実行プランの最適化戦略。 提案方法 1.関係データからXMLの指定タグ付きの テキストをつくる構成子、 2.XMLの同一タグのテキストデータ群を 連接する構成子XMLAGG を入れ子SQL文で使う。 SQL文1つで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. * エンジンの外でソート順にタグづけ。 (一定メモリの場合)。 3のまとめ (1) 結果:DB2、約32万件からXML文書を生成: 30sec.(エンジン外、stored proc.法) から 6sec.(エンジン内、OuterUnion法) へ削減。 3のまとめ (2) • 感想: 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の幾何分布で自己ループを追 加する。) Walking1回あたり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の分析結果) -- 本実験の分析時間はPC1台で2日以下。 -- 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多数からwへリンクがあ り、かつ、それらが、Lにおいてなだらかに 分布している。この係数を計算する。 Web世界の意思決定支援。 VLDB2Kにおける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の浸透の波。 感想2 • ディスク、ストレージサーバ、ネットワーク、 テープアーカイバの話がない。 • セキュリティの話がない。 • メタデータ、LDAPの話が出てきた。 • BioInformatics は? -- 多数の聴衆を得ず。 VLDB2000のEcho = DBソフトウェアの流れを映す。 完 • 注意書き この資料は12月6日に行われたDBWeb2000(ACM SIGMOD 日本支部第16回大会)において行われた発表 において使用されたものに加筆・修正を加えたものです。 DBWeb2000については www.sigmodj.is.uec.ac.jpをご覧 ください。 Copyright : 大森 匡
© Copyright 2024 ExpyDoc