Wyniki wyszukiwania - BazTech

1

Types and Type Checking in Stack-Based Query Languages

Hryniów R., Lentner M., Stencel K., Subieta K.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2005

|

Nr 984

1-60

EN

In this report we propose a new approach to types and static type checking in object-oriented database query and programming languages. In contrast to typical approaches to types which involve very advanced mathematical concepts we present a type system from the practitioners' point of view. We argue that many features of current object-oriented query/programming languages, such as ellipses, automatic coercions and irregularities in data structures, cause that very formal type systems are irrelevant to practical situations. We treat types as some syntactic qualifiers (tokens or some structures of tokens) attached to objects, procedures, modules and other data/program entities. Such syntactic qualifiers we call signatures. We avoid the simpleminded notion that a type has some internal semantics e.g. as a set of values. In our assumptions a type inference system is based on predefined decision tables involving signatures and producing type checking decisions, which can be the following: (1) type error, (2) new signature, (3) dereference, coercion and/or delegation of a type check to run-time. A type inference decision table is to be developed for every query/programming operator. Type inferences are implied by the stack-based approach (SBA) to object-oriented query/programming languages. Static type checking is just a compile time simulation of the run-time computation. Thus the type checker is based on data structures that statically model run-time structures and processes, that is: (1) metabase (internal representation of a database schema, a counterpart of an object store), (2) static environment stack (a counterpart of run-time environment stack), (3) static result stack (a counterpart of run-time result stack) and (4) type inference decision tables (a counterpart of run-time computations). Then, we present the static type check procedure which is driven by the metabase, the static stacks and the type inference decision tables. To discover several type errors in one run we show how to correct some type errors during the type check. Finally we present our prototype implementation showing that our approach is feasible and efficient with moderate implementation effort.

PL

W raporcie proponujemy nowe podejście do typów i statycznej kontroli typologicznej w obiektowych językach zapytań/programowania. W przeciwieństwie do podejść wykorzystujących zaawansowane koncepcje matematyczne prezentujemy tu pozycję praktyków. Wiele cech obecnych języków zapytań/programowania, takich jak elipsy, automatyczne koercje oraz nieregularności struktur danych, powodują, że bardzo formalne systemy typologiczne nie odpowiadają praktyce. Proponujemy typy jako syntaktyczne kwalifikatory (znaki lub struktury znaków) przypisane do obiektów, procedur oraz innych bytów programistycznych. Takie kwalifikatory nazwaliśmy sygnaturami. Unikamy popularnego punktu widzenia, w którym typ posiada wewnętrzną semantykę, np. w postaci zbioru wartości. System wnioskowania o typie jest oparty na tabelach decyzyjnych działających na sygnaturach i generujących decyzje w zakresie kontroli typologicznej, które mogą być następujące: (1) błąd typologiczny, (2) nowa sygnatura, (3) dereferencja, koercja i/lub oddelegowanie kontroli typu do czasu wykonania. Tablice decyzyjne powinny być sporządzone dla każdego operatora występującego w zapytaniach/programach. Wnioskowanie o typie jest implikowane przez podejście stosowe (SBA) do obiektowych języków zapytań/programowania. Statyczna kontrola typologiczna symuluje podczas kompilacji tę sytuację, która zajdzie podczas czasu wykonania. Stąd kontroler typów jest oparty na strukturach danych, które statycznie modelują struktury i procesy czasu wykonania, tj.: (1) metabaza (wewnętrzna reprezentacja schematu, odpowiednik składu obiektów), (2) statyczny stos środowiskowy (odpowiednik stosu środowiskowego), (3) statyczny stos rezultatów (odpowiednik stosu rezultatów), (4) tablice decyzyjne wnioskowania o typie (odpowiednik operatorów). Następnie prezentujemy procedurę statycznej kontroli typów, której działanie jest oparte na metabazie, statycznych stosach i tabelach decyzyjnych. Aby wykryć wiele błędów typologicznych w jednym przebiegu pokazujemy, jak należy skorygować pewne błędy typologiczne podczas kontroli typologicznej. Na końcu prezentujemy prototypową implementację pokazującą, że nasze podejście jest osiągalne i efektywne przy umiarkowanym wysiłku implementacyjnym.

2

Cached Queries in the Stack-Based Approach

Cybula P., Subieta K.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2005

|

Nr 985

1-56

EN

We present a new approach to optimization of ąuery languages using materialization of resułts previously answered ąueries. It is based on the stack-based approach (SBA) to object-oriented ąuery languages, which assumes the description of semantics in the form of abstract implementation of ąuery/programming language constructs. The semantics is expressed in terms of naming, scoping and binding. It involves an environmental stack - a basie mechanism of majority of programming languages. Novelty of our approach concerns methods and data structures proposed to realize the optimization method. The main properties of the structures as well as its essential problems arę outlined, particularly the problem of updating cached ąueries after changes of database content. In the report we present detailed description of our approach including all necessary information on the syntax, semantics, implementation and pragmatics of corresponding language constructs.

PL

Przedstawiamy nowe rozwiązanie optymalizacji języków zapytań z wykorzystaniem materializacji wyników wcześniej zrealizowanych zapytań. Rozwiązanie to bazuje na podejściu stosowym (SBA) do obiektowych języków zapytań wprowadzającym opis semantyki w formie abstrakcyjnej implementacji konstrukcji języka zapytań lub programowania. Semantyka ta jest wyrażana za pomocą trzech terminów: nazw, zakresu i wiązania. Wykorzystywany jest stos środowiskowy - podstawowy mechanizm większości języków programowania. Oryginalność naszego rozwiązania dotyczy metod i struktur danych proponowanych do realizacji wspomnianej metody optymalizacyjnej. Zostały opisane główne własności tych struktur danych, jak również istotne problemy, w szczególności problem aktualizacji zapamiętanych zapytań po zmianach zawartości bazy danych. W raporcie przedstawiamy szczegółowy opis naszego rozwiązania, w tym wszystkie niezbędne informacje dotyczące składni, semantyki, implementacji i pragmatyki odpowiednich konstrukcji językowych.

3

Recursive Query Processing in SBQL

Pieciukiewicz T., Subieta K.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2004

|

Nr 979

1-56

EN

Recursive queries arę reąuired for many tasks of database applications. Among them we can mention Bill-Of-Material (BOM), various kinds of networks (transportation, telecommunication, etc.), processing semi-structured data (XML, RDF), and so on. The support for recursive queries in current query languages is limited and lacks of theoretical foundations. In particular, this concerns corresponding extensions of SQL in Oracle and DB2 systems. In this report we present recursive query processing capabilities for the object-oriented Stack-Based Query Language (SBQL) and compare them with similar capabilities in yariants of SQL. SBQL offers very powerful and flexible recursive querying capabilities due to the fact that recursive processing operators arę fully orthogonal to other features of this language. This report specifies corresponding SBQL constructs, such as transitive closures and fixed point equations. We compare them to other query languages, in particular to Datalog. We also present briefly optimization possibilities for recursive queries.

PL

Rekurencyjne zapytania są wymagane dla wielu zadań występujących w rzeczywistych aplikacjach baz danych. Wśród nich możemy wymienić rachunek materiałów (BOM), różne typy sieci (transportowa, telekomunikacyjna, itp.), przetwarzanie danych półstrukturalnych (XML, RDF) itd. Wspomaganie dla rekurencyjnych zapytań w obecnych językach zapytań jest ograniczone i pozbawione podstaw teoretycznych. W szczególności, dotyczy to odpowiednich rozszerzeń SQL w systemach Oracle i DB2. W raporcie przedstawiamy możliwości w zakresie rekurencyjnych zapytań w języku zorientowanym obiektowo Stack-Based Query Language (SBQL) i porównujemy je do podobnych możliwości w wariantach SQL. SBQL oferuje bardzo mocne i elastyczne możliwości w zakresie rekurencyjnych zapytań dzięki temu, że operatory służące do przetwarzania rekurencyjnego są całkowicie ortogonalne w stosunku do innych cech języka. Raport specyfikuje odpowiednie konstrukcje SBQL, takie jak tranzytywne domknięcia oraz równania stałopunktowe. Porównujemy je do innych języków zapytań, w szczególności do Datalogu. Na zakończenie prezentujemy krótko możliwości optymalizacji zapytań rekurencyjnych.

4

Data-Intensive Grid Computing Based on Updatable Views

Habela P., Kaczmarski K., Kozankiewicz H., Lentner M., Stencel K., Subieta K.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2004

|

Nr 974

1-56

EN

In this report we propose a new approach to integration of distributed heterogeneous resources on the basis of a canonical object-oriented database model, a query language and updateable database views. Views are used as wrappers/mediators on top of local servers and as a data integration facility for global applications. Views support location, implementation and replication transparency. Because views are defined in a high-level query language, the mechanism is much more abstract and flexible in comparison to e.g. CORBA or Web Services. The report presents a short introduction to the query language SBQL and updateable views. It also presents the architecture of the grid network based on updateable views, and simple examples illustrating the mechanism. In the report we also show how the mechanism can be used in peer-to-peer networks. We shortly describe the process of grid design and development. Finally, we present some issues related to grid metadata.

PL

W raporcie proponujemy nowe podejście do integracji rozproszonych, heterogenicznych zasobów. Podejście to oparte jest na kanonicznym obiektowym modelu danych, języku zapytań i aktualizowalnych perspektywach bazy danych. Perspektywy są tutaj używane jako osłony/mediatory, przez które lokalne serwery udostępniają swoje zasoby, oraz jako element, który integruje zasoby i udostępnia je globalnym aplikacjom. Perspektywy wspierają przezroczystość położenia, implementacji oraz replikacji. Perspektywy są zdefiniowane w języku wysokiego poziomu i w związku z tym są one bardziej uniwersalne niż np. CORBA czy Web Services. W raporcie przedstawiamy krótkie wprowadzanie do języka zapytań SBQL i aktualizowanych perspektyw zdefiniowanych na bazie tego języka. Prezentujemy także architekturę sieci grid opartą na aktualizowanych perspektywach i przedstawiamy parę przykładów ilustrujących jej działanie. W raporcie pokazujemy jak prezentowany mechanizm może być wykorzystany w sieciach typu peer-topeer, a następnie krótko omawiamy jak wygląda proces projektowania i implementacji gridu. Na koniec w raporcie prezentujemy zagadnienia związane z metadanymi w gridzie.

5

Uptadeable Object Views

Kozankiewicz H., Leszczyłowski J., Płodzień J., Subieta K.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2002

|

Nr 950

1-54

EN

We present a new approach to updateable, object-oriented, virtual (non-materialized) database views. It is based on the stack-based approach (SBA) to object-oriented query languages, which assumes the description of semantics in the form of abstract implementation of query/programming language constructs. The semantics is expressed in terms of naming, scoping and binding. It involves an environmental stack - a basic mechanism of majority of programming languages. Novelty of our approach is that a view definer has the possibility to introduce into a view definition any information about intents of view updates. The information has the form of procedures, which dynamically overload generic view updating operation. This feature opens possibilities, which have not been even considered yet in other approaches. The approach is relevant not only to any kind of object-oriented and object-relational database management systems, but can also be used to constructing intelligent wrappers and mediators for federated databases, for Web and/or XML applications, and for applications based on an agent-oriented ontology infrastructure. In the report we present detailed description of our approach including all necessary information on the syntax, semantics, implementation and pragmatics of corresponding language constructs. We also present examples demonstrating the power of our approach.

PL

Praca prezentuje nowe podejście do aktualizowanych, obiektowych i wirtualnych (niematerializowanych) perspektyw baz danych. Podejście jest oparte na podejściu stosowanym do implementacji konstrukcji języka zapytań/programowania. Semantyka jest wyrażona w terminach nazywania, ograniczenia zakresu nazw oraz wiązania. Wykorzystuje stos środowiskowy - podstawowy mechanizm większości języków programowania. Nowość naszego podejścia polega na tym, że osoba definiująca perspektywę ma możliwości wprowadzenia do definicji perspektywy dowolnej informacji o intencji aktualizacji perspektywy. Ta informacja ma postać procedur, które dynamicznie przeciążają generyczne operacje aktualizujące perspektywę. To podejście otwiera możliwości, które nie były dotąd nawet rozważane w innych podejściach. Jest ono nie tylko relewantne do dowolnych obiektowych lub obiektowo-relacyjnych systemów zarządzania bazą danych, ale może być także zastosowane do konstrukcji inteligentnych osłon i mediatorów dla federacyjnych baz danych, aplikacji webowych i/lub opartych na XML, oraz dla zastosowań agentowych opartych na infrastrukturze ontologii. W raporcie przedstawiamy szczegółowy opis naszego podejścia zawierający wszystkie potrzebne informacje dotyczące składni, semantyki, implementacji i pragmatyki odpowiednich konstrukcji językowych. Prezentujemy przykłady ilustrujące możliwości tego podejścia. Słowa kluczowe : obiektowość, język zapytań, baza danych, perspektywa, bazy danych, aktualizacja perspektyw, podejście stosowe.