During the Middle Ages, most information was passed by the oral tradition. Bards codified stories and performed them. Manuscripts and libraries, such as there were any, were owned by the Catholic Church.

In the Seventh Century, the Moors lost their Spanish foothold in Europe. The great Arabic libraries fell into Christian hands. These libraries also became the property of the Catholic Church. Monks translated books to Latin. Preservation is the major theme of libraries and of scholarship.

Paper arrived in Europe during the Eleventh and Twelfth Centuries. Prior to this time, manuscripts were usually written on parchment. Parchment is made from skin and is very expensive as compared to paper.

Nearly as a direct consequence of the introduction of paper is the forming of secular universities starting in the Twelfth Century. Vast collections of books, copied by hand, formed the nucleus that grouped a collection of scholars (note: vast is measured according to the scale of the time).

The printing press (in Europe) was invented about 1450. This altered the cost and availability of books. Literary was still very restricted and books still were very expensive to the average person.

The scholarly journal started in the 17th Century. This is a fast form of publishing that was required to keep up with the pace of the times.

Public libraries came in the 18th and 19th Centuries. The lending library came into common use in the 18th Century, while free public library became common in the 19th Century. Literary also became nearly universal due to free public education. (However, note that only half the world is literate today).

A more recent change is the introduction of the Xerox 914 copier. This device changed the way that information stored on paper can be reproduced.

The first information was stored on tape or in boxes of cards. As computers and disks became more reliable, file systems were used for the permanent storage of information (CTSS was the first system to maintain the system sources on disk in the early 1960's). Access methods for files became more commonplace, particularly within IBM. Database systems evolved that used either the hierarchical data model (e. g., IMS) or the network data model (e. g., CODASYL). More recently, the relational data model has been both a theoretical and a commercial success.

However, computer databases have only managed to capture a small fraction of the information used by society. In their marketing, Wang claims that only 1% of stored information for businesses is in "DP" and 3% on microfilm or microfiche, while the remaining 96% is on paper.

There are many reasons why paper based systems are so popular. Computer systems are expensive, are of limited capacity, require access via a terminal, are hard to use, and require special training. The database systems are large and complex. The data models are rigid. Although rigidity is a feature when the data is well structured (such as account payable), it is a determent when the information is not well structured (as in a literature).

Anyone that follows the computer business is very aware of technology change. We often hear of evolutions in the decreasing cost of main memory, fast commercial microprocessors, workstations, scanners, and Fax. Also coming is higher speed communications (FDDI at 100 Megabits/second), cheaper and faster electronic printers, and high capacity magnetic disks. Optical disks and optical disk jukeboxes can put on-line lots of data at a cheap cost per byte. Information services and CD ROM publishing will continue to grow.

Often overlooked are the potential of high capacity optical and magnetic tapes. If these systems can be made to be reliable and have short latencies, then they have the potential to store a good fraction of a terabyte for a few thousand dollars, with access time of a few seconds.

There have been vast changes over fifteen centuries. Where literature was once controlled by religion, it is now (almost) freely available. Where once it was important to preserve literature, it is now important to increase literature. Where the public used to be illiterate, now half of the world is literate. Where the average person was a serf, now we are faced with the post-industrial information worker. Where the media was Parchment or papyrus, now the media is evolving into an electronic one.

We have the potential for a "Future Shock." The amount of information growing. The speed of delivery is increasing. The media and delivery systems are evolving. Old schemes will not work forever.

We also have opportunity. Finding, access, presentation, organization, creation, and contributing to the store of knowledge of mankind will be changing. Reviews and criticism will have to evolve. Collaboration will increase. We need the infrastructure to enable this change. Part of this infrastructure is the database.

In keeping with the theme of literature, nodes in the database are also called documents. A node may not have a real world analogy that the reader might consider a document. The node's contents might be the number three. The node might be a source or object "file."

The system can handle a large number of nodes (e. g., millions). A node can be of any size: one byte long, or a gigabyte. Nodes (or node parts) will be archived to on-line tertiary storage (e. g., an optical disk jukebox).

Nodes have a contents. The contents of a node is a primitive value: it is a type and a value (of that type). Only a dozen or so types are understood by the server. For example, strings (any length), dates, floats (32 bit), and integers (32 bit and infinite precision) are supported. In addition, other types may be stored without the server understanding what the value means. For example, ODA documents and compressed scanned images can be stored, but the server treats them as uninterpreted bytes. The client code, not running on the server, is expected to provide the semantics for these types. The type space is fairly large (almost 32 bits) and is administrated by a database administrator without much support from the system.

Nodes can be connected by links (hypertext) [Bush45, Engl??, Nels81]. A link is a directed pointer between two nodes. The link has a type, which is just a string. An inlink or a to link are links that point at a node, while an outlink or a from link are links leaving a node.

Nodes can efficiently determine both their inlinks and outlinks. Although links are directional, they can be followed in either way. Links are themselves nodes, so they can have attributes. Yggdrasil provides only node to node links. If a client wants a link to point at part of a node, then the client has to encode this as a property on the link.

Nodes have a set of attributes or properties. Both terms are used interchangeably. The attributes of a node are a set of attribute name and attribute value pairs. The attribute name is just a string that identifies the attribute. The attribute value is a set of fields. Each field has a field name and a field value. The field value is a set of primitive values. Each of the above sets may be ordered or unordered (default is unordered).

Yggdrasil is designed to hold millions of nodes. Without some help, it is easy to get "lost in (hyper) space." Both databases and file systems have grouping mechanisms. Relational databases have relations that group similar nodes together. File systems have (hierarchical) directories that are a well accepted improvement over a flat name space. Some sort of context or grouping is needed by any large system.

Containers are the context mechanism in Yggdrasil. A container is a (possibly ordered) set of nodes. A container is associated with a root node of the container (analogous to directory in a file system). A node can belong to any number of containers. In addition, a container can be a sub-container of another container. A container can be the sub-container of any number of containers. Loops are allowed in the sub-container relation (i. e., it is a directed graph, not just a DAG).

One of the powers of relational databases is the non-navigational, relational access to data. Relations are just sets of similar items. The access to data is non-navigational in that the client characterizes what the matching data looks like, as opposed to providing the systems with an (imperative) program to get the data. Sometimes this is called non-procedural access.

Both navigational and non-navigational access are desirable. Hypertext systems are outstanding for browsing (navigating), but are not good at finding starting points for browsing.

Containers can be configured to automatically maintain indices. For any attribute, all nodes that can be reached in the transitive closure of the containment graph starting at the container are indexed. Index maintenance is specified by the "owner" of the subtree or by the database administrator. An index at a level replicates data of indices at lower levels. We intend that the query language will use the notion of container, so that often the indices can be used during query evaluation. Filters (similar to SELECT and join in a RDBMS) will be used to restrict the results of expansions.

Any node can act as a directory. It is natural to expect the root nodes of containers to be directories, but the system does not make this restriction. A special system maintained property provides the name and node binding. Not all nodes have to be named and a node can have many names.

Naming can also help with the "lost in (hyper) space" problem. However, a major consequence of providing naming is that Yggdrasil can provide a view of a database that is a file system or file server. A file server front-end can be built that talks a file server protocol, and provides access to some of the data in the server. Links are not modeled in all file server protocols, so they usually disappear from the file server view. A particular file server protocol may have a restricted notion of attributes (e. g., a fixed number of them of fixed types) or the protocol may not type the contents of files. Directories may or may not have contents. In any case, the file server front-end provides a view of the database that is suitable for programs that are designed to talk to a file server.

A few front-ends are anticipated. NFS, Xerox's NS Filing Protocol, and ANSI/CCITT/OSI Filing and Retrieval are all candidates for front-ends. A server is not restricted to only one front-end filing protocol.

One prime benefit of this is to unify file systems and databases. There is one permanent storage mechanism. Different views are provided for different software. It is possible to maintain information in the database, and "publish" it via the naming system.

Nodes can have have versions, revisions, and alternatives. A node, then, is really a tree of states. States can differ in any of contents, properties, links, containers to which it belongs, and its value as a container. A new branch may be started from any state in the tree. This is called an alternative. Major changes along a branch are called versions while minor changes are called revisions. Changes are (usually) applied at the leaves of the tree. A new version or revision is built whenever a transaction commits that changes some part of the node. The version or revision is added to the version chain for the current alternative. A new version collapses the revisions between it and the previous version.

Yggdrasil will use some "delta" and compression techniques. The system will be optimized for access to the current version.

Yggdrasil will not directly provide for the merging of alternatives and/or versions. Client level code can do the merge in an application specific manner for a container.