Stack-Based Architecture (SBA) and

Stack-Based Query Language (SBQL)


(many parts not completed yet)



by Kazimierz Subieta

back to SBA and SBQL home page






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

·        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

·        Description of the AS0 store model

·        Relationships of AS0 with other database models and concepts

·        The concept of binder

·        Function nested

·        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)

·        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

·        Description of the AS1 Store Model

·        SBQL for the AS1 store model

·        Examples of SBQL queries for the AS1 model

·        Description of the AS2 store model

·        SBQL for the AS2 store model

·        Examples of SBQL queries for the AS2 model

·        Sorting Operator in SBQL

·        Empty and Multi-Valued Keys

·        Sorting in Ascending and Descending Order

·        Alphabetic Order in Native Languages

·        Range Queries

·        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

·        Transitive Closures

·        Fixed Point Equations

·        Recursive Procedures and Functions

·        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

·        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?

·        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






Power Point file with all pictures



Last modified: February 24, 2010