It is difficult to imagine a successful semantic theory that does not include time as an integral component. Yet all of today's major data models – models which purport to provide a general theory on how to represent information for convenient and rapid storage and retrieval on digital computers – completely ignore this essential aspect of semantics. In this work we examine the connection between two areas of semantics, namely the semantics of databases and the semantics of natural language, and link them together via a common view of the semantics of time. In the first part we argue that an essential ingredient for the success of efforts to incorporate more real world semantics into database models is a coherent theory of the semantics of time. We describe such a database theory, and then proceed to present a formally defined English database query language whose semantic theory makes explicit reference to the notion of denotation with respect to a moment of time.

The idea that time might be an important consideration in providing an enriched database semantics is not new to this work, but it is nonetheless a relatively recent concern of database research. [Bub77], [Ser80], [Klo81], [And81], [AM82], [CW83], [Sno84], [GV85], [CC87], [GY88], and [CC88a] are among the many works that have lately investigated ways in which time might be added to a database model.

Overview of the Approach

In a series of papers culminating in [Mon 73], henceforth PTQ, Richard Montague embarked upon a program of providing a formal syntax coupled with a model-theoretic semantics for increasingly sophisticated fragments of English. The semantics for the PTQ fragment is given indirectly, as follows. The set of sentences of the fragment is defined inductively from a set of Basic Expressions (words). Direct translations into an Intensional Logic (IL) are provided for each of the Basic Terms. Each of the formation rules in the inductive definition is coupled with a translation rule which specifies the translation into IL of the output of the rule as a function of the translations of the input(s) to the rule. Thus the interpretation of any English sentence in the fragment is given by means of the model-theoretic interpretation given by the semantics of the logic to its corresponding representation in IL.

Subsequent to the presentation of the PTQ fragment, a number of researchers (e.g. [Tho72], [Ben74], [Par75], [Tho76], [Kar77], [Ben79], [Dow79], [Hir83], and [Hin88]) have explored various extensions to the PTQ fragment. These extensions have been motivated by the desire to provide a formal syntax and semantics to a larger set of English syntactic constructs; occasionally they have necessitated changes or extensions to the underlying logic IL. [DWP81] provides an excellent introduction to the area known as Montague Semantics, while [vB88] surveys the entire field of intensional logic.

Introduction

In this Chapter we give a formal specification of a simple English Query Fragment, QE-III, for the historical department store database example discussed in earlier chapters. This fragment incorporates all of the features that we discussed in the previous chapter. Towards the end of the chapter we present a Fragment Schema for a QE-III type query language that could be adapted to other domains by defining the relevant vocabulary in the categories of the fragment. The schema and the guidelines for defining such a fragment are intended both to help a database administrator in the process of designing a language for a new domain, and also to show some of the general principles relating aspects of the HRDM model to the query language semantics.

We present the language definition in three parts. First we describe the syntactic component, which consists of defining the categories of the language and the basic expressions of these categories, followed by the rules of formation. Together these constitute an inductive definition of the set of meaningful expressions of QE-III. The semantics of the language is presented next, following Montague's general procedure in PTQ. This consists of giving, for each syntactic rule, a corresponding rule of translation into the logic ILs, for which a direct semantic interpretation has already been specified (in Chapter 2.) Finally, we provide a pragmatics for the language when used in the assumed context of a question-answering system.

Motivation for Historical Databases

The relational database model proposed by Codd [Cod70] views a database as a collection of “time-varying relations of assorted degrees” [Cha78]. However the model itself incorporates neither the concept of time nor any theory of temporal semantics. Our research suggests that the concept of time can be of interest in real-world databases, and presents a technique for incorporating a semantics of time into a database model. The relational model is used as the formal database framework within which the work is cast, but it is not an essential ingredient in the work discussed. Indeed in [CC88a] we address the issue of modelling the temporal dimension of data within the context of an object-oriented database model.

A great deal of attention has been given lately to the role that formal logic can play in providing a formal mathematical theory to unify the theory and semantics of database concepts and operations ([GM78] is an excellent reference for these issues.) We believe that this is a healthy trend that can only serve to clarify and make precise otherwise vague ideas and theories. Moreover, a great deal of the meta-theory of formal logic can be applied directly toward the understanding and the proof of many notions in database theory. In this work we propose the concept of a historical database as a tool for modelling the changing states of information about some part of the real world.

Introduction

In this Chapter we describe the relationship between HRDM and the logic ILs and its model theory. This relationship is first presented formally, and is then followed by an informal discussion that emphasizes insights that it can provide into the way that a database models the real world, and into the nature of entities and relationships, of key and non-key attributes, of queries and data constraints, and of the interaction of time with all of these concepts. The formalism is presented in the interests of completeness and rigor, but it is easy to get lost in some of the notation; the informal discussion provides a better overview both of how the temporal dimension is incorporated into, and how it affects, the traditional relational model.

In Chapter 2 we described the syntax and semantics of the language ILs. To be more precise we should rather say the family of ILs languages, any particular language in this family being determined by the set C of non-logical constants. The historical relational database concept presented in Chapter 3 will now be related to the discussion of the intensional logic as follows. First we show that a particular HRDB scheme defines a particular logic in the family of ILs languages that provides a formal expression of the historical database semantics and that serves as the target language for translations from our English Query Language which will be described in the latter half of this work.

Summary

The Historical Relational Database Model

Under the general assumption that in any scientific enterprise the development of a formal logical theory is a fruitful endeavor, we have attempted in this work to develop such formal theories for the incorporation of a temporal component into a database model, and for the specification of an English query language facility for such a database. Because of the power of the logical formalism of IL developed by Richard Montague [Mon74] we have been able to express both of these theories in terms of the same logical apparatus. Thus two areas which may have seemed only marginally related at the outset were seen to have a closer connection.

Beginning first with formalizing a historical database model, we presented the model HRDM. This model turned out to be a simple extension to an entity-relationship semantics imposed upon the relational database model. The temporal component was included in a very simple but fundamental way as a basic component of the model, and its significance from both the informal, intuitive view of three-dimensional relations extending in both directions of time, and from the formal, model-theoretic view, were discussed. In order to present as general a model of time as possible, we put only the barest of constraints upon the temporal dimension – linear order and density.

The HRDM model was seen as providing a number of insights into the nature of a database and how it functions as a model of the real world.

Abstract

This paper describes the design and implementation of a Distributed Ada system. The language is not well defined with respect to distribution, and any implemtation for distributed execution must make a number of decisions regarding the language. The objectives in the implementation described here are to remain as close to the current definition of Ada as possible, and to learn through experience what changes are necessary in future versions. The approach we take translates a single Distributed Ada program into a number of Ada programs (one per site), each of which may then be compiled by an existing Ada compiler. Issues discussed include the ramifications of sharing of data types, objects, subprograms, tasks and task types. The implementation techniques used in the translator are described. We also develop a model of the performance of our system and validate it through performance benchmarks.

INTRODUCTION

The importance of distributed systems cannot be over-emphasized, especially with the reduction in the cost of high speed connection between powerful processing elements. Distributed computing has made inroads into many important areas such as manufacturing, avionic systems and space systems. The cost of developing software for such systems, however, is reaching astronomical proportions [1]. A major concern is the creation of software tools to economically harness the increased computing power.

Central to distributed software development is the language used to program these distributed devices.

ABSTRACT

This paper describes firstly a general model for implementing Ada in a distributed or parallel system using existing compilation systems and without extensions to, or restrictions on, the Ada language definition. It then describes an instance of the model, namely how to implement an application across a network of transputers in Ada using the current Alsys Ada Compilation System for the Transputer.

INTRODUCTION

Much debate has already taken place regarding the inadequacies of Ada to support a single program running on a distributed or parallel architecture. This has led to a set of twelve requirements from the Parallel/Distributed Systems Working Group for consideration by the Ada 9X Project Requirements Team [DoD89]. Whilst we await Ada 9X, it is very important to be able to demonstrate that current Ada can be used to program distributed systems efficiently, without compromising Ada's goals of security and portability. This document describes how Ada can be used in this way in the general case and also gives an example of distributed Ada on the Inmos transputer. The transputer has been chosen primarily as a precursor to a study commissioned by the European Space Agency into the problems of, and recommendations for, mapping Ada onto a multi-transputer network for on-board space applications.

The intention of the general model is to be able to demonstrate support for the needs of distributed systems such as:

• program partitioning and configuration;

• dynamic reconfiguration and fault tolerance;

• different perception of time in different partitions;

• different scheduling requirements in different…

ABSTRACT

This paper presents the current position of the York Distributed Ada Project. The project has developed an approach to the programming of loosely coupled distributed systems in Ada, this being based on a single Ada program consisting of virtual nodes which communicate by message passing. A prototype development environment has been produced to support this approach, and an example distributed embedded system has been built. Preliminary work has been undertaken on mechanisms to support the construction of fault-tolerant systems within the approach.

INTRODUCTION

The Ada programming language, together with an appropriate support environment, is well suited to the development of large software engineering applications. Many such projects involve programming embedded computer systems, which often include loosely coupled distributed processing resources — collections of processing elements which are connected by some communication system but which share no common memory. It is now a commonly accepted view (Wellingsl987) that the Ada language by itself does not provide adequate support for the programming of these systems. The York Distributed Ada (YDA) Project has addressed this problem and developed an approach which allows Ada programs to be constructed for execution on distributed systems. (The YDA project was originally funded through the UK's Alvey Software Engineering Directorate as part of the ASPECT(Hall1985) project. It is currently funded by the Admiralty Research Establishment.) The current position of the project is presented in this paper.

BACKGROUND

Now, when the internal speed of computers is close to the physical limitations of electronic devices cf. [Wil83,Mea83] parallelism is the main way to increase the computing capacity. This conclusion has been obvious for quite some time now, and multiprocessor systems have attracted much attention during the last years.

In order to achieve parallelism, new computer structures and internal organizations are needed. There are, however, still no general solutions to those problems. Finding general and efficient ways to organize for parallelism in computer systems is one main interest of computer architecture research today.

One application of multiprocessors that is likely to increase rapidly is based on the use of parallel languages. As parallel languages has not been generally available, there is still very little knowledge among software designers how to take advantage of program parallelism. Now, when parallel languages like Ada are becoming readily available, the programming community will take advantage of the new possibilities they offer.

There are strong reasons to believe that parallelism in programming will be used even aside from the possibilities of increasing the speed with parallel hardware. Many computational problems have an inherent parallelism that obviously will be used when only parallelism has become part of the programmers' daily life. This will also increase program understandability [Hoa78]. Real-time programming is an obvious example for which these arguments are relevant, but as experience grows the same will show to be true for a variety of application areas.

INTRODUCTION

Overview

This paper will present a study of practical design decisions relevant to the retargeting of a traditional compilation system to a distributed target environment. The knowledge was gathered during the course of Honeywell's Distributed Ada project which involved the retargeting of a full commercial Ada compilation system to a distributed environment. The goal of the project was to create a compilation system which would allow a single unmodified Ada program to be fragmented and executed in a distributed environment.

The Distributed Ada Project

The trend in embedded system architectures is shifting from uniprocessor systems to networks of multiple computers. Advances in software tools and methodologies have not kept pace with advances in using distributed system architectures. In current practice, the tools designed for developing software on uniprocessor systems are used even when the target hardware is distributed. Typically, the application developer factors the hardware configuration into software design very early in the development process and writes a separate program for each processor in the system. In this way, software design gets burdened with hardware information that is unrelated to the application functionality. The paradigm is also weak in that no compiler sees the entire application. Because of this, the semantics of remote operations are likely to be different from local operations and the type checking that the compiler provides is defeated for inter-processor operations.

INTRODUCTION

The task of programming distributed applications in Ada may be addressed in several ways. Most of these require the application developer to factor the hardware configuration into software design very early in the development process. The resulting software is sensitive to changes in hardware, does not lend itself to design iteration, is not easily transportable across different hardware configurations, and is not stable against changes during the lifecycle of the application.

In Section 3, we describe an approach that aims at separation of concerns between program design and program partitioning for distributed execution. The entire application is written as a single Ada program using the full capabilities of the language for program structuring, separate compilation, and type checking. Then in a distinct second phase of design, the program is partitioned and prepared for distributed execution. Advantages of a two-phase design approach are discussed. Section 4 reviews related work and presents a comparative evaluation. Section 5 describes the notation used to express program partitioning. Section 6 revisits the issue of what Ada entities should be distributable.

Two implementations of this approach have been completed and tested with the Ada Compiler Validation Capability (ACVC) test-suite. Implementation issues, and the key features of our implementation approach are presented in an accompanying paper.

CLASSIFICATION OF APPROACHES

The Ada language does not provide explicit language support for distribution.

INTRODUCTION

Perhaps the greatest challenge facing Ada is in the domain of the large distributed real-time system. Because of the long lead time associated with such complex applications no real experience of the use of Ada, in this type of domain, has yet been gained. Nevertheless there are projects of a large and complex nature that are committed to the use of Ada, even though the full potential of the language has yet to prove itself in this challenging domain.

The Portable Common Execution Environment (PCEE) project is a research effort addressing the life cycle support of large, complex, non-stop, distributed computing applications with Mission And Safety Critical (MASC) components. Such applications (for example the International Space Station — Freedom) typically have extended life-time (e.g., 30 years) requirements. PCEE focuses on the system software, the interface to applications and the system architecture necessary to reliably build and maintain such systems. The requirements extend from the target system environment to the integration environment, and ultimately to the host environment. The integration environment serves as the single logical point of integration, deployment, and configuration control whereas system development occurs in the host environment. Life cycle issues include an integrated approach to the technologies (environments, tools, and methodologies) and theoretical foundations (models, principles, and concepts) that span these three environments. The scope of the effort is necessarily broad. There are, however, substantial research foundations to support development across the breadth of the project.