Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/20999
Title: Exhaustive reuse of subquery plans to stretch iterative dynamic programming for complex query optimization
Authors: MEDURI VENKATA VAMSIKRISHNA
Keywords: Databases, Complex Query optimization, Iterative Dynamic Programming, Sub query plan reuse, Cover set generation, Sub graph isomorphism
Issue Date: 3-Jan-2011
Source: MEDURI VENKATA VAMSIKRISHNA (2011-01-03). Exhaustive reuse of subquery plans to stretch iterative dynamic programming for complex query optimization. ScholarBank@NUS Repository.
Abstract: Query optimization using Dynamic Programming is known to produce the best quality plans thus enabling the execution of queries in optimal time. But Dynamic programming cannot be used for complex queries because of its inherent exponential nature owing to the explosive search space. Hence greedy and randomized methods of query optimization come into play. Since these algorithms cannot give optimal plans, the focus has always been on reducing the compromise in plan quality and still handle larger queries. This thesis studies the various approaches that were adopted to address this problem. One of the earliest approaches was Iterative Dynamic Programming. Based on the study of the previous work, we proposed a scheme to reduce the search space of Dynamic Programming based on reuse of query plans among similar subqueries. The method generates the cover set of similar subgraphs present in the query graph and allows their corresponding subqueries to share query plans among themselves in the search space. Numerous variants to this scheme have been developed for enhanced memory efficiency and one of them has been found better suited to improve the performance of Iterative Dynamic Programming.
URI: http://scholarbank.nus.edu.sg/handle/10635/20999
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
report.pdf758.27 kBAdobe PDF

OPEN

NoneView/Download

Page view(s)

327
checked on Dec 11, 2017

Download(s)

433
checked on Dec 11, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.