Predictionhardness of acyclic conjunctive queriesAuthor: Kouichi Hirata
Source:
Theoretical Computer Science Vol. 348, Issue 1,
December 2005, pp. 8494
Abstract. A conjunctive query problem is a problem to determine whether or not a tuple belongs to 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 a ground atom, a nonrecursive functionfree definite clause and a finite set of ground atoms, respectively, in inductive logic programming terminology. An acyclic conjunctive query problem is a conjunctive query problem with acyclicity. Concerned with the acyclic conjunctive query problem, in this paper, we present the hardness results of predicting acyclic conjunctive queries from an instance with a jdatabase of which predicate symbol is at most jary. Also we deal with two kinds of instances, a simple instance as a set of ground atoms and an extended instance as a set of pairs of a ground atom and a description. We mainly show that, from both a simple and an extended instances, acyclic conjunctive queries are not polynomialtime predictable with jdatabases (j ≥ 3) under the cryptographic assumptions, and predicting acyclic conjunctive queries with 2databases is as hard as predicting DNF formulas. Hence, the acyclic conjunctive queries become a natural example that the equivalence between subsumptionefficiency and efficient paclearnability from both a simple and an extended instances collapses.

©Copyright 2005 Elsevier Science B.V.