Transcript SBA (Stack-Based Approach) and SBQL (Stack

Stack-Based Approach and
Stack-Based Query Language
- Overview
Presentation prepared for the OMG Analysis & Design Task Force (ADTF)
OMG TECHNICAL MEETING, Brussels, Belgium
June 25th-29th, 2007
by
Prof. Kazimierz Subieta
Polish-Japanese Institute of Information Technology, Warsaw, Poland
[email protected]
http://www.ipipan.waw.pl/~subieta
SBA/SBQL pages: http://www.sbql.pl
K.Subieta. SBA and SBQL, slide 1
June 2007
Topics
•
•
•
•
•
•
•
•
•
•
•
What is SBA?
What is SBQL?
SBA/SBQL database models
Abstract implementation as semantic specification
The idea of SBA
Naming, scoping, binding and environment stack
SBA/SBQL data store models
SBA/SBQL in recent (pending) projects
ODRA architecture
SBQL queries and programs (examples)
Unique qualities of SBA/SBQL
K.Subieta. SBA and SBQL, slide 2
June 2007
What is SBA?
• The Stack-Based Approach (SBA) is a formal methodology
addressing object-oriented query and programming languages.
• In SBA we reconstruct query languages’ concepts from the point
of view of programming languages (PLs).
– No definite border line between querying and programming; thus there
should be a universal theory that uniformly covers both aspects.
• SBA offers a unified and universal conceptual and semantic
basis for queries and programs involving queries – including programming abstractions such as procedures, functions,
classes, types, methods, views, etc.
K.Subieta. SBA and SBQL, slide 3
June 2007
What is SBQL?
• SBQL (Stack-Based Query Language) plays the same role for
object models as the relational algebra for the relational model.
• However:
– SBQL is incomparably more powerful - this concerns universality of
data models and complete algorithmic power.
– SBQL is much more powerful than OQL, OCL and XQuery (at least
concerning o-o data model, updating capabilities, program control
facilities, programming abstractions and virtual o-o views).
– SBQL is fully precise w.r.t. the specification of semantics.
– SBQL (in contrast to SQL and OCL) is free of parasite syntax.
– SBQL has been carefully designed from the pragmatic point of view.
– SBQL is strongly (statically) and semi-strongly typed.
– SBQL has advanced query optimization methods.
K.Subieta. SBA and SBQL, slide 4
June 2007
Pragmatic quality of SBQL
• It is achieved by:
–
–
–
–
–
–
–
–
–
–
Orthogonality of introduced data/object constructors,
Orthogonality of all the language constructs,
Object relativism,
Orthogonal persistence,
Typing safety,
Introducing all the classical and some new programming abstractions
(procedures, functions, modules, types, classes, methods, views, etc.),
Clean formal semantics,
No semantic reefs,
No far context dependencies,
Following commonly accepted programming languages’ principles.
K.Subieta. SBA and SBQL, slide 5
June 2007
SBA/SBQL database models
• SBA and SBQL are neutral to database models.
• SBA covers all database models that we are aware of:
– Relational and nested-relational models,
– XML and RDF models,
– Object-oriented models with static (UML-like) and dynamic
inheritance,
– Collections, associations, encapsulation, polymorphism, etc.
• SBA and SBQL address data structures rather than data
models.
– When a concept in a data model is mapped as an abstract data
structure, a corresponding feature of SBQL can handle it.
• SBQL is the first and only query language that deals with
dynamic object roles and dynamic inheritance.
K.Subieta. SBA and SBQL, slide 6
June 2007
Abstract implementation as semantic specification
• It is a kind of operational semantics based on abstract data
structures that participate in query/program processing
• SBA introduces three well-known structures:
– object store,
– environment stack (thus Stack-Based Approach),
– query result stack.
• These structures are fundamental for precise semantic
description of everything that may happen in database
query/programming languages.
– Classical query operators, such as selection, projection, joins and
quantifiers, can be generally and precisely specified.
– We abandon (poor) database theories such as object algebras or calculi.
K.Subieta. SBA and SBQL, slide 7
June 2007
The idea of SBA
• The SBA solution relies on adopting a run-time mechanism of
PLs and introducing necessary improvements to it.
• The main syntactic decision is the unification of PL expressions
and queries - no conceptual difference:
–
–
–
–
2+2
(x+y)*z
Employee where salary = 1000
(Employee where salary = (x+y)*z).surname
• All such expressions/queries can be used as:
– arguments of imperative statements,
– parameters of procedures, functions or methods
– a return from a functional procedure (from a method).
K.Subieta. SBA and SBQL, slide 8
June 2007
Naming, scoping, binding and environment stack
• Each name occurring in a query is bound to run-time
programming entities (persistent data, procedures, actual
parameters of procedures, local procedure objects, etc.), according
to the actual scope for the name.
– The common PLs’ approach is that the scopes are organized in an
environment stack with the “search from the top” rule.
– Some extensions to the structure of stacks used in PLs are necessary.
• Abstract implementation of query operators, imperative
programming constructs and procedures (functions, methods,
views, etc.) is defined in terms of the mentioned abstract
structures:
– object store,
– environment stack,
– query result stack
K.Subieta. SBA and SBQL, slide 9
June 2007
SBA/SBQL data store models
• SBA/SBQL assumes a family of formal object store models
which are enumerated M0, M1, M2 and M3.
• The simplest is M0, which covers relational, nested-relational
and XML-oriented databases.
– M0 assumes hierarchical objects with no limitations concerning the
nesting of objects and collections. M0 also covers pointer links
(relationships) between objects.
• M1 store model extends M0 by classes and static (multiple)
inheritance.
• M2 store model extends M1 by object roles and dynamic
inheritance.
• M3 store model extends M1 or M2 by encapsulation.
K.Subieta. SBA and SBQL, slide 10
June 2007
SBA/SBQL in recent (pending) projects
• ODRA (Object Database for Rapid Applications) - queries, imperative
constructs, programming abstractions, classes, types, methods, inheritance,
modules, query optimization,...
• European project eGov Bus. Integrating distributed resources being
under control of various European governmental institutions.
– SBQL as an embedded QL for application programming in Java.
– SBQL as self-contained DBPL for application programming.
– Virtual repository based on SBQL virtual updateable OO views
• European project VIDE - developing a visual programming language
for the OMG MDA.
– OCL and other concepts related to Executable UML are implemented
• XML2XML mapper based on SBQL
K.Subieta. SBA and SBQL, slide 11
June 2007
ODRA
Architecture
K.Subieta. SBA and SBQL, slide 12
June 2007
SBQL object (ODRA)
K.Subieta. SBA and SBQL, slide 13
June 2007
SBQL schema (ODRA)
K.Subieta. SBA and SBQL, slide 14
June 2007
SBQL queries
• Get all information on departments for employees named Doe:
(Emp where lName = “Doe”).worksIn.Dept
• Get the name of Doe’s boss:
(Emp where lName = “Doe”).worksIn.Dept.boss.Emp.lName
• Names and cities of employees working in departments managed by Kim:
(Dept where (boss.Emp.lName) = “Kim”).employs.Emp.
(lName, if exists(address) then address.city else “No address”)
• For each employee get the name and the percent of the annual budget of
his/her department that is consumed by his/her monthly salary:
Emp . (lName as n, (((if exists(sal) then sal else 0) as s).
((s * 12 * 100)/(worksIn.Dept.budget)) as percentOfBudget)
K.Subieta. SBA and SBQL, slide 15
June 2007
SBQL programs
• For each person having no salary give the minimal salary in his/her
department:
for each (Emp where not exists(sal)) as e do {
e.changeSal( min(e.works_in.Dept.employs.Emp.sal) )}
• A method:
changeSal( newSal: real ): boolean {
if (not exists(self.sal)) then {
sal: real[0..1];
self :< create sal(newSal);
}
else {
if (self.sal > newSal) then return false;
else self.sal := newSal;
}
return true;
}
K.Subieta. SBA and SBQL, slide 16
June 2007
Conclusions
• To make a high quality standard 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 QL/PL.
• Michi Henning, ZeroC: „No standard should be approved without a
reference implementation.
– This provides a first-line sanity check of what is being standardized.
– No one is brilliant enough to look at a specification and be certain that
it does not contain hidden flaws without actually implementing it.”
• SBQL has been implemented more than 10 times, for different
systems and purposes.
K.Subieta. SBA and SBQL, slide 17
June 2007
10 unique qualities of SBA/SBQL for a new
O-O database standard
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, next are 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. SBA and SBQL, slide 18
June 2007
Acknowledgement
• This work is supported by the European Commission 6-th Framework
Programme, Project VIDE - VIsualize all moDel drivEn programming, IST
033606 STP
• VIDE Participant List (in random order)
– SAP AG (Germany)
– SOFTEAM (France)
– Institute for Information Systems at the German Research Center for
Artificial Intelligence (Germany)
– IESE Fraunhofer (Germany)
– Polish-Japanese Institute for Information Technology (Poland, coordinator)
– FIRST Fraunhofer (Germany)
– TNM Software GmbH (Germany)
– Bournemouth University (United Kingdom)
– Rodan Systems S.A. (Poland)
– ALTEC (Greece)
K.Subieta. SBA and SBQL, slide 19
June 2007