A Bottom-up Algorithm for Query Decomposition

  1. (PDF, 481 KB)
AuthorSearch for: ; Search for: ; Search for: ; Search for: ; Search for:
ConferenceInternational Journal of Innovative Computing and Applications (IJICA)
Subjectquery decomposition; bottom-up strategy; database integration; stratégie de bas en haut; intégration de bases de données
AbstractIn order to access data from various data repositories, in Global-As-View approaches an input query is decomposed into several subqueries. Normally, this decomposition is based on a set of mappings, which describe the correspondence of data elements between a global schema and local ones. However, building mappings is a difficult task, especially when the number of participating local schemas is large. In our approach, an input query is automatically decomposed into subqueries without using mappings. An algorithm is proposed to transform a global path expression (e.g., an XPath query) into local path expressions executable in local schemas. This algorithm considers parts of a path expression from right to left, i.e., the algorithm traverses from the bottom to the top of a schema tree depending on the structure of local schemas. Compared to topdown approaches, such as by Lausen and Marron, our algorithm can reduce the time for forming subqueries for local (e.g., XML) schemas to a large extent.
Publication date
AffiliationNRC Institute for Information Technology; National Research Council Canada
Peer reviewedNo
NRC number50342
NPARC number5763671
Export citationExport as RIS
Report a correctionReport a correction
Record identifier69236886-9edd-49bb-aa45-c7bcb1231f5f
Record created2009-03-29
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)