An algorithm for answering queries efficiently using views

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

33 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationProceedings - 12th Australasian Database Conference, ADC 2001
EditorsMaria E. Orlowska, John F. Roddick
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Electronic)0769509665, 9780769509662
StatePublished - Jan 1 2001
Event12th Australasian Database Conference, ADC 2001 - Gold Coast, Australia
Duration: Jan 29 2001Feb 1 2001

Publication series

NameProceedings - 12th Australasian Database Conference, ADC 2001


Other12th Australasian Database Conference, ADC 2001
CityGold Coast

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Information Systems
  • Software


Dive into the research topics of 'An algorithm for answering queries efficiently using views'. Together they form a unique fingerprint.

Cite this