Stack-Based Architecture (SBA) and

Stack-Based Query Language (SBQL)

Description

(many parts not completed yet)

by Kazimierz Subieta

back to SBA and SBQL home page

Preface

Introduction to Object-Oriented Concepts in Programming Languages and Databases

· Motivation of object-orientedness

· Object-oriented concepts

· Objects

· Object identity, identifier, reference

· Object name

· Attributes

· Operations and methods

· Links (relationships, associations) between objects, pointers

· Classes

· Interfaces

· Types

· Polymorphism

· Dynamic object roles and dynamic inheritance

· Encapsulation and information hiding

· Modules

· Collections

· Persistence

· Impedance mismatch

· Complexity of a data model vs. complexity of queries (under construction)

· Principles of query/programming languages

· Flaws in formalization and construction of datamodels and corresponding query languages (under construction)

Basic Issues of SBA and SBQL

• What are query languages?
• Syntax, semantics and pragmatics of query languages

· Data model and database schema as inherent pragmatic parts of a query language

· Abstract syntax and syntax-driven semantics

· General assumptions of the semantics of query languages

· Completeness of query languages

• Abstract models of object stores
• AS0 Store Model: complex objects and links among objects

· Description of the AS0 store model

· Relationships of AS0 with other database models and concepts

• Environment stack, name scoping and binding
• Environment stack (ENVS) in AS0

· The concept of binder

· Function nested

• Results returned by queries and the query result stack (QRES)
• General architecture of query processing
• SBQL syntax
• Query evaluation through recursive procedure eval
• SBQL algebraic operators

· Operators and comparisons for primitive types (numbers, strings, booleans, etc.)

· Aggregate functions, removing duplicates

· Operators and comparisons on collections (union of bags, concatenation of sequences, etc.)

· Coercions and dereferences

· Conditional queries (operator if)

· Defining auxiliary names (operators as and group as)

• SBQL non-algebraic operators - general semantics

· Procedure eval for non-algebraic operators

· Selection

· Projection, navigation and path expressions

· Dependent/navigational join

· Existential and universal quantifiers

Examples of SBQL queries and comparison with SQL and OQL

Advanced issues in SBA and SBQL

• AS1 store model: AS0 + classes and static inheritance

· Description of the AS1 Store Model

· SBQL for the AS1 store model

· Examples of SBQL queries for the AS1 model

• AS2 store model: AS1 + dynamic object roles and dynamic inheritance

· Description of the AS2 store model

· SBQL for the AS2 store model

· Examples of SBQL queries for the AS2 model

• The order by operator and range queries

· Sorting Operator in SBQL

· Empty and Multi-Valued Keys

· Sorting in Ascending and Descending Order

· Alphabetic Order in Native Languages

· Range Queries

• Why the group by operator is not necessary in object query languages

• Storing and processing irregular data (semi-structured data)

· Null Values

· Variants

· Current Proposals Concerning Irregular Data

· Irregular Data in Theories

· Irregular Data in Object Databases

· Date’s Default Values

· SBA - Approach to Irregular Data

· Querying Optional Data, Variants and Repeating Data

· Capabilities Equivalent to Outer Joins

· Default Values in SBA

· Possibility of False Binding

· Assignment to Absent Object

· Typing Irregular Data in SBQL

· Irregular Queries

• Recursive Queries in SBQL

· Transitive Closures

· Fixed Point Equations

· Recursive Procedures and Functions

• Imperative Constructs in SBQL

· Declarations of Objects

· Creating Objects

· Locations of Created Objects

· Deleting Objects

· Assignment

· Inserting Objects

· Changing Object Name

· Control Statements (if, case, while, for, for each)

· Low-level Iterators

• Procedures and Methods in SBQL (under construction)

· Parameters of procedures, functions and methods in SBQL

· Call-by-value

· Call-by-reference and call-by-value-return

· Strict-call-by-value

· Calling with labeled actual parameters and defaults

· Call-by name and call-by-need

· Functional procedures vs. database views: are they similar concepts?

• AS3 store model: (AS1 or AS2) + encapsulation

· Description of the AS3 store model

· SBQL for the AS3 store model

· Examples of SBQL queries for the AS3 model

• Scoping rules
• Recursion in SBQL procedures, functions and methods
• Optimization through query modification
• Virtual updateable views

· Critique of view updateability criteria and current approaches to views

· The relativity principle for views

· View definition

· Seeds of virtual objects

· Virtual identifiers

· Procedures overloading generic updates on virtual objects

· Sub-views

· Examples of updateable views

· Optimization of queries invoking views

· Comparison with relational views based on instead of triggers

• Static type checking of SBQL queries and programs

· Abstract query syntax tree

· Types and database schemata

· Metabase

· Static and dynamic typechecking

· The concept of type and types in query languages

· External and internal type system

· Type signatures and attributes of signatures

· Static environmental (S_ENVS) and result stacks (S_QRES)

· Typechecking decision tables (type inference rules)

· Involving general rules such as subsitutability (inclusion polymorphism)

· The static_type_check recursive procedure

· Restoring the typechecking process after a type error

· Automatic coercions, ellipses, dereferences and dynamic typechecking

· Typechecking of imperative constructs

· Typechecking of procedures, functions and methods

· Typechecking of updateable views

· Typechecking of dynamic object roles

· Typechecking and encapsulation

· Dynamic typechecking of objects

· Referential types

· Parameterized types (parametric polymorphism)

· Proposal of an external type system for SBQL

• Query optimization

· General observations concerning query optimization methods

· Why object algebras, object calculi, etc. are wrong ideas

· Query evaluation cost models

· Optimizations supported by data organization and access

· Method of independent subqueries

· Methods based on the distributivity property of query operators

· Methods based on indices

· Removing dead subqueries

· Pushing selections before structure constructors

· Method of weakly dependent subqueries

· Queries with large and small collections

· Optimization through caching results of queries

· The order of query optimization methods and general strategies

· Pipelining and distributed query optimization

Some research topics (currently being developed by SBA/SBQL folks)

· Grid databases: integration of distributed, heterogeneous and redundant resources on the ground of virtual updateable objects views

· External type systems and metamodels for grid databases

· Aspect-oriented databases and overloading views

· Processing and optimization of SBQL queries in grid databases

· Wrappers and mediators for legacy databases (relational, document, XML, etc.) based on SBQL views

· Three-level database architecture and SBQL views as interfaces

· BPQL - a workflow query language based on SBQL for tracking, monitoring and dynamic process changes

· SBQL as a querying tool in P2P networks

· SBQL as a querying tool in e-learning systems

· Distributed linear hashing indices and integration of them with the SBQL engine

· Semi-strong typechecking for query languages addressing semi-structured data

· SBQL as a querying tool in the OMG Model Driven Architecture

· OCL as stack-based querying tool in OMG MDA

References

Power Point file with all pictures

Last modified: February 24, 2010