@article{oai:kyutech.repo.nii.ac.jp:00000129,
 author = {Hirata, Kouichi and 平田, 耕一},
 issue = {1},
 journal = {Theoretical Computer Science},
 month = {Dec},
 note = {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.},
 pages = {84--94},
 title = {Prediction-hardness of acyclic conjunctive queries},
 volume = {348},
 year = {2005},
 yomi = {ヒラタ, コウイチ}
}