\section{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 {\em
impedance mismatch}.  Alternative approaches that have been
proposed and extensively investigated include persistent
programming languages and database programming languages such as
Pascal/R \cite{Schm77}, Galileo \cite{ACO85}, DBPL
\cite{ScMa92,MRSS92a}, Napier88 \cite{MBCD89}, Machiavelli
\cite{OBB89}, Taxis \cite{MBW80}, and O$_2$C \cite{O2Ma92}.  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 \cite{Beer89,SRH90,SRLG+90}. This is not only because
they are the means for {\em 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 {\em 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.
 
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 {\em 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 \cite{Subi91}.
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 \cite{SBMS93}). 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.
