Aldat (1453/ald001) |
 |
Database language, based on extended algebra
for ALgebraic approach to DATa
Database language, based on extended algebra.
Timothy Merrett et al, McGill University 1977-1990
It featured intrinsic relational expressions and a complete information algebral, together with a mechanism for displaying the information space graphically and projecting subdivisions of that space by trig-based queries.
Structures:
Related languages
| ALPHA | => | Aldat | Influence | |
| Aldat | => | PLAIN | Citation | |
| Aldat | => | Relix | Implementation |
References:
in Information Processing Letters 6(1) February 1977 view details
in Information Processing Letters 6(1) February 1977 view details
in Information Processing Letters 6(1) February 1977 view details
in Information Processing Letters 6(1) February 1977 view details
in Information Processing Letters 6(1) February 1977 view details
in Information Processing Letters 6(1) February 1977 view details
in Information Processing Letters 6(1) February 1977 view details
in Information Processing Letters 6(1) February 1977 view details
This paper explores extensions to the relational algebra, made with practicality in mind, but under the constraint of generality, i.e., freedom from being limited to particular interpretations. By going to the foundations of the relational model in mathematical set theory we can generalize the now classical operations of projection, restriction, natural join and division to two useful families of binary operations and a flexible unary operator which adds quantifiers to the usual process of selecting tuples and attributes from a relation. By using the principle of algebraic closure, we can integrate arithmetical operations on the values of attributes in tuples into the algebraic framework.
We also discuss some of the areas of application which we have used as touchstones of practicality in our research: commercial and library information systems, text and graphics database processing.
Extract: Operations on Relations
Operations on Relations
The relational model is grounded in set theory - a relation is a set of tuples, or, more precisely, it is a subset of the cartesian product of its domains (the sets from which its attributes are drawn). A set is a special case of a relation, namely a unary relation. It is appropriate that operations on relations should generalize the operations already provided for sets. There are three classes of such operations: unary operations (complementation), binary operations which result in sets (union, intersection,etc.) and binary operations which result in logical or boolean values (inclusion, disjointness, etc.)
The unary operation of complementation does not seem to be very useful for relations, which are stored explicitly in a computer and which are usually sparse relative to the universe of all possible tuples. Complementation has not been used in queries or data processing because the notion of the universe is not free from ambiguity in the user's mind: we shall say more on this when we discuss quantification. It is the identity operation on sets which generalizes to the relational operations of project and restrict. (Sorting is such an identity operation, since the abstraction which created the notion of set ignores the order of the elements.) The binary set operations give easier generalizations, and we discuss them first. Extract: Operations on Attributes
Operations on Attributes
Many practicalproblems for databases require computations to be performed on attributes. For instance, multiplying an income by a tax rate for every tuple in a salary relation, or totalling sales by department. Most implemented systems handle at most some of the possible requirements, and these in an ad hoc fashion, such as by special functions for COUNT, TOTAL, AVERAGE, etc. The failure of these approaches to adopt a framework for operations on attributes which is consistent with the operations they provide for relations leads to dislocations of syntax and to incompleteness.
To be consistent with the relational algebra, we must embody our operations on attributes in an algebraic framework and in particular, we must observe the principlesof closure and of atomicity. Closure requires that we operate on attributes to get attributes and atomicity requires that we avoid considering the structure of attributes or their connection with particular relations. The resulting formalism we call the domain algebra, and it comes in two flavours, horizontal and vertical.
2.1 Horizontal Operations
Horizontal operations are defined on any one tuple and are applied repeatedly to each tuple in a relation. They can be any arithmetical, logical or other operation or expression. They are "horizontal" because they can be imagined to operate horizontally along each row of the usual tabular representation of relations. In keeping with our algebraic principles, of course, there is no mention of tuples or of relations in the syntax:
let MARK be MIDTERM + FINAL + ASSIGNMENTS
creates an attribute MARK from the existing attributes MIDTE~, FINAL and ASSIGNMENTS.
Since MARK has been defined above in the absence of any particular data, it is a virtual attribute until it is actualized in the context of some particular relation. The most obvious mechanism for actualization is an operation of the relational algebra, such as projection. Thus, if we have a relation COURSE (STUDENT, SECTION, MIDTERM, FINAL, ASSIGNMENTS) we could project the relation:
STUDENT, MARK in COURSE.
2.2 Vertical Operations
If horizontal operations work "along the tuples", vertical operations work "down the attribute" and fill the roles of totalling, subtotalling, integrating and partial integrating and their generalizations. For the first we have reduction:
let TOTAL be red + of MARK
let COUNT be red + of i
let AVMK be TOTAL/COUNT ÷ a horizontal operation
let MAXMK be red max of ~RK
for the second we have equivalence reduction:
let SUBTOT be equiv + of >~RK by SECTION
let SUBCT be equiv + of I by SECTION
let SUBAV~ be SUBTOT/SUBCT + a horizontal operation
let SUBMXMK be equiv max of MARK by SECTION
for the third and fourth we have functional mapping and partial functional mapping:
let INTF be fcn + of F order X
let PINTF be par + of F order X b~ Y
We do not discuss these latter except to remark that, in the above simple forms, they provide poor integrals, but can be improved to perform as well as the data will allow. Note the ordering clause, which effectively specifies a sort on a given attribute or set of attributes, and makes very useful the special operations pred (predecessor in the ordering) and succ (successor in the ordering):
let NEXTEVENT be fcn succ of EVENT order TIME.
While these vertical operations of the domain algebra were motivated by practical considerations arising from the application areas we have investigated in our research, fundamental principles and basic mathematical concepts have been used in their definition. Thus, apart from the principles of algebraic closure and algebraic atomicity, we have applied the notion of "equivalence class" in equivalence reduction and the notion of "functional" in functional mapping. Note that the order clause in functional and partial functional mapping does not violate the relational abstraction that order does not matter. The result of an operation actualizing one of these attributes is still a relation, and order does not matter. Functional mapping cannot, for instance, be used to print out a given relation in order: that must be done by a specialized print routine, which is not of particular interest to the relational algebra because it is at best an identity operation.
in ACM SIGMOD Record 14(3) November 1984 view details
in ACM SIGMOD Record 14(3) November 1984 view details
in ACM SIGMOD Record 14(3) November 1984 view details
in ACM SIGMOD Record 14(3) November 1984 view details
Aldat is an attempt to build a language that is based predominantly on relational algebra, but with extensions to give more expressive power. A similar approach was adopted for a tutorial system, RDB, in relational algebra [Nikhil 19821. These languages contrast with other examples of relational DBPLs, which are basically general-purpose programming languages that have an added relational data type. The idea is to develop the relational algebra by the addition of operators, function definitions, and some form of procedural evaluation to provide, in a sense, the expressive power of other programming languages. Aldat demonstrates that a language in which the only available data types are relations and the usual base types, such as integer and string, can be used for a number of tasks that one would not normally associate with database work. In Merrett [1985b] there are a number of examples of applications of this extended relational algebra to areas as diverse as inferencing, text processing, and geometric computation. Aldat should be compared closely with APL, which similarly demonstrates the power of using an array data type with a suitably rich set of operators. The database schema declarations are essentially those given in Figure 5 and need no further elaboration here. Task 2 is shown in Figure 76. The syntax is similar to the SELECT.. . FROM.. . WHERE of SQL. ijoin performs a natural join but can also be extended to relabel the columns. To embark on the solution to Task 3, we follow the previous development of a Prolog program and first give in Figure 77 a solution to the transitive closure problem. This is a breadth-first solution to the problem in which the transitive closure is formed by recursively joining the relation Above with MadeFrom. The infix function [Component icomp Assembly] relabels the joins on the named columns and then drops that column from the relation. ujoin performs a union after the appropriate relabeling.
A partial solution to Task 3 is given in Figure 78. The first step is to obtain a relation Above (Assembly, Component, Qty), which gives the total number of times a given component part is used anywhere in the manufacture of a part. The general structure follows that of the transitive closure given before; however, a number of declarations to provide relabelings and functions on domains are needed. The form equiv...of... by provides, like GROUP BY in SQL, a method of reducing columns by some function such as addition. The second stage is to form a combined cost relation for base and composite parts in CostRel; this is done by relabeling and taking the union. Finally, the Cost in this relation is multiplied by the Qty of Above and then reduced to obtain the total cost of all (direct and indirect) subparts in Sub- Cost 2 of the relation SubCostRel, which is then added to the cost of manufacture to obtain, for every part, the total cost of manufacture in the Cost column of FinalCost.
Only the total cost of manufacture has been computed here. One could clearly write an additional computation to find the total mass and join the resulting relations together. Performing the two computations together would indicate that some further pairing functions are needed and that the algebra for relations may not be entirely independent of the algebra of operations required on domains.
The efficiency of this solution is, of course, questionable. Whether this is a more efficient solution than the recursive programs we have presented elsewhere depends, among other things, on the structure of the database. A database for which the number of parts is large but for which the MadeFrom relation is small would not be appropriate for this method. However, manufacturing systems are frequently set up to produce one or two complete assemblies (e.g., a car). In such cases, the solution presented here would be competitive with the memoized versions we have examined earlier. Note that in this method we are implicitly memoizing the intermediate results. In contrast to Prolog, part of the complexity of the Aldat solution arises from the need to relabel columns. Any language based on the relational algebra needs to address this problem.
in [ACM] ACM Computing Surveys (CSUR) 19(2) June 1987 view details
in [ACM] ACM Computing Surveys (CSUR) 19(2) June 1987 view details
Introduction
Aldat is a project to develop programming languages based on the algebraic approach to data. The main persistent data type we have investigated is the relation, which we have used to represent data in many diverse applications. The significance of the family of Aldat languages that has resulted is the algebraic operations on relations they embed, enabling the applications to be written at a very high level. These operations form an extension and generalization of Codd's relational algebra. They allow administrative information systems, pictorial databases, text, and even knowledge bases to be Implemented without any specific extensions to the language needed for any individual application.
The three important aspects of data on secondary storage are size, sharing and persistence. Database research has focussed largely on the first two, assuming the latter.
Operations on data which is too large to be brought into RAM have been the objective, first of query languages and, subsequently, of database programming languages. Since such large amounts of data are often a common resource, means were developed to permit concurrent access without rendering the data inconsistent. The fact that the data outlives the execution of any particular transaction or program was taken for granted until the work of the Data Curator project (see, for instance [ABCCM831). This work introduced the principle that all data objects have the same rights to persistence or transience, and present purpose is to demonstrate just how far we can get with a sole data type, the relation of database research. The value of doing this in the present context is to complement the approach which uses many data types. Data types other than relations are needed for sophisticated work, and to them the principle that persistence is "orthogonal" - independent of data type - must certainly apply. We do not discuss these but content ourselves with exploring the applicability of relations alone. Their persistence poses no new implementation problems.
Persistence is hardly discussed explicitly in this paper, because of our database perspective: that relations persist is assumed in all implementations we have made of Aldat, and we supply only an explicit delete operator to remove any named relations which we do not want to keep. Large amounts of data cause no difficulty, since all operators introduced are database operators and intended for large databases on secondary storage. Sharing is also not explicitly discussed because that takes us into the province of editors, which we only briefly mention, and into aspects of concurrency control an absence thereof which are the concern of on-going work. This paper reviews the Aldat formalism and extensions to the relational algebra. Our main objective is to establish the advantages of Aldat programming on persistent data by developing examples from some of the areas of Current interest in database programmIng. Administrative data processing having been extensively investigated in the past decade and a half, we look instead at more recently interesting topics of text, pictures and logic programming.
Our interest in all cases is not just the representation of the appropriate data but the operations which permit us to process the data. In formulating operations we adhere to the algebraic principles: the principle of closure requires that operations on a type of object result in objects of the same type; and the principle of abstraction requires that neither the structure of objects nor their context should be of concern to the operations applied to them. Relations are very suitable as objects to represent persistent data these algebraic principles, because they usually represent quantities of data at least the size of a physical block and because the principle of abstraction tends to allow us to process whole blocks at a time. This leads us to implementation considerations, which are important in our work but which we do not discuss further here.
In the first two sections, we summarize the extended relational algebra and the domain algebra respectively. Section 3 gives programming applications to text processing and to geometrical computations. For text, we compute the concordance of a document and the similarity coefficients of several documents, a first step in cluster analysis. For diagrams, we give a point-in-polygon algorithm and we calculate the intersection points of two closed lines. In section 4, recursive relations are introduced. Recursion is illustrated for classical fixed-point problems such as bill-of-materials and routing, then for logic programming to do both Horn clause and syllogistic deductions. Finally, the problem of property inheritance, as it arises in semantic networks and data types, is solved as a closure computation in the relation algebra.
in Data Types and Persistence. Atkinson, MP, Buneman, OP, Morrison, R (eds), Proc. 1st Workshop on Persistent Object Systems, Appin, Scotland, 1985. In Series: Topics in Information Systems. Springer-Verlag, ISBN 3-540-18785-5. 1988 view details
in Data Types and Persistence. Atkinson, MP, Buneman, OP, Morrison, R (eds), Proc. 1st Workshop on Persistent Object Systems, Appin, Scotland, 1985. In Series: Topics in Information Systems. Springer-Verlag, ISBN 3-540-18785-5. 1988 view details
in Data Types and Persistence. Atkinson, MP, Buneman, OP, Morrison, R (eds), Proc. 1st Workshop on Persistent Object Systems, Appin, Scotland, 1985. In Series: Topics in Information Systems. Springer-Verlag, ISBN 3-540-18785-5. 1988 view details
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 ).
in Data Types and Persistence. Atkinson, MP, Buneman, OP, Morrison, R (eds), Proc. 1st Workshop on Persistent Object Systems, Appin, Scotland, 1985. In Series: Topics in Information Systems. Springer-Verlag, ISBN 3-540-18785-5. 1988 view details
Introduction
The purpose of this paper is to present the subset of temporal logic, that has been found useful and accessible to programmers of communications software, and to present the additional assumptions and structuring operators which had to be added to make this subset into a viable programming language. The resulting language is called L.0. The fact that enhancements to temporal logic are necessary to make it a viable programming language should not be surprising, since a standard criticism of temporal logic is that it is: global, non-modular, and non-compositional.
A somewhat restricted first version is currently in use at Bellcore as an executable specification and prototyping language. The applications of L.0 include specification of communications protocols, services, and network performance models. A brief overview of the structure of the applications of the language will be presented at the end of the paper. The design decisions of L.0, which will be discussed in this paper include: the particular subset of temporal formulas allowed, the particular restricted form of quantification used, the choice of the structure for the states, the choice of the set of atomic predicates, the introduction of structuring operators, and the particular solution to the frame problem chosen. The reason that a solution to the frame problem is needed is that an L.0 specification is viewed as forcing changes in the previous state, rather than completely specifying each state. One apparent valuable side- effect of these choices is to make temporal formulas rcadablc and writable, by industrial programmers.
The close fit between L.0 and temporal logic is especially interesting because the design and development process of L.0 have been user-centered. The control and structuring constructs were designed to be compatible with a programmers intuitive operational view of the problem. Various user groups within Bellcore have used L.0, and its predecessor C&E to specify prototypes of communications software. The restrictions of the temporal constructs are directly traceable to specific problems encountered by the users. It is not surprising that a language designed for the specification of various types of communications software, which are reactive systems, should be fundamentally related to temporal logic. For the problem of specification and verification of reactive systems has been one of the principal motivations and primary applications of temporal logic.
in ACM SIGSOFT Software Engineering Notes , Conference proceedings on Formal methods in software development April 1990 15(4) view details
The expert system shell consists of editors for entering rule schemata, rules and facts, of consistency checkers for uniqueness and monotonicity of rules, and of an inference engine which can handle inequalities and ranges as well as equalities and which can do numerical computations.
The principle result of this work is the ease with which the expert system shell was built in Aldat, a language intended for general database work, not for building expert systems. Another important result is the flexibility of the code: when it became apparent that monotonicity of rules is an important constraint, we were easily able to incorporate a checker into the system, which the commercial systems we were following are not able to do; generalization of simple inequalities to ranges and general boolean combinations of inequalities were not easy to do but also simplified the implementation. A final result is that the expert system shell has been implemented in a database language, thus making trivial the interface between an expert system and an extensive database
External link: Online copy
in ACM SIGSOFT Software Engineering Notes , Conference proceedings on Formal methods in software development April 1990 15(4) view details
External link: Onlikne copy
in ACM SIGSOFT Software Engineering Notes , Conference proceedings on Formal methods in software development April 1990 15(4) view details
Resources
- ALDAT logo
- Merrett's Introduction to Databases and to the Aldat Project at McGill
external link - Aldat: Database Perspective
A relation is an abstraction over files, and Aldat is designed to support programming at this level of abstraction. In particular, neither records (tuples) nor their order are imposed on the programmer's concerns. Aldat is also designed to provide the bulk operations that are well supported by secondary storage, where files reside, and which has totally different memory charateristics from RAM. external link