Speculative query evaluation over databases of plans

Speculative query evaluation is the process of answering queries over databases containing objects that serve as compact representations for very large search spaces. Such objects occur naturally in scheduling, planning and engineering applications. The basic idea behind efficient evaluation of speculative queries is the ability to construct a subset of the database, called a witness of the query, which is sufficient to answer the query. In some cases, it is more efficacious to construct counter witnesses that are sufficient to falsify a query because early falsification reduces the work involved. We also introduce a third kind of witness whose behavior is socinian in the sense that it is not omnipotent but its ability to answer queries grows as the database changes. Finally, we introduce a notion of sentinels that are subsets of a database designed in such a way that a pre-determined set of queries to a sentinel is guaranteed to have efficient evaluations.