Fully Integrated Data Environments

This book cannot encompass all the achievements of the FIDE consortia and so it focuses on a selection of highlights that represent the major achievement in the final years. There are references to or synopses of FIDE work that has been published elsewhere. Although there are many publications generated by the FIDE consortia, the majority of this book is new material.

Persistent programming languages are designed to support the construction of persistent application systems which have the potential to be long-lived, concurrently accessed and consist of large bodies of data and programs. Well designed programming languages have two important effects: they provide better notations enhancing and accelerating descriptions, for example definition of schemata via data definition languages or definition of process via programming languages, and they demand the development of clean and precise understanding of the underlying concepts. FIDE therefore paid particular attention to the integration of databases and programming languages focusing on those issues peculiar to persistent application systems.

Three approaches to the design of a persistent programming language have been investigated during the FIDE₂ project. The approaches share a common assumption but differ in some basic goals. The common assumption has been that a persistent language should be statically and strongly typed, and based on a type system with parametric polymorphism, recursive types, and functions as first class values. This assumption is motivated by the fact that the reliability of code which is part of long-lived and evolving systems must be automatically checked as far as possible. Static and strong type systems are one of the most effective partial correctness checking tool currently available. On the other side, static type system can be a hindrance for evolution unless they exhibit sophisticated polymorphic features which allow changes to be accommodated.

This text provides an introduction to Tycoon1, an open persistent polymorphic programming environment. The Tycoon language TL is based on expressive and orthogonal naming, typing and binding concepts as they are required, for example, in advanced data-intensive applications. The characteristic language mechanisms of TL are first-class functions and modules, parametric and subtype polymorphism extended to a fully higher-order type system. Tycoon programs are statically typed but may include explicit dynamic type variables which can be inspected at run-time.

Fibonacci is an object-oriented database programming language characterized by static and strong typing and by new mechanisms for modelling databases in terms of objects with roles, classes and associations. A brief introduction to the language is provided to present those features which are particularly suited to modelling complex databases. Examples of the use of Fibonacci are given with reference to the prototype implementation of the language.

Persistent programming systems are designed as an implementation technology for long lived, concurrently accessed and potentially large bodies of data and programs, known here as persistent application systems (PASs). Within a PAS the persistence concept is used to abstract over the physical properties of data such as where it is kept, how long it is kept and in what form it is kept. As such it is seen as having a number of benefits in simplifying the task of PAS programming. Here, we describe the integrated design of the Napier88 persistent programming system and how Napier88 may be used to develop PASs.

Linguistic reflection is defined as the ability of a running program to generate new program fragments and to integrate these into its own execution. This is the basis for system evolution which itself is necessary to achieve adequate persistent application system (PAS) longevity. For safety reasons only strongly typed reflection has been investigated in the FIDE project.

Reflective systems allow their own structures to be altered from within. In a programming system reflection can occur in two ways: by a program altering its own interpretation or by it changing itself. Reflection has been used to facilitate the production and evolution of data and programs in database and programming language systems. This paper is concerned with a particular style of reflection, called linguistic reflection, used in compiled, strongly typed languages. Two major techniques for this have evolved: compile-time reflection and run-time reflection. These techniques are described together with a definition and anatomy of reflective systems using them. Two illustrative examples are given and the uses of type-safe reflective techniques in a database programming language context are surveyed. These include attaining high levels of genericity, accommodating changes in systems, implementing data models, optimising implementations and validating specifications.

This paper describes the use of reflection to create programs which modify themselves, the difficulties in writing such programs and a practical tool for making reflective programming easier.

The most significant difference between persistent and non-persistent programming languages is that, in a persistent language, the long-term data is typed. This results in a major shift in the emphasis of type system protection, from one of a safety mechanism over programs to that of a safety mechanism over the entire software system, including both programs and long-term data. Type systems are normally viewed as providing two aids to the programmer: a modelling framework to aid the task of data abstraction, and a protection mechanism which prevents this modelling framework from being improperly used by a program. The difference in persistent systems is that the integrity of the data modelling is enforced over data which outlive the program invocation in which they are created, and are shareable by other program invocations.

We present a simple extension of typed λ-calculus where functions can be overloaded by putting different “branches of code” together. When the function is applied, the branch to execute is chosen according to a particular selection rule which depends on the type of the argument. The crucial feature of the present approach is that the branch selection depends on the “run-time type” of the argument, which may differ from its compile-time type, because of the existence of a subtyping relation among types. Hence overloading cannot be eliminated by a static analysis of code, but is an essential feature to be dealt with during computation. We obtain in this way a type-dependent calculus, which differs from the various λ-calculi where types do not play any role during computation. We prove Confluence and a generalized Subject-Reduction theorem for this calculus. We prove Strong Normalization for a “stratified” subcalculus. The definition of this calculus is guided by the understanding of object-oriented features and the connections between our calculus and object-orientedness are extensively stressed. We show that this calculus provides a foundation for typed object- oriented languages which solves some of the problems of the standard record-based approach.

Persistent programming is concerned with the creation and manipulation of data with arbitrary lifetimes. This data is often valuable and therefore protected to ensure that it is free from misuse. The mechanisms used to protect the data vary with a tradeoff between static expression of the protection and the flexibility in modelling it. This paper explores the full range of protection mechanisms in persistent systems from static to dynamic checking and contrasts it with the corresponding balance between safety and flexibility in the system. Protection by capabilities, dynamic universal union types, encapsulation, subtype inheritance, existential quantification and predicate defined invariants are all explored with reference to manipulating long-lived data.

Our focus of interest is in the integration of programming languages and database management systems. In particular, the integration of type systems and data models is considered. One tension in this integration occurs when a type system with subtype inheritance is combined with a data model which contains mutable values, as described by Albano [2].

A bulk type describes a homogeneous collection of values. These values are described by another type which is given as a parameter to the bulk type constructor. Many bulk types such as sets, lists and relations are already familiar and widely used in data-intensive applications. Additional bulk types, like bags and multisets, can be defined either by system providers or by expert users. Languages with multiple bulk types have a higher potential for problem-oriented data modelling. In particular, by using bulk types to describe data that resides in legacy databases one gains access to that data in a convenient, consistent and safe manner.

The semantics of many bulk data models depends on user-defined attributes such as definitions of element equality, ordering, and other domain predicates. While these attributes are an intrinsic part of the data model, they are not normally treated as part of the static type description. This leads to the occurrence of data modelling errors which are not statically detectable, such as a union operator accidentally being applied to two sets which have different equality semantics.Here we introduce a model of bulk types which includes such attributes as part of the type definition, along with a typechecking scheme which is statically decidable. The model relies upon the value dependencies being manifest to the typechecker; one neat way of achieving this is through the new paradigm of hyper-programming.

Bulk structures play a central rôle in data-intensive application programming. The issues of bulk type definition and implementation as well as their integration into database programming languages are, therefore, key topics in current DBPL research.

One of the limitations of commercially available object-oriented DBMSs is their inability to deal with objects that may change their type during their life and which exhibit a plurality of behaviours. Several proposals have been made to overcome this limitation. An analysis of these proposals is made to show the impact of more general modelling functionalities on the object implementation technique.

Traditionally the database and programming language communities have taken different approaches to concurrency control. In programming languages, concurrency control is based upon the concept of the coordination of a set of cooperating processes by synchronisation. Language constructs such as semaphores [1], monitors [2], mutual exclusion [3], path expressions [4] and message passing [5] have been provided to support this concept. By contrast, in databases, concurrency is viewed as a system efficiency activity which allows parallel execution and parallel access to the data. However, each database process may have to suffer the indignity of abortion in order to sustain the illusion of non-interference. The key concept in databases is that of serialisability [6] which has led to the notion of atomic transactions [7] supported by locking or optimistic concurrency control methods [8].

An abstract, operational model for specifying flexible concurrency control schemes within a persistent store is presented. The goal of the model is to allow concurrency control schemes to be specified in a manner that promotes understandability and supports their implementation. Schemes that support controlled sharing among autonomous computations are the primary targets of this work. An abstract machine programmed by a set of rules is employed to specify operational semantics for the concurrency control schemes.

A noticeable trend in database research and database system development is an increased interest in behavioural and procedural aspects of information systems. Data models that describe dynamic processes in addition to static data structures are capable of capturing more of the application semantics as exemplified by object-oriented models like Taxis, ADAPLEX, Galileo or Fibonacci. Similarly, database systems that support procedures, methods, rules or triggers in addition to persistent data values are capable of factoring-out procedural code from individual application programs into shared databases.

The goal of the persistent support systems developed in FIDE is to improve the construction, maintenance and operation of persistent application systems (PAS). A PAS is a software system that gives its users a flexible, problem-oriented and safe access to large sets of long-lived objects of application-specific types.

The search for an appropriate architecture for Persistent Systems is still in its infancy and can be compared with the original exploration of operating system architectures. Indeed it is not clear whether a favoured architecture will emerge or whether there will remain a variety of architectures.In a recent paper [6] the following classes of architecture were discussed:Combined Existing Systems Here an existing storage technology and an existing programming language are combined re-using varying amounts of existing knowledge, designs and implementations.Extended Existing Systems In these architectures an existing technology is chosen to provide one of these two major components and then extended to encompass more of the functionality of the other.Systems Based on an Integrated Design Combined requirements are identified and a system is then designed and built “from scratch” to fulfill those requirements. However, this construction utilises conventional operating systems and potentially other pre-existing technology.Persistent Worlds The constructors of these systems start with a few primitives to provide persistence and build from these. In this category we find work on novel persistent operating systems [24,15].It may be useful to use this classification to study the current FIDE₂ work and its relationship with other work. By definition, the work of FIDE ₂ Fully Integrated Data Environment, is directed towards the final two classes. In practice, all the FIDE₂ implementations end up in the third category.

Problems with the inconsistent behaviour of system construction components for building large and long-lived application systems are identified. They make the programmer’s task harder and the user’s world more confusing in the same way that the disharmonies between programming languages and databases did. Persistent programming languages overcame those disharmonies.This paper challenges researchers to design and build a common substrate to the construction components. The construction components would be re-built using the substrate to achieve consistent behaviour. Application systems would then use this new family of construction components. The substrate, called the Scalable Persistent Foundation promises several advantages: consistent application system behaviour even when under stress, accelerated application system building and maintenance, genuine longevity of application systems and improved operational efficiency.The search for a design and implementation of this foundation will provoke debate about what behaviour, in the context of distribution, overload, failure, change, concurrency, transactions, safety, security, etc. is wanted.Experiments using short-lived computations and small-scale systems are rarely useful in predicting large-scale and long-term behaviour. Therefore large-scale apparatus and long-term experimental procedures are required.

In the DBPL project we tackled the problem of supporting data-intensive applications in a single framework, clean and simple in its conceptual foundation and free of technical mismatches. Our development of specific language extensions required by data-intensive applications was guided by a strict adherence to the language design principles of simplicity, orthogonality and abstraction. The project started in the mid 70ies with Pascal/R [16-18,6] and Modula/R [10,12] where we first suggested some high-level language constructs for data of type relation. This research culminated in the delivery of a mature implementation of the DBPL system [23,22,15,14,19], a database programming language based on Modula-2.

The application of orthogonal persistence to a number of traditional programming language mechanisms has produced significant results for the modelling power of persistent languages. Many of the implementation techniques for these mechanisms have been copied or adapted from non-persistent systems for use in early persistent language implementations. As the appearance of integrated persistent programming environments becomes more widespread, an examination of these implementation techniques shows that they may not be well-suited to a persistent environment. The premise of this paper is that the techniques do not take into account the increased object management costs involved in a persistent system. Aspects of the PamCase abstract machine architecture are presented that efficiently implement a number of common language mechanisms as well as some novel ones enabled within the persistent environment. The machine has been implemented and measurements support the initial premise.

We describe the Tycoon persistent system architecture that achieves a high degree of scalability and interoperability through a full integration of persistent data, programs and threads while maintaining a strict separation of storage, manipulation, modelling and representation tasks into well-defined system layers. For several of these layers alternative implementations with distinct operational support are provided that can be configured dynamically to match best the requirements of a given application. Moreover, we present Tycoons architectural contributions to enable interoperability with existing generic services like databases, user-interface toolkits and C++ program libraries.

The development of persistent store technology is a fundamental research issue in the FIDE/FIDE₂ framework. In FIDE’s envisaged architectures, data and programs are held in the persistent store. As such, the reliability, integrity, capacity, performance, and functionality of persistent stores are crucial to the achievement of FIDE’s goals.

An essential feature of a persistent programming system is a store capable of supporting complex objects. A number of proposals and implementations of persistent object stores have been made [1–8]. Each store has its own set of design goals since each has been used with a particular view of the persistence abstraction.

PIOS (Physically Independent Object Server) is a prototype implementation of an object store intended to test some new ideas and techniques in the framework of the FIDE₂ project.The main idea in PIOS is the support of physical objects’ independence in an object store. Physical Independence allows the change of strategies in storing physical objects in the database without affecting the applications since they always see the same logical database schema. Physical Independence opens up opportunities to enhance performance in areas such query optimisation and high performance concurrency control.In this paper, an overview of the PIOS architecture is presented, stressing the new techniques implemented in the system to exploit physical independence in improving system performance.

We briefly outline the main characteristics of an efficient server-based algorithm for garbage collecting object-oriented databases in a client-server environment. The algorithm is incremental and runs concurrently with client transactions. Unlike previous algorithms, it does not hold any locks on data and does not require callbacks to clients. It is fault tolerant, but performs very little logging. The algorithm has been designed to be integrated into existing OODB systems, and therefore it works with standard implementation techniques such as two-phase locking and write-ahead-logging. In addition, it supports client-server performance optimizations such as client caching and flexible management of client buffers. The algorithm has been implemented in the EXODUS storage manager before being evaluated.

Systems that have to work with large-scale persistent data have a system architecture where there is a clean separation between a frontend performing data manipulation and visualization and a back end responsible for reliable persistent bulk data storage. Since actions in the frontend trigger data access operations performed by the backend, this separation leads to a client-server architecture, where a store protocol defines possible interactions between a client program and a database server.

Measurements of persistent systems are reported. A discussion of issues and criteria that should guide measurements and their interpretation is initiated. Measurements which may inform the engineering of persistent object stores are discussed and in particular a proposal is made for the formulation of laws governing the behaviour of persistent object stores. Some initial laws are presented. Experiments examining adherence to these laws are briefly reported.

Persistent system environments are expected to provide the data management facilities required by languages, such as those presented in Chapters 1.1.1 to 1.1.3, and with at least the performance of traditional database systems. In FIDE the major research issue was the choice of architectures for complete, extensible and tailorable systems. This includes work on: canonical store mechanisms relating to transactions, concurrency, distributions, global optimisation and inter-operability,efficient programming language implementation, andquery processing and optimisation.

The differing requirements for concurrency models in programming languages and databases are widely diverse and often seemingly incompatible. The rigid provision of a particular concurrency control scheme in a persistent object system limits its usefulness to a particular class of applications, in contrast to the generality intended by the provision of persistence. One solution is to provide a flexible system in which concurrency control schemes may be specified according to the particular task in hand, allowing the same data to be used in conjunction with different concurrency control schemes according to the needs of the application.A major difficulty in the engineering of such a system lies in the building of generic mechanisms to provide the facilities of data visibility restriction, stability, and atomicity, independently of the combination of these employed by a particular concurrency control scheme. Flask is a architecture which is designed to achieve this goal by defining a layering whereby the memory management is not tied to any one concurrency control scheme operating above. This paper outlines the Flask architecture and focuses on an implementation based on concurrent shadow paging.

Nested transactions facilitate the control of complex persistent applications by enabling both fine-tuning of the scope of rollback and safe intra-transaction parallelism. In this paper, we are concerned with supporting concurrent nested transactions on client workstations of an OODBMS. Use of the traditional design and implementation of a lock manager results in a high CPU overhead: in-cache traversals of the 007 benchmark perform, at best, 4.5 times slower than the same traversal achieved in virtual memory by a non-persistent programming language. We propose a new design and implementation of a lock manager which cuts that factor down to 1.8. This lock manager supports nested transactions with both sibling and parent/child parallelisms, and provides object locking at a cost comparable to page locking. Object locking is therefore a better alternative due to its higher functionality.

An approach to query processing in object-oriented stores supporting physical data independence is proposed in this Chapter.In particular, the problem of query optimisation (i e finding efficient execution plans for declarative queries) is investigated. A set of rewrite rules has been defined in order to allow an algebraic optimisation phase. A local search procedure, based on a cost model of the store, has been tailored to the task of physical optimisation. To support the physical data independence in the store, a translation algorithm, dealing with the actual storage organisation of the database, has been studied. A comprehensive example illustrates these mechanisms. Finally, performance results are presented.

A fundamental characteristic of declarative query languages is the nesting of queries (embedding of a query within another query). In the object-oriented (oo) context, nested queries are used to (i) express complex conditions, (ii) access nested structures and (iii) produce nested results. We propose novel techniques for efficiently evaluating nested queries in oo languages.

The traditional focus of database language research has been on high-level languages for data access and manipulation (query languages, trigger definition languages, 4th generation languages, script languages) or on implementation-oriented languages which capture the characteristic operations of a specific target system at hand (relational algebra, object algebra, structural recursion,…).

Polymorphic abstraction provides the ability to write programs that are independent of the form of the data over which they operate. It has proved difficult to provide efficient implementations of polymorphism. This paper addresses this problem and describes a new technique which can implement all forms of polymorphism, use a conventional machine architecture and support non-uniform data representations. Furthermore, the method ensures that any extra cost of implementation applies to polymorphic forms only and allows such polymorphic forms to persist over program invocations.

This Part focuses on making use of the persistence technology, described in Parts 1 and 2 of this book, to build Persistent Application Systems (PASs). In order to fully exploit the FIDE₂ technology we need to provide the application builder with techniques, tools and environments to support system building. We also want to demonstrate that the main features of the FIDE₂ languages such as orthogonal persistence, strong typing and referential integrity can be exploited to construct better application building environments. The characteristics of a PAS are that it is a large-scale, long-lived, data-intensive application system. Therefore, we need to identify and prototype techniques and tools which address these aspects of application systems.

A Persistent Programming Environment (PPE) is the environment within which all the enabling tools for persistent software engineering will operate. Our objectives in this work were to identify the minimal set of elements which are essential in a PPE and to prototype some of the tools which would be required for the development of Persistent Application Systems (PASs).

This paper examines some of the advantages of providing software engineering environments within a persistent object system with strong typing and referential integrity. Persistent linkage allows persistent objects to be included in the binding process. Strong typing guarantees that objects are only manipulated in a manner consistent with their type system descriptions. Referential integrity ensures that once a link (reference) to an object is established, its identity is unique and it persists over time. As a consequence no object can be deleted while another refers to it. It is shown how the integration of system specifications, programs, configuration management tools and documentation all within a single persistent environment leads to powerful new techniques. This new power is achieved by sharing structured persistent data across the hitherto enclosing boundaries of system components.

The content of these chapters derives from two papers which explore further the possibilities of the hyperprogramming and hypercode concept. Neither paper describes engineered systems, but rather both are workshop papers which explore long-range possibilities of systems built around the hyperprogramming model. Although most FIDE research is based upon engineering practice as well as ideas, these papers are purely conjectural; the hyperprogramming and hypercode systems are built and in use, but a second generation of such systems is a prerequisite before the engineering aspects of systems such as those outlined here can be investigated, and so at the time of writing these remain descriptions of potential research projects.

Some general comments relevant to the contents of this chapter are given in the Preface to Chapters 3.1.2 and 3.1.3 at the beginning of Chapter 3.1.2.

The Persistent Workshop is a programming environment to support the construction of application systems in Napier88, a persistent programming language. In addition to supporting programming activities, the Workshop provides a demonstration of the persistence technology together with an environment in which various experiments can be conducted. The basic structure of the Workshop is outlined, together with a short summary of the tools provided within the programming environment. Finally, the evaluation of the Workshop is briefly described.

This chapter describes the development of the Glasgow Persistent Libraries for Napier88. Our overall goals are to increase software re-use and accelerate software construction and maintenance. The objectives of this work were to investigate the creation of high-quality library components and the provision of accurate retrieval mechanisms enabling users to find relevant library components. We discuss the basic principles which guided our research and describe the tools which were built to support the construction and use of the Libraries. To conclude, we outline possible future work in the area of large component libraries.

This paper summarises work to design Software Visualisations that support Napier88 programmers in understanding and using the contents of the persistent store. Two example visualisations are described. Their effectiveness in supporting their intended tasks has been assessed by studying programmers using these visualisations.Visualisation design can borrow existing metaphors. However, successful application of a metaphor (and thus a successful visualisation) depends upon a careful analysis of the expected context of use for the visualisation.

Data modelling is the process of creating a schema — i e a description of the data handled by a database application. The process uses a “data model” which is a language containing generalised constructs for the description of data structures. As such, creating an application by data modelling is akin to writing the set of type declarations in a programming language — a data model and a type system playing a similar role in application development.

Data modelling is the process of creating a schema — i e a description of the data handled by a database application. This report describes the automatic generation of the code implementing the application from the schema. The resulting code can be used as the completed application but is more likely to be used as the basis of customisation to create the final product. This produces a number of benefits: the creation of a high-level description of the data structure which genuinely fits the application; the acceleration of application development; and the creation of a structure for the application implementation which, being regular, is easier to extend and to maintain. The code generated can be in any of four target languages — all of which are full database programming languages. The paper finishes with a discussion of how to add to this list of languages.

STYLE is a method to systematically construct a customized development environment (CDE) for a given high-level data model by exploiting and extending an existing persistent programming environment along three dimensions.On the functional dimension, polymorphic types and higher-order functions are used to extend the system functionality with new generic services and through the integration of external tools. On the operational dimension, orthogonal persistence is provided for application and meta data related to design objects. Finally, on the modal dimension, reflective capabilities of persistent programming environments make it possible to view data as executable code and vice versa. This is used in a CDE to switch dynamically between different modes of a design object.The STYLE approach is illustrated using a concrete CDE implemented for an object-oriented data model exploiting and extending the Tycoon persistent programming environment. This STYLE workbench provides integrated graphical and textual modelling tools, generation support and data model animation.

We present a systematic approach to the rapid implementation of high-level data models and query languages in the polymorphic higher-order programming language TL. The static semantics of data model constructs are captured by a mapping to polymorphic types and associated data constructor and selector functions. The dynamic semantics of query languages are realised by a mapping to bulk data types and iteration abstractions. Contrary to conventional approaches, these two mappings are specified by user-defined grammar extensions of the target language TL based on user-defined library code and not by separate tools in the programming environment. We give examples of this syntax-directed approach to data modelling and discuss its ad450 tages and limitations.

Today, successful application development is rarely carried out by coding application programs from scratch, instead there is a strong tendency to exploit services provided through open and modular environments already populated with prefabricated and packaged functionality and information.

Database systems are concerned with structured data. Unfortunately, data is often stored in an unstructured manner (e g in files) even when it does have a strong internal structure (e.g. electronic documents or programs). Unfortunately, data stored in files cannot benefit from database technology and in particular, has to rely on very primitive linguistic support. In this paper, we show how structured files can be queried using (high-level) database languages. In [2] (see Chapter 3.3.2) we address the problem of updates.

This text is a complement Chapter 3.3.1. It sketches the solution we propose for the propagation of updates specified at the database level (here a view specified using structuring Schemas) to a file (here the physical storage).

Reliable interoperation between independently developed Persistent Object Systems (POS) requires type-safe access to persistent data objects and generic services:Persistent Object Management: It is necessary to identify, store, retrieve and manipulate objects that outlive a single program execution and that may even exist independently of the application that created them. Appropriate naming and scoping mechanisms are required to establish temporary or persistent bindings between persistent objects created independently, possibly using different tools on different machines.Data Integrity: Type systems represent a particularly successful approach to enforce integrity constraints on data objects local to a single program. Similarly, language-independent mechanisms have to be provided for shared, persistent objects.Generic Functions: Many functions required in a POS can be obtained by instantiating generic services. Interoperation protocols have to be capable of handling these generic functions without diminishing data integrity or duplicating code.