関数従属性を持つ結合クエリの数え上げ計算量【JST・京大機械翻訳】

Carmeli Nofar; Kroll Markus

プレプリント

J-GLOBAL ID：202202218852046031 整理番号：21P0005794

関数従属性を持つ結合クエリの数え上げ計算量【JST・京大機械翻訳】

Enumeration Complexity of Conjunctive Queries with Functional Dependencies

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2017年12月21日プレプリントサーバーでの情報更新日： 2021年09月26日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

機能的依存性(FD)の存在におけるConjunective Queies(CQs)の回答を列挙する複雑性を研究した。この焦点は,線形時間前処理に従って,一定遅延で出力タプルをリストする能力にある。既知の二分切断は,非環状自己joinフリーCQを,そのような計数をアドミットするもの,およびそうではないものに分類する。しかし,この分類は,データベースが属性間の依存性を示す共通事例においてもはや保持されない。すなわち,ハードとして分類されるいくつかのクエリは,依存性が説明されるならば,実際に扱いやすい。FDを収容するための二分切開の一般化を確立した。したがって,著者らの分類は,CQと一組のFDの組み合わせが線形時間前処理で一定遅延計数を許すと決定する。さらに,一般的なタイプのFDを収容するために,繰返しCQsの硬度結果を一般化した。著者らの開発のさらなる結論は,線形遅延による計数のための二分切開と不等性を有するCQのための二分切開を含む。最後に,全ての結果が,FDを一般化する既知のクラス(例えば,映画当りのジャンル数に対する上限,または人当たりの友人)を一般化する,既知のクラスの「心因性依存性」に適用されることを示した。【JST・京大機械翻訳】

, , , , , ,
, , , 【Automatic Indexing@JST】

計算理論 , 移動通信 , 検索技術 , データベースシステム , 生体遠隔測定

, ,

前のページに戻る