Optimization of object query languages
Hendrika Janna Steenhagen · 1995
Samenvattingde vertaling van een SQL-achtige querytaal naar een logische algebra, in de context van een geavanceerd gegevensmodel dat complexe objecten toestaat.Het werk dat hier gepresenteerd wordt kan geplaatst worden binnen de context van het geneste relationele model.Wij zijn van mening dat een effciënte implementatie van een querytaal voor het geneste relationele model de basis vormt voor een effciënte implementatie van querytalen voor object-georiënteerde gegevensmodellen.Het onderzoek bestaat uit twee delen: (1) de definitie van een logische algebra die geschikt is voor de implementatie van de gebruikerstaal (genaamd OSQL) en (2) het maken van de feitelijke vertaling.We definiëren een logische algebra genaamd ADL, een extensie van één van de algebra's die gedefiniëerd zijn voor het geneste relationele model.ADL is een verzamelings-georiënteerde taal, uitgebreid met taalconstructies die expliciete iteratie over verzamelingen toestaan.Deze laatste zijn nodig omdat attributen verzamelingswaardig kunnen zijn.We zijn van mening dat, zoals in relationele systemen, ook in geavanceerde systemen de logische algebra zoveel mogelijk verzamelings-georiënteerd dient te zijn, omdat verzamelingsoperatoren vele mogelijkheden tot optimalisatie bieden.De vertaling van de gebruikerstaal naar de logische algebra wordt traditioneel beschouwd als de taak van het parseeralgorithme; overwegingen met betrekking tot performance (prestatie) spelen geen rol in deze fase van query-processing.Wij denken echter dat optimalisatie een rol dient te spelen in elke stap van het implementatieproces.We besteden opnieuw aandacht aan de vertaling van SQL naar de relationele algebra, en we laten zien dat de feitelijke vertaling van de querytaal naar de logische algebra een grote invloed heeft op de uiteindelijke performance, vooral wanneer ook willekeurige taalconstructies zoals universele kwantificatie en disjunctie in de beschouwing betrokken worden.Standaard vertaalalgorithmen resulteren vaak in inefficiënte logische algebra-expressies, die daarbij vaak moeilijk algebraïsch te optimaliseren zijn.We stellen voor relationele algebra uit te breiden met enkele niet-standaard (join-) operatoren en we doen een poging te komen tot een verbeterd vertaalalgorithme: we combineren vertaling met optimalisatie.Uitgaande van een select-project-produktexpressie is de voornaamste heuristiek die gebruikt wordt in traditionele relationele optimalisatie het doorduwen van selecties en projecties.Deze heuristiek is gebaseerd op de wens de grootte van tussenresultaten zo klein mogelijk te houden.Het blijkt echter dat zowel de vertaling van SQL naar de algebra als logische optimalisatie gestuurd zou moeten worden door een meer gedetailleerd kostenmodel.Om te kunnen kiezen uit verschillende vertaalstrategieën zou een model dat een schatting maakt van de relatieve kosten van de diverse operatoren bijvoorbeeld nuttig kunnen zijn.Voor de vertaling van geneste OSQL queries naar de algebra definiëren we de nestjoinoperator, de equivalent van de relationele join-operator voor modellen met complexe objecten.We tonen aan dat we voor de vertaling van OSQL expressies dezelfde strategie kunnen hanteren als gebruikt wordt in het relationele model: een transformatie naar expressies bestaande uit (geneste) produkt-expressies.Deze observatie is echter hoofdzakelijk van theoretisch belang; teneinde meer efficiënte algebraïsche expressies te verkrijgen hebben we een zorgvuldig ontworpen vertaalalgorithme nodig, temeer daar logische herschrijving van een taal met complexe objecten nog moeilijker is dan het herschrijven van relationele algebra-expressies.We presenteren een raamwerk voor de vertaling van geneste OSQL agreed to be members of the committee.Gratefully, I acknowledge the anonymous referees, whose comments helped to improve the quality of my work.My colleagues are thanked for their pleasant cooperation and friendliness.Especially, my thanks go to Rolf de By, who has been a truly helpful friend, and to Sandra