Copyright ©2008 T. H. Merrett


Computer memory comes in a variety of forms, two principle ones being primary memory ("RAM"), and secondary memory ("SS") which includes hard and floppy disks and CD-ROM. Data structures and languages for RAM are core computer science. The Aldat Project is concerned with language and data structures for SS.

Secondary storage is distinguished from RAM primarily by the long times required to find data, relative to the times required to transfer it for processing. Different memory organization needs different data structures, algorithms, and languages.

There are many general-purpose languages for RAM and it is unusual to encounter languages specialized for individual applications. Languages for SS are usually query languages rather than full programming languages, and they are specialized both to particular data structures (hierarchies, linked lists, tables, etc.) and to particular applications (administrative data, spatio-temporal data, logic data, semistructured data, etc.) For instance, RAM has no spatio-temporal dialect of FORTRAN or Java, but SS has Arc-Info while commercial relational databases (SS) do not have comparable spatial capability except as add-ons.

Aldat is a general purpose SS programming language developed at McGill over the past several years. This development has been empirical, following and sometimes leading the main thrusts of database research (including hierarchies, data-structure-set, multiset relations, entities and relationships, object-oriented databases, logic databases, active databases, data warehousing, data mining, semistructured data, and Internet data) with the aim of including all the evolving possibilities of SS programming. The difficulties of doing this are captured in the phrase "impedance mismatch", which characterizes the gaps among applications on one hand and between querying and programming on the other.

The language and data abstractions with which Aldat accommodates SS also turn out to be valuable in programming for RAM, and so our work has benefits for all computer science.

Documentation on Aldat

For an overview, see Aldat (45KB, including links to 4 other pages)

For tutorial material in the form of a course, see course 612.

T. H. Merrett Aldat: a Retrospective on a Work in Progress PDF paper 418KB
Copyright 2006 Elsevier B. V. noting the following
Permission to make electronic copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to republish from: "Permissions", Elsevier Global Rights Department.
The author gratefully acknowledges support from the taxpayers of Quebec and of Canada who have paid his salary and research grants while this work was developed at McGill University, and from his students (who built the implementations and investigated the data structures and algorithms) and their funding agencies.

See also Aldat: Database Perspective 14KB

JavaRelix, an implementation of Aldat

Here is relix.tar.gz Copyright ©2008 T. H. Merrett (10M), an implementation for UNIX supplied without support, warranty or liability and as-is. It is version 0.96 and does not support everything the research papers and documents talk about.

It comes without documentation except the following installation instructions.

  1. Select your preferred destination for the file JavaRelix.jar (for instance, choose or create a java package repository folder); copy it there. As an example, suppose you copy JavaRelix.jar to the following directory:
  2. Open the file "relix" using a text editor. For instance, from the command line write:
    pico relix
  3. Replace the two instances of YOUR_PATH with the path of the folder you chose. In our example, I would replace YOUR_PATH by
  4. Save the file. Adjust the permissions of relix by typing the following command in the terminal:
    chmod 755 relix
  5. Copy the file "relix" to the folder
  6. Launch JRelix by typing "relix" in the command line. You might need to restart your shell the first time you try to run the command.

Here is relix-src0.96.tar.gz Copyright ©2008 T. H. Merrett (15M) source code. You are completely on your own. The usual open source terms apply: modify as you like but acknowledge clearly the provenance as The Aldat Project, McGill University; fix the bugs yourself.

Implementation data structures and algorithms for SS

JRelix is a main-memory (RAM) implementation of Aldat. For a discussion of techniques for secondary storage (SS), see course 420.