Ordering conjunctive queries (Q1060862)

Conjunctive problems are pervasive in artificial intelligence and database applications. In general, such problems cannot be solved without carefully ordering the set of conjuncts for the problem-solving system. In this paper, the problem of determining the best ordering for a set of conjuncts is addressed. We first show how simple information about set sizes can be used to estimate the cost of solving a conjunctive problem. Assuming the availability of this information, methods for ordering conjuncts are developed, based on several theorems and corollaries about ordering. We also consider two well-known heuristic ordering rules and discuss their advantages and disadvantages. Finally, the overall efficiency of including conjunct ordering in a problem solver is considered. To help reduce the overhead we present an approach of monitoring problem-solving cost at run-time. In this way conjunct ordering is limited to difficult problems where the cost of ordering is less significant. We also consider several issues involved in extending conjunct ordering to problems involving inference and planning problems.