Transcript Advanced Notions of SBQL - Instytut Podstaw Informatyki PAN

3rd Country Conference, February 2007
Advanced Notions of SBQL
(procedures, views, types, etc.)
by
Prof. Kazimierz Subieta
[email protected]
http://www.ipipan.waw.pl/~subieta
SBA/SBQL pages: http://www.sbql.pl
K.Subieta. Advanced Notions of SBQL, Slide 1
3rd Country Conference, Feb.2007
Extension of SBQL with imperative constructs
• SBQL queries can be embedded within statements that can
change the database or program state.
• Concerning this issue we follow state-of-the-art standards
known from majority of programming languages.
• Typical imperative constructs are creating a new object, deleting
an object, assigning new value to an object (updating) and
inserting an object into another object.
• We also introduce typical control and loop statements such as
if…then…else…, switch, while loops, for each iterators and
others.
• Some peculiarities are implied by queries that may return
collections; thus there are possibilities to generalize imperative
constructs according to this new feature.
K.Subieta. Advanced Notions of SBQL, Slide 2
3rd Country Conference, Feb.2007
Procedures, functions and methods
• A procedure call opens a new section on the environment stack.
• The section contains binders to local procedure objects (transient) and
binders related to the actual parameters of the procedure.
• Local procedure objects are invisible from outside.
• Scoping rules assume skipping irrelevant stack sections.
• Queries are used as actual parameters of procedures.
• A query determines an output from a functional procedure.
• A call of a functional procedure is considered a query.
Procedure p1 calls p2 .
Then, procedure p2 calls p3.
When p3 is executed, sections
of p1 and p2 are irrelevant for binding.
K.Subieta. Advanced Notions of SBQL, Slide 3
3rd Country Conference, Feb.2007
SBQL: Example of a procedure
• Procedure ChangeDept moves the specified employees to the
specified department.
procedure ChangeDept( E: EmpType[0..*]; D: DeptType ) {
delete ( Dept . employs ) where Emp in E;
for each E as e do {
create &e as employs;
insert employs into D;
e . worksIn := & D
e . D# := D . D#;
};
};
Let Kim become the manager of all designers working so far for Lee:
ChangeDept(
Emp where job = “designer” and (worksIn.Dept.boss.Emp.name) = “Lee”;
Dept where (boss.Emp.name) = “Kim” );
K.Subieta. Advanced Notions of SBQL, Slide 4
3rd Country Conference, Feb.2007
Parameter passing
• The stack-based machine is prepared to specify precisely
various parameter passing methods,
–
–
–
–
–
–
variants of call-by-value,
call-by-reference,
strict-call-by-value,
the method with parameter defaults,
call-by-value-return,
etc.
• SBQL deals with parameters being any queries; thus
corresponding parameter passing methods are generalized to
take collections into account.
K.Subieta. Advanced Notions of SBQL, Slide 5
3rd Country Conference, Feb.2007
SBQL updatable object views
• 30 years of R&D on views have resulted in minor results.
– Very restricted view updating in Oracle and DB2.
– Proposals concerning object-oriented views - limited and immature.
• Essentially, all previous solutions were based on the assumption
that a view definition is a function determined by a single query.
– View updating through side effects of the definition.
• First fine solution for RDBMS – instead of trigger views:
– Based on overloading of an updating operation on a virtual table by a
trigger with the code accomplishing the intention of the updating.
• SBQL views are based on a similar idea, but it is incomparably
more general and efficient.
– The idea works for any data model, including XML and O-O ones.
– It assumes that each operation on a virtual object is overloaded by a
special procedure written by the view definer.
– The procedure expresses definer’s intention of the operation.
K.Subieta. Advanced Notions of SBQL, Slide 6
3rd Country Conference, Feb.2007
General scenario of view processing
User program
A query
invoking the view
A consumer of the
query result (e.g. the
operator „update”)
…..
K.Subieta. Advanced Notions of SBQL, Slide 7
View definition
virtual
identifiers
Interpreter of
queries and updating
statements
A piece of the
interpreter code
implementing the
given consumer
…..
The procedure in
the view definition
overloading the
given consumer
…..
3rd Country Conference, Feb.2007
Overloaded operations on virtual objects
• Dereference, i.e. taking a value of a virtual object (on_retrieve).
– Unavailable in instead of trigger views.
• Assignment a new value to a virtual object (on_update).
• Deleting a virtual object (on_delete).
• Inserting a (material or virtual) object into a virtual object
(on_insert).
• Creating a new virtual object (on_create).
• If some of the procedures on_retrieve, …, on_create is not defined
by the view definer, the corresponding operation on virtual
objects is not allowed.
K.Subieta. Advanced Notions of SBQL, Slide 8
3rd Country Conference, Feb.2007
Example of a virtual updatable view
Stored
objects
Virtual
objects
Book
title
author
price
currency
sold
bestSellingBook
vtitle
vauthor
vprice
vprice always in euro, updating
of vprice is converted to the
proper currency of the book.
create view bestSellingBookDef {
virtual objects bestSellingBook {
return (Book where sold > 1000) as b;}
on_delete do { delete b; }
create view vtitleDef {
virtual objects vtitle { return (b.title) as t; }
on_retrieve do { return deref( t ); } }
create view vauthorDef {
virtual objects vauthor { return (b.author) as a; }
on_retrieve do { return deref( a ); } }
create view vpriceDef {
virtual objects vprice { return ( b.price ) as p; }
on_retrieve do { return convertToEuro( b.currency, p ); }
on_update (newPrice) do
{ p:= convertFromEuro(b.currency, newPrice);}}}
for each (BestSellingBook where vtitle = ”MDA” ) do vprice := vprice - 10;
K.Subieta. Advanced Notions of SBQL, Slide 9
3rd Country Conference, Feb.2007
Strong static type checking in SBQL
• In our approach and implementation we have taken the
following tenets:
– Don’t trust intuitions
• easy to come to inconsistency (the ODMG case).
– Don’t trust type theories
• too idealistic, addressing mathematical models very limited for practice.
– Distinguish internal and external type systems.
•
•
•
•
•
Internal type system reflects behavior of the type checking mechanism.
External type system is seen and used by the programmer.
Internal type system is much more sophisticated that the external one.
Both must coincide, but the internal type system should dominate.
ODMG defined an external type system only. This is like the definition
of a building construction by determining its front elevation.
– Trust only abstract implementation of the internal type system.
K.Subieta. Advanced Notions of SBQL, Slide 10
3rd Country Conference, Feb.2007
Static type checking mechanism for QLs
• Any static strong type checking mechanism must simulate runtime computations during compile time…
– …by reflecting run-time semantics with the precision that is available
at the compile time.
• New semantic properties of query languages cause that known
strong typing systems and their theories are totally useless.
• Current OO models and XML models introduce many
peculiarities that make strong typing very challenging:
– Ellipses, automatic coercions, automatic dereferences.
– Mutability, collection cardinality constraints, collection types (set, bag,
sequence, etc.), type names, multimedia types,....
– Irregularities in data structures (semi-structured data).
• We call the SBQL type system „semi-strong”, to underline liberal attitude
to strong typing.
K.Subieta. Advanced Notions of SBQL, Slide 11
3rd Country Conference, Feb.2007
Roles and functions of the SBQL typing system
• Compile-time type checking of query operators, imperative
constructs, procedures, functions, methods, views and modules.
• User-friendly, context dependent reporting on type errors.
• Resolving ambiguities with automatic type coercions, ellipses,
dereferences, literals and binding irregular data structures.
• Shifting type check to run-time, if it is impossible to do it during
compile time.
• Restoring a type checking process after a type error.
– To discover more than one type error in one run.
• Preparing information for query optimization by proper
decorating a query syntax tree.
– Decorations allow for automatic decisions concerning query rewriting,
use indices, etc.
K.Subieta. Advanced Notions of SBQL, Slide 12
3rd Country Conference, Feb.2007
Internal SBQL type system
• Three basic data structures are compile-time counterparts of
run time structures:
– Metabase – a counterpart of an object store.
– Static environment stack S_ENVS – a counterpart of ENVS
– Static result stack S_QRES – a counterpart of QRES
• Static stacks contain and process type signatures – internal
typing counterparts of corresponding run time entities.
– Signatures are atomic types, references to metabase nodes, static
binders n(s), where s is a signature, struct and bag signatures, etc.
– Signatures are additionally associated with attributes, such as
mutability, cardinality, collection kind, type name, multimedia, etc.
• For each query/program operator a decision table is provided:
– It determines allowed combinations of signatures and attributes, the
resulting signature and its attributes, and additional actions.
• Then, the type checking engine simulates run-time semantics.
K.Subieta. Advanced Notions of SBQL, Slide 13
3rd Country Conference, Feb.2007
Example decision table for dot
• Syntax: qL.qR
• E1, E2 are signatures of individual elements (not collections)
• T1, T2 are signatures of any types
Signature of qL
Signature of qR
Signature of qL.qR
E1
E2
E2
E1
bag{T2}
bag{T2}
E1
sequence{T2}
sequence{T2}
sequence{T1}
E2
sequence{E2}
sequence{T1}
sequence{T2}
sequence{T2}
bag{T1}
E2
bag{E2}
bag{T1}
bag{T2}
bag{T2}
Additional action
• Other cases (not included in this table) are type errors.
K.Subieta. Advanced Notions of SBQL, Slide 14
3rd Country Conference, Feb.2007
Classes, interfaces, types, schemas and metamodels
• In SBA/SBQL we make an attempt to clarify these concepts by assigning
pragmatic roles to them.
• Classes are source code units that contain implementation; after compilation they
became special kind of database objects employed by the stack-based machine.
• Interfaces are external specifications of access to objects; they contain no
implementation. Interfaces usually contain more information than types.
• Types are constraints on the construction and behavior of any program entities (in
particular, modules, objects, values, links, procedures, etc.) and constraints on the
query/programming context in which these entities can be used.
• Schemas are external (application programmer oriented) specifications of a
database content and are inevitable pragmatic part of a query/programming
languages.
• Metamodel is an internal representation of a schema; it is internally used by the
database management system and externally for generic programming with
reflection.
K.Subieta. Advanced Notions of SBQL, Slide 15
3rd Country Conference, Feb.2007
3-level architecture of object database applications
• A classical architecture involves two levels: database server and
application client. We introduce more levels.
• 1st: database programmers - prepare the server-side database
schema and implement (in SBQL + classical object-oriented
languages) database classes together with methods.
• 2nd: administrative programmers who determine access privileges
and external views for applications and application users. The
external views are determined by virtual updateable views, which
might accomplish sophisticated mappings between stored and
virtual data and mappings between updating of virtual data and
updating of stored data.
• 3rd: application programmers, who use interfaces to virtual views
delivered by the second layer.
• The subdivision on these three layers could make business
applications very flexible for development and maintenance.
K.Subieta. Advanced Notions of SBQL, Slide 16
3rd Country Conference, Feb.2007
Data-intense grids and P2P networks
• Integration of distributed, heterogeneous, fragmented and
redundant resources.
• The research concerns creating virtual repositories that integrate
distributed, heterogeneous, fragmented and redundant data and
service resources on the ground of virtual updateable views.
• We have developed and implemented an architecture of such an
virtual repository, its metamodel and other functional properties.
• As part of this research, we have developed a P2P network, which is
technically based on the Sun JXTA technology and conceptually on
the SBQL engine and its virtual updateable views.
K.Subieta. Advanced Notions of SBQL, Slide 17
3rd Country Conference, Feb.2007
Architecture of virtual repository
Future
eGov-Bus
applications
Workflow
application
Java
application
Web Service
application
Web Service
application
Client
view 1
Client
view 2
Client
view 3
Client
view 4
ODRA database server
Integration view
Communication Bus
Existing
sources
K.Subieta. Advanced Notions of SBQL, Slide 18
Contributory
view 1
Contributory
view 2
O-R
wrapper
O-RDF
wrapper
Relational
databases
RDF
resources
XML
importer/
exporter
XML
files
Contributory
view 3
Contributory
view
O-WS
wrapper
….
wrapper
Web Service
applications
….
application
3rd Country Conference, Feb.2007
Query optimization
• Lack of query optimization undermines the pragmatic goals of a
query language.
– Bad performance  no use the language
• The optimization requires discipline in the QL’s development:
– Occam’s razor: minimizing the data model, minimizing the number of
features of the QL, avoiding irregular treatment and special cases.
– Orthogonality of constructs, avoiding big syntactic monsters.
– Precise formal semantics of all query operators, allowing one to reason
on semantically equivalent queries and their performance.
• SBA, as a formal methodology of building OO query languages,
is exceptionally well prepared for query optimization.
– I believe that it is much better prepared than the relational model and
SQL.
K.Subieta. Advanced Notions of SBQL, Slide 19
3rd Country Conference, Feb.2007
Optimization methods for SBQL
• Methods based on rewriting:
– Factoring out independent subqueries, rules based on the distributivity
property, removing dead subqueries, query modification for processing
stateless functions and views, query tail absorption, …
• Methods based on indices:
– Involving dense and range indices, index management utilities.
• Methods based on query caching:
– Storing results of queries in order to reuse them.
• Pipelining, parallel execution of queries:
– Splitting a complex query processing into many parallel processes.
• Query optimization for distributed databases with horizontal
and vertical fragmentations.
• Heuristics and cost models concerning a query execution plan.
• Query optimization is the major topic of the research on SBA.
K.Subieta. Advanced Notions of SBQL, Slide 20
3rd Country Conference, Feb.2007
Conclusions
• To make a high quality model for object-oriented databases, the
specification of semantics is the must, …
– …to avoid the fate of SQL-99 and ODMG standards, perceived as
loose recommendations rather than technical specifications.
• SBA offers the unique method of query languages’ construction
and semantic specification.
– SBA is a holistic database theory, it doesn’t give up any, even the most
advanced feature of current practical O-O database query and
programming languages.
– Even smallest semantic problem is considered very important.
– Efficiency has been proven by several implementations.
• Alternatively, the new model can rely on the current well-known
theories concerning object-oriented databases.
– In such a case many qualities will be among nice wishes.
K.Subieta. Advanced Notions of SBQL, Slide 21
3rd Country Conference, Feb.2007
10 unique qualities of SBA/SBQL
1. Orthogonal syntax, full compositionality of queries.
2. Universal formal semantics based on abstract implementation.
3. Computational universality, advanced data structures,
integration with PL constructs.
4. Strong typing of advanced O-O queries and programs.
5. Several advanced implementations, further ones pending.
6. Fully transparent O-O virtual updatable views.
7. Strong potential for query optimization.
8. All O-O notions treated formally and uniformly.
9. Sound and manageable metamodel.
10. The potential for distributed query processing.
K.Subieta. Advanced Notions of SBQL, Slide 22
3rd Country Conference, Feb.2007
SBA/SBQL in projects
•
•
•
•
•
•
•
•
•
•
•
•
1989: NETUL – an expert system shell developed for Intra Video GmbH in West Berlin, Germany. Implementation
of SBQL for the M0 store model.
1990: LOQIS OO DBMS. Includes modules, elements of dynamic inheritance (M2 store model), typed objects,
transitive closures, recursive functions and methods, binding to C libraries and other features.
2002: SBQL for XML DOM. XML files are mapped to the M0 store model, then queried by SBQL. Results of
queries are returned as XML files. At that time the most powerful XML querying tool.
2003: YAOD – a prototype OODBMS. Client-server architecture with an advanced SBQL implemented for the M0
store model.
2004: European Project ICONS (commercialized). ICONS assumed an object-based database (no classes) on the top
of a relational database. SBQL was implemented on the client side. A powerful query rewriting optimizer was also
implemented.
2004: SBQL prototype for Objectivity/DB. A student project aiming at enhancing the Objectivity/DB OODBMS
with SBQL in the M1 store model.
2005: BPQL for OfficeObjects® Workflows (commercial). BPQL is a subset of SBQL embedded into XPDL, an
XML process definition language. A very successful project resulting in incredible flexibility (change potential) of
workflows implemented in Java+XPDL+BPQL.
2005: ODRA (Object Database for Rapid Application development). An OODBMS prototype under .NET written in
C#.
2005: (pending) ODRA/J: ODRA ported to Java for the M3 store model, with all the functionalities of SBQL,
imperative constructs and programming abstractions, classes, types, methods, inheritance, modules, recursive
querying capabilities, query optimization by rewriting and by indices, distributed query processing, and many other
advanced features.
2006: (pending) LoXiM – a client-server prototype OODBMS with SBQL, developed at the Warsaw University.
2006: (pending): European project eGov Bus. SBQL is to be used as an embedded QL for application programming
in Java. Alternatively, SBQL can be a self-contained DBPL for application programming. SBQL updateable views
will play the following roles: as mediators (adapting local resources to the global requirements), as integrators
(fusing fragmented collections) and as customizers (adapting the data to the needs of end users).
2006: (pending): European project VIDE. VIDE aims at developing a visual programming language for the OMG
MDA. We assume that OCL and other concepts related to Executable UML are to be implemented through SBA
concepts.
K.Subieta. Advanced Notions of SBQL, Slide 23
3rd Country Conference, Feb.2007