TY - GEN
T1 - Speculative query evaluation over databases of plans
AU - Naqvi, Shamim A.
AU - Imielinski, T.
AU - Kohli, Madhur
AU - Vadaparty, K.
PY - 1993
Y1 - 1993
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0027801461&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0027801461&partnerID=8YFLogxK
U2 - 10.1145/170088.170391
DO - 10.1145/170088.170391
M3 - Conference contribution
AN - SCOPUS:0027801461
SN - 0897916263
SN - 9780897916264
T3 - Proc 2 Int Conf Inf Knowl Manage
SP - 439
EP - 450
BT - Proc 2 Int Conf Inf Knowl Manage
PB - Publ by ACM
T2 - Proceedings of the 2nd International Conference on Information and Knowledge Management
Y2 - 1 November 1993 through 5 November 1993
ER -