WEKO3
アイテム
Prediction-hardness of acyclic conjunctive queries
http://hdl.handle.net/10228/373
http://hdl.handle.net/10228/3733ed9110b-585b-433b-ab0f-394960970862
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
j.tcs.2005.09.006.pdf (172.6 kB)
|
|
| アイテムタイプ | 学術雑誌論文 = Journal Article(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2007-11-20 | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | Prediction-hardness of acyclic conjunctive queries | |||||||||||||
| 言語 | en | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | eng | |||||||||||||
| 著者 |
平田, 耕一
× 平田, 耕一
WEKO
597
|
|||||||||||||
| 抄録 | ||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||
| 内容記述 | A conjunctive query problem is a problem to determine whether or not a tuple belongsto the answer of a conjunctive query over a database. In this paper, a tuple,a conjunctive query and a database in relational database theory are regarded as aground atom, a nonrecursive function-free definite clause and a finite set of groundatoms, respectively, in inductive logic programming terminology. An acyclic conjunctivequery problem is a conjunctive query problem with acyclicity. Concernedwith the acyclic conjunctive query problem, in this paper, we present the hardnessresults of predicting acyclic conjunctive queries from an instance with a j-databaseof which predicate symbol is at most j-ary. Also we deal with two kinds of instances,a simple instance as a set of ground atoms and an extended instance as aset of pairs of a ground atom and a description. We mainly show that, from both asimple and an extended instances, acyclic conjunctive queries are not polynomialtimepredictable with j-databases (j ≥ 3) under the cryptographic assumptions,and predicting acyclic conjunctive queries with 2-databases is as hard as predictingDNF formulas. Hence, the acyclic conjunctive queries become a natural examplethat the equivalence between subsumption-efficiency and efficient pac-learnabilityfrom both a simple and an extended instances collapses. | |||||||||||||
| 書誌情報 |
Theoretical Computer Science 巻 348, 号 1, p. 84-94, 発行日 2005-12-02 |
|||||||||||||
| 出版社 | ||||||||||||||
| 出版者 | Elsevier | |||||||||||||
| DOI | ||||||||||||||
| 関連タイプ | isVersionOf | |||||||||||||
| 識別子タイプ | DOI | |||||||||||||
| 関連識別子 | https://doi.org/10.1016/j.tcs.2005.09.006 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||
| 収録物識別子 | 0304-3975 | |||||||||||||
| 著作権関連情報 | ||||||||||||||
| 権利情報 | Copyright (c) 2005 Elsevier B.V. | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | acyclic conjunctive query | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | inductive logic programming | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | prediction | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | prediction-preserving reduction | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | subsumption | |||||||||||||
| 出版タイプ | ||||||||||||||
| 出版タイプ | AM | |||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||
| 査読の有無 | ||||||||||||||
| 値 | yes | |||||||||||||
| 情報源 | ||||||||||||||
| 識別子タイプ | URI | |||||||||||||
| 関連識別子 | http://www.sciencedirect.com/science/journal/03043975 | |||||||||||||
| 関連名称 | http://www.sciencedirect.com/science/journal/03043975 | |||||||||||||
