Transcript Stack-Based Approach and Stack

Stack-Based Architecture and
Stack-Based Query Language
Presentation prepared for
1st International
Conference on Object Databases
Berlin, 13-14 March 2008
by
Kazimierz Subieta
Polish-Japanese Institute of Information Technology, Warsaw, Poland
SBA/SBQL pages: http://www.sbql.pl
K.Subieta. SBA & SBQL, slide 1
March 2008
State of the theory
• Books:
K.Subieta. Theory and
Construction of Object-Oriented
Query Languages
(522 pages – in Polish)
K.Stencel. Semi-strong Type
Checking in Object-Oriented
Database Programming Languages
(210 pages – in Polish)
• 20 years of research, ~ 80 research papers, 2 habilitations,
14 PhD-s (10 finished), several (>10) implementations
• We describe SBA and SBQL on http://www.sbql.pl
(work in progress)
K.Subieta. SBA & SBQL, slide 2
March 2008
What is SBA and SBQL?
• No border between querying and programming
– A single theory that uniformly covers both aspects
– Query languages are programming languages
• SBA offers a conceptual & semantic frame for queries and
programs involving queries
• SBQL is a model query & programming language according to
SBA
– It has the same role and meaning as object algebras, but it is
formally sound, semantically precise and more universal
• SBA deals with various data models and all reasonable query
constructs
– Including the most advanced OO models
K.Subieta. SBA & SBQL, slide 3
March 2008
Database models and SBA
• Database semantics depends on the assumed data model
• „Data model” is an ideological rather than technical notion
– People believe or not
– The relational database model is an ideology, supported by very
limited mathematical theories
– OO is an ideology, too.
• SBA is a theory supporting the OO database ideology
– But no limits
– Full algorithmic and pragmatic power
– All imaginable and reasonable query and programming constructs
• However, SBA is neutral to database models
– It deals with data structures rather than with data models
K.Subieta. SBA & SBQL, slide 4
March 2008
Abstract implementation
• … is a semantic specification method used in SBA
– A kind of operational semantics
– Denotational semantics abandoned due to heavy, obscure mathematics
• Abstract machine acting on abstract data structures:
– object store
– environment stack (thus Stack-Based Architecture)
– query result stack
• The structures are well-known in PLs
• Query operators (selection, projection, join, quantifiers, …)
can be precisely specified using the above abstract structures
• No loss for query optimization (just otherwise)
K.Subieta. SBA & SBQL, slide 5
March 2008
Features and functionality of SBQL
• All well-known database models, including the relational model,
XML and the most advanced OO models
• All well-known query operators
• Less known operators (transitive closures, fixpoint equations, ...)
• Updating statements integrated with queries,
• Procedures, functions and methods
– Recursive, with parameters being queries
• Object-oriented virtual updatable views
• Static (semi-) strong type checking
• Query optimization methods (indices, rewriting rules, …)
K.Subieta. SBA & SBQL, slide 6
March 2008
Query Languages as Programming Languages
• SBA adopts a run-time mechanism of PLs
– with necessary improvements
• 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).name
• All such expressions/queries can be used as:
– arguments of imperative statements
– parameters of procedures, functions or methods
– a return from a functional procedure
K.Subieta. SBA & SBQL, slide 7
March 2008
Naming, scoping, binding and ENVS
• 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
• Scopes are organized in an environment stack (ENVS) with the
“search from the top” rule
• All names occurring in queries & programs must be bound via
ENVS
– No name can be bound otherwise
K.Subieta. SBA & SBQL, slide 8
March 2008
SBA object store models
• SBA assumes a family of formal object store models which are
enumerated AS0, AS1, AS2 and AS3
• AS0 covers relational, nested-relational and XML-oriented
databases
– including complex objects and pointer links
• AS1 store model extends AS0 by classes and static (multiple)
inheritance
• AS2 store model extends AS1 by object roles and dynamic
inheritance
• AS3 store model extends AS1 or AS2 by encapsulation
K.Subieta. SBA & SBQL, slide 9
March 2008
Notions common to store models
1. Internal object identifier (OID)
–
–
–
Uniquely identifies an object in the store.
Assigned automatically, no external meaning.
Used as a reference or a pointer to an object.
2. External object name
–
–
–
Usually bears some external semantics of an object, e.g. Person,
Customer.
Explicitly assigned by a database designer, programmer, etc.
It is usually not unique, e.g. many objects named Person.
3. Atomic object value
–
–
–
Cannot be subdivided into smaller parts
E.g. 2, 3.14, “Doe”, “Hello, World!”.
The size is not constrained – from 1 bit to gigabytes.
K.Subieta. SBA & SBQL, slide 10
March 2008
SBQL objects
< i9, Emp, { < i10, name, ”Lee” >,
< i11, sal, 900 >,
< i12, address, { <i13, city, “Rome” >,
<i14, street, “Boogie” >,
<i15, house#, 13 > } >,
< i16, worksIn, i22 > } >
< i22, Dept, { < i23, dname, ”Ads” >,
< i24, loc, “Rome” >,
< i25, employs, i5 >,
< i26, employs, i9 > } >
K.Subieta. SBA & SBQL, slide 11
March 2008
SBQL query operators
• Algebraic operators do not use ENVS
–
–
–
–
–
arithmetic and string operators and comparisons
set-oriented operators
auxiliary naming operators
Boolean operators
…
• Non-algebraic operators use ENVS
–
–
–
–
–
selection (where),
projection, navigation, path expression (dot),
dependent join (join),
quantifiers,
…
• Non-algebraic operators cannot be expressed by any algebra
(in the style of the relational algebra)
K.Subieta. SBA & SBQL, slide 12
March 2008
Environment stack (ENVS)
– A.k.a. call stack
• For query processing we modified it
– It contains binders rather than objects
– A binder is a named reference to an object (but not only)
– The same object can be referenced from different stack sections
• ENVS has usually two forms: static (compilation) and dynamic
(run-time)
– Some properties of a static stack must be shifted to a dynamic stack
– Static stack necessary for strong typing and optimizations
• A new role of ENVS: processing non-algebraic operators
K.Subieta. SBA & SBQL, slide 13
March 2008
ENVS – example of state
bind( Emp ) = i1
bind( Y ) = i128
bind( I ) = ”Maria”
bind( sal ) = i11
bind( Dept) = {i17, i22}
K.Subieta. SBA & SBQL, slide 14
March 2008
Opening a new section of ENVS (1)
– In PLs opening a new scope on ENVS is caused by entering a new
procedure or entering a new block
– Respectively, removing the scope is performed when the control leaves
the body of the procedure/block.
• To classical situations we add a new one:
– Non-algebraic operators behave similarly to program blocks
– In query:
Emp where ( name = “Poe” and sal > 1000 )
the part ( name = “Poe” and sal > 1000 ) behaves as a program block
executed in an environment consisting of the interior of an Emp object.
– Binding must concern names name and sal
– Hence, we push on ENVS a section with the interior of the currently
processed Emp object (next slide)
K.Subieta. SBA & SBQL, slide 15
March 2008
Opening a new section of ENVS (2)
condition
Emp
where
binding
(name = ”Poe” and sal > 1000)
binding
name(i10) sal(i11)
address(i12) worksIn(i16)
Emp(i1) Emp(i5) Emp(i9)
Dept(i17) Dept(i22)
Initial ENVS state.
bind( Emp ) = {i1, i5, i9}
Interior of the
3-rd object Emp
Emp(i1) Emp(i5) Emp(i9)
Dept(i17) Dept(i22)
ENVS during evaluation of the condition
for the third object Emp.
bind( name ) = i10; bind( sal ) = i11
• Binder – a pair n(x), n is a name that can be used in a query, x is
some run-time entity (usually object identifier, but not only)
• Function nested – returning binders to the interior of a
processed object (generalized to other cases)
K.Subieta. SBA & SBQL, slide 16
March 2008
Classes, Roles and Inheritance
• AS1 introduces classes and static inheritance in the classical
variant known e.g. from modeling tools such as UML
• AS2 introduces dynamic object roles and dynamic inheritance
• AS3 introduces subdivision of class properties into public and
private
• The extensions imply small and obvious changes of the
behavior of ENVS concerning semantics of nonalgebraic operators
– For AS2 some new operators are necessary
K.Subieta. SBA & SBQL, slide 17
March 2008
UML-like schema (ODRA)
K.Subieta. SBA & SBQL, slide 18
March 2008
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 & SBQL, slide 19
March 2008
SBQL programs
• For each employee having no salary give the minimal salary in
his/her department:
for each Emp where not exists(sal) {
changeSal( min(worksIn.Dept.employs.Emp.sal) );
}
• A method:
changeSal( newSal: real ): boolean {
if not exists(self.sal) then
self :<< newSal as sal; //create and insert
else {
if self.sal > newSal then return false;
else self.sal := newSal;
}
return true;
}
K.Subieta. SBA & SBQL, slide 20
March 2008
Conclusions
• SBA is a universal theory that offers the methods of
semantic specification concerning OO databases
– SBA is a come back from various DB theories to the PLs theory
– SBA is holistic - it does not give up any (even the most advanced)
feature of current OO database QL & PL
– Proven by several advanced implementations
• SBQL is the most advanced OO QL ever invented
– With precisely defined formal semantics
– Strongly typed, optimized, PL capabilities, updatable views
• Currently, no theory concerning OO databases can
seriously compete with SBA
K.Subieta. SBA & SBQL, slide 21
March 2008