Please use this identifier to cite or link to this item:
Title: Exhaustive reuse of subquery plans to stretch iterative dynamic programming for complex query optimization
Keywords: Databases, Complex Query optimization, Iterative Dynamic Programming, Sub query plan reuse, Cover set generation, Sub graph isomorphism
Issue Date: 3-Jan-2011
Citation: 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.
Appears in Collections:Master's Theses (Open)

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



Google ScholarTM


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