Probably approximately optimal derivation strategies
Russell Greiner, Pekka Orponen · 1991
An inference graph can have many "derivation strategies", each a particular ordering of the steps involved in reducing a given query to a sequence of database retrievals. An "optimal strategy" for a given distribution of queries is a complete strategy whose "expected cost" is minimal, where the expected cost depends on the conditional probabilities that each requested retrieval succeeds, given that a member of this class of queries is posed. This paper describes the PAO algorithm that first uses a set of training examples to approximate these probability values, and then uses these estimates to produce a "probably approximately optimal" strategy --- i.e., given any ffl; ffi ? 0, PAO produces a strategy whose cost is within ffl of the cost of the optimal strategy, with probability greater than 1 \\Gamma ffi . This paper also shows how to obtain these strategies in time polynomial in 1=ffl, 1=ffi and the size of the inference graph, for many important classes of graphs, including all and...