文献

J-GLOBAL ID：201202251871026580   整理番号：12A1216234

結合クエリに対するサイズとツリー幅境界

Size and Treewidth Bounds for Conjunctive Queries

著者 (4件)： GOTTLOB Georg (Univ. Oxford, GBR) ,  LEE Stephanie Tien (Univ. Oxford, GBR) ,  VALIANT Gregory (Univ. California, Berkeley) ,  VALIANT Paul (Univ. California, Berkeley)
資料名： Journal of the ACM (Association for Computing Machinery)  (Journal of the ACM (Association for Computing Machinery))
巻： 59  号： 3  ページ： 16:1-16:35  発行年： 2012年06月 
JST資料番号： C0267A  ISSN： 0004-5411  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 結合クエリーの結果は,どれ位大きく複雑に入力と関連できるかを考察した。クエリー自体の構造的特性のみに依存する,クエリー結果サイズに対する最悪ケース境界を導出した。また,クエリー結果のツリー幅に対する境界(データベースの複雑さ)を導出し,ツリー幅を保持する結合クエリを特性化した。これらは,カラーリング数を各クエリーに結合させるクエリー変数のカラーリングに基づく。キーも単純キーも特定されない環境において,厳格な最悪ケースサイズ境界を確立し,ツリー幅保持を特性化した。一般的関数従属を有する環境において,最悪ケースサイズ境界と多変量エントロピー構造との結合を確立し,情報理論ツールのデータベース解析への利用を可能にした。最後に,サイズ境界の決定,およびツリー幅保持の決定に関する計算複雑性の結果を示した。

シソーラス用語： 質問 ,  *データベース管理システム ,  *木探索 ,  *境界 ,  事例研究 ,  計算理論 ,  キーワード ,  エントロピー ,  関数従属 ,  計算量 ,  *彩色問題 ,  関係データベース ,  キャラクタリゼーション
準シソーラス用語： クエリー ,  ツリー探索 ,  データベース理論 ,  計算複雑性 ,  最悪ケース解析 ,  特性化

分類 (1件)： データベースシステム  (JD03030U)

タイトルに関連する用語 (3件)： クエリ ,  サイズ ,  境界