文献

J-GLOBAL ID：202002283026508406   整理番号：20A1510468

データベース理論に合致する準同形不許容性特性試験の可試験性【JST・京大機械翻訳】

Testability of Homomorphism Inadmissibility Property Testing Meets Database Theory

著者 (2件)： Chen Hubie (Birkbeck, University of London, London, United Kingdom) ,  Yoshida Yuichi (National Institute of Informatics, Tokyo, Japan)
資料名： ACM Proceedings  (ACM Proceedings)
号： PODS ’19  ページ： 365-382  発行年： 2019年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 本論文では,関係データベースクエリの可試験性を考慮するために,特性試験の展望を利用した。一次動機は,その特性を決定するために,全データベースを読むことを回避するための要求である。著者らは,最も基本的で,大いに研究されたデータベースクエリである結合クエリに焦点を合わせる。各結合クエリは,関係構造Bが,関係構造Bによって満足されるかどうかを決定するような関係構造Aとして表現でき,AからBへの同形写像が存在するかどうかを決定する。これらの結果を同形写像の観点からフレーズした。正確に,著者らは,各関係構造Aに対して,Aからのホモモルフィズムの不可能性の可試験性を研究した。著者らは,入力関係構造Bへのオラクルアクセスを持つアルゴリズムを考察し,高い確率で,AからBまでのホモモルフィズムがないケースから,すべてのそのようなホモモルフィズムを抑制するために,Bからタプルの一定部分を除去する必要があるケースから,そのケースからBまで,そのケースから,そのケースは,そのケースから,その事例から,そのケース構造Aの完全なキャラクタリゼーションを提供し,その1つは,Bに対して一定数のクエリを作ることによって,片側誤差でホモモルフィズム不可能性をテストすることができる。特性化は,Aからのホモモルフィズム不可能性が,もしAのコアがアルファ非環状であるならば,片側誤差で,一定-クーリーテスト可能であることを示した。また,この問題の注入バージョンは,もしAがアルファ非巡回であるならば,片側誤差で,一定の質問可能であることを証明した。この結果は,一般的グラフモデルにおけるサブグラフフリー性をテストするための既存の結果を一般化した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *データベース ,  同形写像 ,  準同形写像 ,  関係データベース ,  キャラクタリゼーション ,  可試験性
準シソーラス用語： グラフモデル ,  オラクル ,  クエリー ,  データベース理論 , 【Automatic Indexing@JST】

著者キーワード (4件)： 結合質問 ,  超グラフの非環状性 ,  特性試験 ,  質問評価

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

タイトルに関連する用語 (4件)： データベース理論 ,  許容性 ,  特性試験 ,  可試験性