Ordering conjunctive queries
type: Item
instance of: scholarly article
title: Ordering conjunctive queries
zbMATH Open document ID: 0569.68077
DOI: 10.1016/0004-3702(85)90028-1
author: David E. Smith
author: Michael Genesereth
published in: Artificial Intelligence
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 3909780
zbMATH Keywords: conjunctive problem
MaRDI profile type: Publication
full work available at URL: 0004-3702(85)90028-1
OpenAlex ID: W2091327243
cites work: Q4747542
cites work: Q3862380
cites work: Q3856120
cites work: A logic for default reasoning
cites work: Optimal problem-solving search: All-or-none solutions
cites work: Controlling backward inference
cites work: Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis
cites work: Q3347338
Recommended article: Dynamic conjunctive queries
Recommended article: Q4414539
Recommended article: Query Order
Recommended article: Quantified Conjunctive Queries on Partially Ordered Sets
Recommended article: Quantified conjunctive queries on partially ordered sets
Recommended article: Conjunctive query containment revisited
Recommended article: Q4366882
Recommended article: Q3777504
description: scientific article; zbMATH DE number 3909780