SBQL for the AS0 Store Model -
Query Result Stack (QRES)
by Kazimierz Subieta (February 2006)
Back to Description of SBA and SBQL.
The query result stack (QRES) is necessary to accumulate temporary and
final query results. As in the case of ENVS, the stack is a client-side main
memory data structure. In contrast to ENVS, QRES is not a component of the State, because the
result of query evaluation does not depend on the state of this stack. QRES is
purely abstract data type, that is, it can be managed by four abstract
operations:
·
void: push(
newSection: queryResultType ) - push a new section above the top,
·
void: pop(
) - remove the top,
·
queryResultType: top( ) - read the top section,
·
boolean: isEmpty(
) - check if the stack is empty.
Each QRES section contains a query
result, as defined in a previous page. Thus QRES is a straightforward
generalization of an arithmetic stack
known from implementation of programming languages and construction of computer
hardware. Fig.22 presents subsequent states of the arithmetic stack during
calculation of a simple expression. At the beginning the stack is empty. The
final state contains the result of the expression.
Fig.22. States of the arithmetic stack during calculation
In
implementation QRES can be also used for other purposes, for instance, to keep
counters of iteration loops during processing collections.
QRES is not a necessary concept of a
programming or query languages’ semantics. In some formulations, e.g. in
the denotational semantics or expressing the semantics by recursive procedures,
it disappears. However, in the operational semantics it is a very useful
concept, as it allows one to explain precisely what is actually done within the
abstract implementation machine. The advantages of the explicit QRES stack
concept are the following:
·
It
makes the definition of semantics highly intuitive. Our experience with
explaining the denotational semantics for average developers and programmers is
extremely negative. We didn’t discover any essential advantage of this
specification style (except it is excellent to write a next paper to a next
theoretical conference).
·
The
stack concept makes it possible to reduce the distance between abstract
specification and concrete implementation. It is a useful element of the abstract implementation paradigm that we
follow in our presentation of SBA.
·
The
stack is associated with its static counterpart (S_QRES - it will be introduced
much later) that is managed during query compilation. The static result stack
is an inevitable feature of strong static type checking and query optimization
methods.
Operations on QRES affect only its top, other
stack sections are invisible. A section becomes visible after popping a proper
number of top sections. Fig.23 presents an example state of the stack in SBA.
Fig.23. Example of a QRES state
After evaluation of a query the top of QRES
contains the final query result. This result is consumed by some agent within the
application software, e.g. by a print
command, by a graphical user interface, by an updating or deleting clause, etc.
Providing the application is free of inconsistencies, the beginning state of
QRES is empty and the final state of QRES is empty too (all results of queries
are consumed by the application software).
Last modified: December 31, 2007