Speculative query evaluation over databases of plans

Shamim A. Naqvi, T. Imielinski, Madhur Kohli, K. Vadaparty

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationProc 2 Int Conf Inf Knowl Manage
PublisherPubl by ACM
Number of pages12
ISBN (Print)0897916263, 9780897916264
StatePublished - 1993
Externally publishedYes
EventProceedings of the 2nd International Conference on Information and Knowledge Management - Washington, DC, USA
Duration: Nov 1 1993Nov 5 1993

Publication series

NameProc 2 Int Conf Inf Knowl Manage


OtherProceedings of the 2nd International Conference on Information and Knowledge Management
CityWashington, DC, USA

All Science Journal Classification (ASJC) codes

  • General Engineering


Dive into the research topics of 'Speculative query evaluation over databases of plans'. Together they form a unique fingerprint.

Cite this