©Copyright by Kazimierz Subieta.

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