TY - GEN
T1 - An algorithm for answering queries efficiently using views
AU - Mitra, P.
PY - 2001/1/1
Y1 - 2001/1/1
N2 - Algorithms for answering queries using views have been used in query planning in order to answer queries posed to knowledge bases, databases, and information systems. However, these algorithms do not scale well when the number of views increases. Three known algorithms, the bucket algorithm, the inverse-rules algorithm and an algorithm suggested by Leser (1998) have been used to rewrite queries using views before executing the queries. The bucket algorithm, predominantly used to reformulate queries, generates a candidate rewriting to a query using views, and checks that the rewriting is contained in the original query. An exponential conjunctive-query-containment-test needs to be performed to check each candidate rewriting. Using a few extra a buckets (shared-variable-buckets), we show how we can avoid the conjunctive-query-containment-test. This paper presents a scalable query rewriting algorithm-the shared-variable-bucket (SVB) algorithm. Experimental results demonstrate its superiority over other known algorithms.
AB - Algorithms for answering queries using views have been used in query planning in order to answer queries posed to knowledge bases, databases, and information systems. However, these algorithms do not scale well when the number of views increases. Three known algorithms, the bucket algorithm, the inverse-rules algorithm and an algorithm suggested by Leser (1998) have been used to rewrite queries using views before executing the queries. The bucket algorithm, predominantly used to reformulate queries, generates a candidate rewriting to a query using views, and checks that the rewriting is contained in the original query. An exponential conjunctive-query-containment-test needs to be performed to check each candidate rewriting. Using a few extra a buckets (shared-variable-buckets), we show how we can avoid the conjunctive-query-containment-test. This paper presents a scalable query rewriting algorithm-the shared-variable-bucket (SVB) algorithm. Experimental results demonstrate its superiority over other known algorithms.
UR - http://www.scopus.com/inward/record.url?scp=84964547570&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84964547570&partnerID=8YFLogxK
U2 - 10.1109/ADC.2001.904470
DO - 10.1109/ADC.2001.904470
M3 - Conference contribution
AN - SCOPUS:84964547570
T3 - Proceedings - 12th Australasian Database Conference, ADC 2001
SP - 99
EP - 106
BT - Proceedings - 12th Australasian Database Conference, ADC 2001
A2 - Orlowska, Maria E.
A2 - Roddick, John F.
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 12th Australasian Database Conference, ADC 2001
Y2 - 29 January 2001 through 1 February 2001
ER -