A Stack-Based Approach to Query Languages^{∗}

Kazimierz Subieta^{▷}  Catriel Beeri^{•}  Florian Matthes^{⋄}  Joachim W. Schmidt^{⋄}

▷) Institute of Computer Science Polish Academy of Sciences Ordona 21 01-237 Warszawa, Poland subieta@wars.ipipan.war.pl

•) Hebrew University Institute of Computer Science Givat Ram, Jerusalem 91904, Israel beeri@cs.huji.ac.il

⋄) University of Hamburg Department of Computer Science Vogt-Kölln-Straße 30 D-22527 Hamburg, Germany matthes@dbis1.informatik.uni-hamburg.de

Abstract Scoping, naming and binding are central concepts in the definition and understanding of programming languages. With the introduction of sophisticated data models, these issues become important for query languages as well. Additionally, the goal of integrating query and programming languages requires a common basis for their operational semantics. We offer here an approach to the definition of the operational semantics of query languages based on an abstract machine, in which names, their bindings, and scopes defined by query and data structure are central. The machine has own simple data model for its store, and has a stack for dealing with scopes. We argue for the generality of the approach and illustrate it by defining the semantics of many query language primitives. Finally, we briefly consider how assignment and procedures can be neatly added.

1 Introduction

A major theme of database research in the last decade is the relationship between declarative, high level query languages and procedural, general purpose programming languages. The standard solution, namely embedding a query language (typically SQL) in the programming language suffers from problems that have been amply recorded in the literature and collectively called impedance mismatch. Alternative approaches that have been proposed and extensively investigated include persistent programming languages and database programming languages such as Pascal/R [?], Galileo [?], DBPL [?, ?], Napier88 [?], Machiavelli [?], Taxis [?], and O_{2}C [?]. The emergence of object-oriented databases is also due, in part, to the feeling that classical database systems do not provide the functionality desired and required for data intensive application development.

Despite their limited algorithmic expressive power, query languages are one of the major achievements of the database domain [?, ?, ?]. This is not only because they are the means for ad hoc interactive querying and updating of a database, but rather because they are the basis for high level, declarative, data independent data definition and manipulation. In data manipulation, declarative queries are much easier to optimize than procedural programs. Queries are also potentially parallelizable. The use of queries and set-oriented updates increases programmers’ productivity, and program reliability, readability and modifiability. In data definition, queries are used to express integrity constraints, access restrictions, views, snapshots, database procedures, and active rules. However, despite continuous advances in research and development of database languages and object-oriented database systems, the ideal of “seamless integration” of a programming language with a query language is still elusive.

A primary goal of this paper is to contribute to the understanding of the relationship between query and general programming languages. A major thread in the development of programming languages concerns facilities for modularity, as expressed, e.g., in procedural abstraction in the form of functions and procedures, and data abstraction in the form of ADT’s and objects. The use of such facilities emphasizes the relationships between names used in a program, their scope of definition, and the bindings they receive at compile and run-time. We believe that the study of names, scopes, and bindings is also important for the design and use of query languages. Understanding of the relevant issues is a crucial step towards the successful integration of query and programming languages. The issue is important even if one is interested in query languages only for the relational model, since a query may use a relation name or an attribute more than once with different meanings. However, in the last decade many query languages for more sophisticated models have been defined and studied. In such models, the meaning of a name depends both on where it is defined and where it is used.

∗Work partially supported by a grant from the German-Israel Foundation for Scientific Research and Development.

Draft, October 12, 1994

This paper proposes an approach to the definition of the operational semantics of query languages centered around the naming-scoping-binding theme. Specifically, we present an abstract machine that we claim to be suitable for the definition of program data bindings. An important component of the machine, that distinguishes it from other machines, is its store, modelling the database as a collection of related entities associated with names to which they can be bound. The store can also contain volatile objects. It is defined in terms of a simple object model. We argue that the simplicity of the model makes our work applicable to a variety of current data models.

The actual binding of names appearing in queries to store objects is achieved by the use of environments, where an environment is a collection of local scopes and rules used for associating names with programming objects. The common approach, which we follow here, is that the scopes are organized in a stack, with the “search from the top” rule. Some extensions to the structure of stacks used in the definition and interpretation of programming languages are necessary to accommodate, e.g., the fact that in a database we have bulk data structures, hence possibly multiple simultaneous bindings for a name. This environment stack, and a procedure for evaluation of queries, are the backbone of our approach. An important aspect of the evaluation is parallelism which is inherent in many query primitives, and important for proper definition of update semantics.

The machine and the semantics of a query language are derived from a language implemented in the system LOQIS [?]. However, majority of constructs that we considered exists also in other query languages. In the paper we illustrate how the machine can be used to provide a precise definition of the semantics of some query constructs. (A more comprehensive presentation can be found in [?]). We also illustrate the design of a query language that is directly influenced by the stack-based discipline of scoping and binding. Finally, we briefly consider updates and procedures, thus supporting our claim that this approach facilitates the integration of declarative and procedural constructs.

The rest of the paper is organized as follows. In Section 2 we discuss the abstract store model and present preliminary formal definitions. In Section 3 we discuss the abstract machine model, introducing details of the operational semantics used for the specification of language constructs. In Section 4 we present and discuss various query constructs. In Section 5 we discuss updates and procedures. Section 6 concludes.

2 An Abstract Store Model

The store is the component of the abstract machine that models the database. The operational semantics of queries is defined to a large extent in terms of accesses and manipulations of its elements. The store model and its relationship to other data models are described below.

2.1 The Goals

The primary goal is to serve as a basis for defining the operational semantics of query languages. The model does not include details of physical data organization, indices, storage hierarchies, and buffer management. We view a database as a large collection of (possibly interrelated) entities, as it can be found in modern persistent object stores [?, ?]. The store may contain both persistent and volatile entities; we strive to treat them uniformly.

Current implemented or proposed data models include a large variety of features: data types such as records and arrays; bulk data types such as sets, bags, lists, maps and trees; object features such as identity, is-a relationships, methods and encapsulation. We want our approach to semantics to be applicable to a wide range of query languages. One possible approach to addressing this diversity of concepts is to define a rich model that contains “all” features. We have chosen the opposite approach of a very simple model, where various conceptual models, from value-based to object-based, can easily be mapped to it. Semantics for a specific query language over a given model can be defined by a mapping to our model, and by providing the semantics in our model. Although some features found in existing models have no direct mapping to our model, it covers a large variety of features and can be easily extended. The approach presented in this paper can also be adapted directly (without translation) as another data model.

The ideas treated in the paper do not require a specific (monomorphic, polymorphic) type discipline nor precise data representation details. Types are very important for enforcing static constraints on the use of queries and procedures; however, they are irrelevant to the goals of this paper, hence are not discussed.

2.2 The Model

Intuitively, a stored database (at a given point of time) consists of a collection of stored entities which we call store objects^{1}. There are three components in a store object: (1) its location; (2) the name that can be used to denote it; (3) the value stored there, i.e., its content. As we are not interested in physical organization, we represent locations abstractly, using the concept of l-value from programming language semantics. Atomic values, records, components of records, conceptual objects, are all store objects: each one of them resides somewhere in memory and needs location for internal identification, in order to be retrieved, updated or deleted. For us, these locations have no structure or meaning, except that they can be used to access objects; queries do not refer to them or use their values in any way. In the sequel, to emphasize their abstract nature, locations are called identifiers.

Names are among the basic building blocks of queries and, in general, of program expressions. Their bindings are an important component of semantics, and a central topic in this paper. While for general programming languages names used in a program are normally defined in the program itself, most of the names used in queries are defined in the database. That is, we are dealing with persistent data where names are an inherent part.

The contents (i.e., the r-value) can be an atomic or complex value, or a location. As for the names, we assume that each store object contains one value. As seen below, more than one value associated with an object is modelled by creating many objects.

Formally, let I be a set of identifiers, N be a set of names, and V be a set of atomic values. We make no assumption about V; it may contain numerals, strings, graphics, compiled procedures, and so on. Atomicity of the elements of V means that we do not assume the existence of operations that refer to their parts. We assume I ∩ (V ∪ N) = ∅; however, N and V are not required to be disjoint. It is possible, even common, that programs compute values, then use them as names, e.g., integers are used as array indices. Generally, some stored values can be used as names of store objects; this property supports genericity of programming. In many languages, for example Ingres/Windows 4GL [?], LOQIS [?] and F-logic [?], data names are first-class citizens.

A store object is a triple < i, n, ϑ >, where i ∈ I, n ∈ N, and ϑ are its identifier, name, and value, respectively. We say that i identifies this object. The value ϑ can be one of the following:

• An atomic value from V.

• An identifier from I. This identifier, as the value of the store object, serves as a (logical) pointer to another store object.

• A set of objects.

We refer to these three types of objects as value-objects, pointer-objects, and set-objects, respectively. Objects of the first two types are called atomic, those of the third type are called complex. Nesting of set-objects allows us to represent arbitrarily complex objects with hierarchical structure. Below is an example of a complex object, consisting of three atomic objects.

< i_{5}, EMP, { < i_{51}, NAME, Smith >,
< i_{52}, SAL, 2000 >, < i_{53}, W ORKS IN, i_{6} > } >

In the following, “object” always means store object, unless specifically noted otherwise.

A store is a set S of store objects, and set R of identifiers of designated root objects. We make no assumption that elements of R refer to the top hierarchy level of store objects: sometimes elements of R refer to objects nested in other objects. We assume that S satisfies the obvious constraints: An element i ∈ I is used in it at most once as an identifier; that is, there is a one-to-one correspondence between the set of identifiers used in a database, and the set of objects in it. If an identifier is used as a pointer, then it is also used as an identifier (referential integrity). We also assume that each root identifier actually identifies an object in S. By definition, objects inaccessible from R (directly or indirectly) do not exist. As we will see later, we build over the set R some structure which we will call environment stack. The persistence status of objects is irrelevant in our approach; indeed, there is no essential semantic property that can make distinction between querying persistent and volatile data. (The orthogonality of types, queries and persistence is assumed in many modern DBPLs [?, ?, ?, ?, ?, ?].)

1These should not be confused with the conceptual objects of object-oriented models.

We re-emphasize that the identifiers are internal – they are not used in queries or programs, and are not printable. A one-to-one mapping of all identifiers to another collection of identifiers cannot be recognized from the outside. The names are external in the sense that they are used in queries – they are part of the users’ model.

Example 2.1 The following is an example store. The root objects are

{i_{1}, i_{5}, i_{9}, i_{13}, i_{17}}.

MyDatabase:

< i_{1}, EMP, {< i_{2}, NAME, Brown >,

< i_{3}, SAL, 2500 >, < i_{4}, W ORKS IN, i_{13} >} >

< i_{5}, EMP, {< i_{6}, NAME, Smith >,

< i_{7}, SAL, 2000 >, < i_{8}, W ORKS IN, i_{17} >} >

< i_{9}, EMP, {< i_{10}, NAME, Jones >,

< i_{11}, SAL, 1500 >, < i_{12}, W ORKS IN, i_{17} >} >

< i_{13}, DEP T, {< i_{14}, DNAME, T oy >,

< i_{15}, LOC, P aris >, < i_{16}, LOC, London >} >

< i_{17}, DEP T, {< i_{18}, DNAME, Sales >,

< i_{19}, LOC, Berlin >} >

Note that an object WORKS IN stores an identifier of a department object. If instead it contained, say, a department name, the example would be value-based. If additionally we disallow multiple LOC objects for a department, we obtain a relational database. □

In examples we also use the schema presented in Fig.1. It has redundancy allowing us to demonstrate different styles of querying, e.g. relational and navigational. Arrows denote pointers, and symbols 1 and n denote a 1:n relationship. For example, EMPLOYS denotes pointer-objects inside DEPT objects; a DEPT objects can contain many EMPLOYS objects. Similarly, LOC and PREV JOB are multi-valued attributes.

2.3 Discussion

Having defined the model, let us now consider how databases given in one of the common conceptual models can be represented in it. In the relational model, to represent information about employees, we may use a relation, i.e., a set of tuples, called EMP. Considering the execution of the query select SAL from EMP, we can see that the name EMP gets bound to each tuple of the relation. As we are interested in names in the context of binding, in our model the name EMP is associated not with the relation, but rather with each of its tuples. This holds in general for any named set: in our model the name is associated with each of the elements of the set; see, e.g., LOC of DEPT in MyDatabase.

Speaking in terms of programming languages, a tuple defines a local environment: each attribute is a name that, in the context of this tuple, can be bound to the associated object – attribute value. Note that we do not have tuple as a data structure in our model – as just seen, a tuple is represented by the set of its named components. Also note that the identifier of the object representing the tuple is internal and has nothing to do with the conceptual model, in which this tuple is a value, not an object. It is

Figure 1: A database schema used in examples

just an abstract representation of the fact that the tuple is an identifiable store object. (Many relational systems indeed use tuple-id’s internally.)

Names can be numbers. For example,

< i_{1}, A, {< i_{2}, 1, Monday >,

< i_{3}, 2, T uesday >, …, < i_{8}, 7, Sunday >} >

represents an array. Thus, tuples and arrays have essentially the same representation. Indeed, both are essentially local environments, and the differences have to do only with the type and generation of the names that can be used in the environment. As already noted, names used in arrays are also values, and can be calculated during run-time.

We do not impose constraints requiring that objects with the same name should have the same structure. This allows us to represent variants, as in the following database fragment:

< i_{1}, EMP, {< i_{2}, NAME, Brown >, < i_{3}, SAL, 2500 >} >
< i_{6}, EMP, {< i_{7}, NAME, Smith >, < i_{9}, IS ST UDENT, T RUE >} >

Similarly, we can represent null values, when they mean lack of stored information. Since the definition of a store does not include any concept of format, a null value is represented simply by the absence of a binding. For example, in the database fragment above, the SAL field for Smith is null-valued. We do not associate any semantics with this absence. As far as we are concerned, Smith may have no salary, or his salary may be unknown, or it may be determined in another way, e.g., by using the information that he is a student. The interpretation of the absence of information is part of the semantics of the data, but is outside of the scope of our model. Of course, we need the ability to test for the lack of a stored object with a given name, so that the query evaluator can interpret this and apply the appropriate semantics.

To generalize to the nested relational, or complex object models, we need to be able to represent sets, and obviously we have that in the model. We can also represent bags. For example, the object < i_{1}, N, {< i_{2}, M, 5 >, < i_{3}, M, 5 >} > represents the bag {5, 5}. Similarly one can represent lists, trees, and generally, instances of recursively defined data types.

Let us now consider a conceptual object. It has an identity, and an updatable state. The mapping is straightforward – an object is represented as a store object. Object sharing and relationships between objects can be easily mapped by using internal object identifiers as values of pointer sub-objects, as seen in MyDatabase above.

In summary, this simple model allows one to represent a variety of data structures and concepts, and their combinations, including tuples, arrays, sets, bags and lists, variants, null values; objects, object sharing, and instances of recursive types. For object-oriented models some simple extensions are needed; we discuss them in [?]. However, we believe that the simplicity of the model is an advantage: it allows us to explain the meaning of query constructs without having to deal with a variety of special cases.

3 An Abstract Machine Model

In this section we present an abstract machine model, on which query language expressions can be evaluated. A component of a state of the machine is a store, as described above. Other components include an environment stack and a result stack for the store of intermediate results. We discuss some commands of the machine, and its facility for parallel execution.

3.1 The Environment Stack

The atomic components of queries are the names and constants. The evaluation of names means binding them to data units, depending on the context. Consider, for example, a query in a relational database that asks for the names of employees satisfying some condition:

select NAME from EMP where …

The evaluation of the query involves finding a set of bindings for EMP, then removing some of them which do not satisfy a predicate after where. Each binding for NAME is then determined in a context associated with one of the bindings to EMP; it is bound to the appropriate NAME sub-object inside an EMP object.

3.1.1 Stack Organization

While bindings for simple relational queries, such as the one above, seem to be well understood, this is not the case for more complex queries. For example, in a query that selects the salaries of employees that earn more than their managers, SAL is used three times, and there is a need to define how each occurrence is bound. The problem is aggravated in models that admit deeply nested structures, possibly, with repeated (sub) attributes. The binding of a name to its meaning may then depend both on the positions of the name in the data structure, and its use in the query.

To deal with this issue, we propose a well known concept of environment. Abstractly, an environment is an association of names and objects. It is constructed incrementally, by accumulating local scopes and the scope added last is the first to be visited in a search. Thus, the environment is subdivided into parts, called sections, which form the environment stack, denoted ES.

We assume that each section of ES stores identifiers of store objects. Given an identifier, the complete object can be retrieved. In particular, the name stored in the object can be retrieved, to be compared with the name for which a binding is requested. Thus, storing identifiers suffices for establishing bindings.

In a (run-time) stack in programming languages a stack section typically contains local data such as parameters and local variables of a procedure. Such local data lives on the stack. In contrast, we are dealing here with global data, that live in the database, and continue to exist not only when a stack section is removed, but also when query evaluation has terminated and the complete stack has disappeared. Thus the objects themselves will be stored in the store, and their identifiers stored in the appropriate stack section(s). This scheme allows the same object to be referenced from several sections (in contrast to the run-time stack where an object occurs in precisely one section). The semantics we are going to deal with depends on this property. Note that in a run-time stack a name occurring in a program is bound to one object. In contrast, we allow a section in ES to associate several objects with a name, as e.g. for the EMP name.

In summary, our proposal generalizes the environment stack as used in programming languages in two major ways: (1) The stack contains identifiers of both persistent and volatile store objects, which exist outside the stack; (2) Binding is a multi-valued, rather than a single-valued. This is intimately related to the set orientation and parallelism inherent in query semantics.

In an implementation based on our semantics many optimizations are possible, such as storing names with the identifiers in sections, avoiding long lists of identifiers of objects having the same name, and performing some bindings during compilation. Some of these optimisations are implemented in LOQIS; they are not discussed here.

We assume that at the beginning of the evaluation of a query the environment stack consists of one section containing identifiers of all persistent root database objects, such as the EMP and DEP T objects in MyDatabase.