Relix(ID:1882/)Implementation of first stage of AldatImplementation of first stage of Aldat Related languages
References: The Aldat Project at McGill University intends to build a programming language, Aldat, based on the data type relation and the operations of the domain and relational algebras. The present incarnation of Aldat is the system relix, which implements all the operators described by Merrett plus relational recursion and some specialized editors for pictures and Prolog. Relix is described in a technical report, which refers to further documentation. The next section briefly introduces relix. For the present discussion, the important thing about relix is that it implements only the formalism defined by the above operators on relations and attributes. It does not include any of the facilities proper to a programming language, such as the scoping and typing of names, or abstractions such as functions and loops. It is significant that many diverse applications can be handled by relix and that the set of operators it implements has remained stable since 1984. Both these points encourage us now to consider how to embed relix into a programming language defined along classical lines but built for modem high-performance computers and with the latest developments in programming languages in mind. Such developments include polymorphism (which is implicit in relational operations), parallelism (which we can achieve very easily as a by-product of the notions developed in this paper), and abstract data types. However, in this paper we will not explore these issues but restrict ourselves to the foundation step of providing scalars in the language. It will turn out to be easy to add arrays and records once we have scalars, so we do that too, and include the interesting discussion of QT-selectors as l-expressions. Our motivation for these developments arises from particular applications which we wish to build using Aldat. Our methodology in developing Aldat has been and continues to be empirical: the language evolves as a result of being tested on a diversity of applications. We started with commercial and administrative data processing, went on to text and pictorial databases, and are currently working on expert databases and knowledge-based systems. These latter require metadata, or data which refers to the relations and attributes which represent it, and our current additions to Aldat will give us a general ability to handle data of this sort. At the same time, we avoid ad hoc constructions in the language by relying on a few principles of generality which we need not elaborate here. So far, we have kept relix very lean. It consists of five families of operators in the domain algebra, and, in the relational algebra, two families of binary operators (which extend respectively the set-valued operators on sets and the comparison operators on sets), and three families of unary operators. We continue to minimize syntactic and conceptual additions in incorporating scalars into Aldat. The next section reviews the facilities of relix. Section III proposes the language extensions for scalars and also for arrays and records. Section IV discusses the general requirements for using QT-selectors as l-expressions which are introduced by the need to be able to assign to array elements and record fields. Section V discusses the implementation of the new array syntax using B-trees and Z-order. The section on performance gives the result of this implementation and the last section concludes the paper and discusses some of the planned future work. Since the present paper is restricted to the topic of scalars in Aldat, it will not always be clear how the extension to scalars lays the groundwork for further extensions, such as metadata. We will add a few hints in parentheses, but for fuller explanation, the reader will have to await future publications. Related work is being done in database programming languages-see the survey by Atkinson and Buneman. Persistence of scalars, and of data in general, was a major concern of the Data Curator Project and of the language created there, PS-Algol. Our approach shows that only minor syntactic extensions to a simple existing system are needed to achieve this. Extract: Overview of Relix Overview of Relix Relix is a system which implements the current state of the programming language, Aldat. It consists of operators of the relational algebra and of the domain algebra. The relational algebra operators used here are the natural compositiorl, icomp, the nutural or intersection join, ijoin, the ourer or union join, ujoin, selection, and projection. An example of the syntax which ijoins relations R(A, B) and S(B, C), then selects the result on A > C, projects on A and B and assigns the result to T, is: T<- {A,B} whereA > Cin(RijoinS) Here, {A, B } is the set of attributes known as the ?projection list. ? The outer join is similar to the natural join, but includes all tuples from both operands: tuples from R that do not match any tuple in S, or vice versa, appear in the result associated with a null value. Selection and projection are syntactically combined in an operator known as the T-selector. which can be generalized to include quantifiers, the QT-selector. The domain algebra operators used here are scalar operations, such as making E the sum of attributes A and B (let E be A + B), reduction, such as making F the total of all values of attribute A (let F be red + of A), and equivalence reduction, such as making K the subtotals of each group of values of attribute A corresponding to one value of attribute B (let K be equiv + of A by B). Null values in a domain algebra operation always act as if they are the identity element. In addition to these classical operators, relix has an implementation of relational recursion. We here use relix notation to present the simplest form of the transitike closure operation. The transitive closure of a graph, G( X, Y ), is Tis Gujoin (T[YicompX]G) where we use is in place of < - to indicate the definition of a view, in this case a recursive view, and where the ujoin gives the set union of G( X, Y) and the expression in brackets (which is also a relation on X and Y ). |