Building Query Compilers

《Building Query Compilers》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、BuildingQueryCompilers(UnderConstruction)[expectedtimetocompletion:5years]GuidoMoerkotteSeptember3,2009ContentsIBasics31Introduction51.1GeneralRemarks...........................51.2DBMSArchitecture.........................51.3InterpretationversusCompilation................

2、..61.4RequirementsforaQueryCompiler................91.5SearchSpace.............................111.6GenerationversusTransformation.................121.7Focus.................................121.8OrganizationoftheBook......................132TextbookQueryOptimization152.1Ex

3、ampleQueryandOutline.....................152.2Algebra................................162.3CanonicalTranslation........................172.4LogicalQueryOptimization.....................202.5PhysicalQueryOptimization....................242.6Discussion........................

4、.......253JoinOrdering313.1QueriesConsidered..........................313.1.1QueryGraph.........................323.1.2JoinTree...........................333.1.3SimpleCostFunctions....................343.1.4ClassificationofJoinOrderingProblems..........403.1.5SearchSpaceSiz

5、es......................413.1.6ProblemComplexity.....................453.2DeterministicAlgorithms......................473.2.1Heuristics...........................473.2.2DeterminingtheOptimalJoinOrderinPolynomialTime493.2.3TheMaximum-Value-PrecedenceAlgorithm........563.2.

6、4DynamicProgramming...................613.2.5Memoization.........................783.2.6JoinOrderingbyGeneratingPermutations........793.2.7ADynamicProgrammingbasedHeuristicsforChainQueries813.2.8Transformation-BasedApproaches.............94iiiCONTENTS3.3ProbabilisticAlgori

7、thms.......................1013.3.1GeneratingRandomLeft-DeepJoinTreeswithCrossProd-ucts..............................1013.3.2GeneratingRandomJoinTreeswithCrossProducts...1033.3.3GeneratingRandomJoinTreeswithoutCrossProducts.1073.3.4QuickPick..........................1163.3

8、.5IterativeImprovement....................1163.3.6SimulatedAnnealing.....................