Optimization of object-oriented queries by factoring out independent subqueries

• Autorzy: Płodzień J. , Subieta K.

Warianty tytułu

PL

Optymalizacja obiektowych zapytań poprzez wyciąganie przed nawias niezależnych podzapytań

• Języki publikacji: EN

Abstrakty

EN

We generalize query optimization methods based on rewriting for a general object-oriented model and a formalized OQL-like query language. Our approach makes it possible to detect and factor out independent subqueries in queries bulit upon traditional or new query operators, including dependent joins of OQL, quantifiers, generalized path expressions and method invocations. In contrast to well-known methods relying on specific patterns of algebraic or calculus expressions, our methodis based on a formal analysis of scoping and binding rules for names occuring in a query and its subqueries. It neither depends on the complexity of an independent subquery nor on the operator connecting this subquery to its parent query. Being very general, the method is simple to understand and analyze. We follow the stack-based approach to object-oriented query languages (having roots in the semantics of programming languages), rather than object algebras or calculi.

PL

W pracy przedstawiamy uogólnienie metod optymalizacji zapytań opartych na przepisywaniu dla ogólnego modelu obiektowego i sformalizowanego języka zapytań w duchu OQL. Nasze podejście umożliwia wykrywanie i "wyciąganie przed nawias" niezależnych podzapytań wystepujących w zapytaniach konstruowanych przy pomocy tradycyjnych i nowych operatorów, m. in. zależnych złączeń z języka OQL, kwantyfikatorów, uogólnionych wyrażeń ścieżkowych i wywołań metod. W przeciwieństwie do dobrze znanych metod operujących na specyficznych wzorach wyrażeń algebraicznych lub wyrażeń pewnego rachunku, nasza metoda jest oparta na formalnej analizie zakresów i reguł wiązania dla nazw wystepujących w danym zapytaniu i jego podzapytaniach. Nie zależy ona ani od stopnia złożoności niezależnego podzapytania, ani od rodzaju operatora lączącego go z pytaniem nadrzędnym. Metoda ta jest jednocześnie ogólna oraz łatwa do zrozumienia i wykorzystania do analizy zapytań. W naszej metodzie używamy podejścia stosowego do obiektowych zapytań (które ma korzenie w semantyce języków programowania) zamiast obiektowych algebr i rachunków.

Słowa kluczowe

EN

object-oriented data model; query processing; environment stack; static analysis of queries; query optimization; rewriting rules; factoring out

PL

obiektowy model danych; przetwarzanie zapytań; stos środowisk; statyczna analiza zapytań; optymalizacja zapytań; reguły przepisywania; wyciąganie przed nawias

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 1999
• Tom: nr 889
• Strony: 1--16

Twórcy

autor

Płodzień J.

autor

Subieta K.

• Instytut Podstaw Informatyki PAN ul. Ordona 21 01-237 Warszawa,