What Remains Of The Relational Model If We Drop The Relvars?

Given a relational database we

Given a table-less database we generally should be able to create a corresponding relational database but two important moments should be considered:

Relational variable is a storage unit in a relational database. Consistency constraints and queries are expressed either in the form of relational algebra operations over the values of these relational variables or in the terms of predicate calculus. The latter operates on predicates implicitly backing up these relational variable. ^[1]

Similar facilities are available in the table-less data model.

Set Of Tuples (possibly with different attribute sets) is the main data entity in the table-less data model (like relational value is the main data entity in the relational data model).

As this concept will be so common in the following discussion let us use tupset as the abbrevation for “set of tuples”.

Let us call the set of attributes present in a tuple the tuple type.

Mapping of attributes to domains is global to the database and therefore not included into the tuple type (in contrast to relation type in the relational data model).

The whole database is just a single variable that has an almost arbitrary tupset as its value.

Just like a relational DBMS our table-less DBMS needs a catalong as a way to query and possibly modify metadata such as

Like a catalog of a relational database that is visible to users as a set of special “system” relvars a catalog in table-less database should probably be visible as a set of “system” attributes that are used to build “system tuples”.

Probably user shouldn't be allowed to store arbitrary tuples with “system” attributes to the database. Probably there should be a predefined fixed number of “system” typle types and “system” attributes shouldn't be allowed to be stored into the database as part of any other tuple types.

If a consistency constraints system able to enforce similar limitations over user-defined attributes will be built into the data model, then the limitaions imposed on “system” attributes would be visible (but not modifiable) via the catalog too.

On the other hand at the current time it is not clear to the author if such limitation should be imposed on system attributes at all. It may prove usefull to attach special meaning to certain tuple tupes but not limit the user in other usages of system attributes except the key uniquness consistency constraints.

Let us say that a tupset is uniform iff the sets of attributes in all the tuples of the tupset are the same (tuples contain exactly the same attributes). For example the following tupset is not uniform:

while the next one is

Empty tupset is uniform by definition.

Uniform tupset is just a classical relational value.

Let us define the projection operation: projection of a tupset over attribute set {a_1,a_2,...a_n} is the result of the following steps:

As we always operate on sets of tuples, exclusion of repeating tuples is implied on every step where it is necessary.

We can apply the projection operation to the whole database or to any intermidiate tupset. Even if the source tupset is not a uniform the result of projection is guaranteed to be uniform.

All the relational algebra operations are performable over uniform tupsets (aka relvals), projections are uniform tupsets, so it should be easy to prove that the DML we're sketching now for our table-less data model will be relationally full.

Given some table-less database with N attributes defined we can build 2**N-1 ^[2] subsets of the whole attribute set and respectively build 2**N-1 projections of the contents of the database.

These are 2**N-1 relations that may be considered to be stored in the table-less database. They are a close analog of the relational variables from the relational database world.

These are also the 2**N-1 implicit predicates of our table-less database.

We shall call them stored relations and stored predicates further on.

These stored predicates/relations are naturally named and denoted by their attribute sets. The relation header (also called predicate type in this paper) coming from the relational data model has become the name of table-less relvars and their implicit predicates analog.

These relations/predicates are not independent however, the following rule holds:

where {i_1,i_2,...i_m} is any subset of {1,2,...n}.

While in relational data model consistency constraints are associated to relvars in the table-less data model they may be associated to the stored relations/predicates.

All kinds of constraints known for relational databases should be possible, while additional kinds are also foreseen. For example, we may prohibit to store a tuple of the form

without storing the tuple

These 2**N-1 implicit predicates of the database are also the entity that informal predicates may be associated to.

It should be possible to specify consistency constraints similar to unique key constraints in relational data model. Of course it may be done by a formal predicate of the following sort:

where x1, x2, y and z are variables (implicitly universally quantified) and pc1, pc2, v are constants denoting the names of attributes; this constraints says that in the {pc1,pc2,v} relation pc1,pc2 pair serves as a unique key.

But we may also go for games of another sort. Imagine we have system attributes named 'attr' and 'func_depends_upon' and 'mult_depends_upon'. Imagine we use these attributes to store functional and multiple dependecy meta-information directly into the database (this becomes part of the catalog). Let for example the following information about attributes name 'v1','v2' and 'v3' be stored:

That is we have a dependency chain: v1->v2->v3. Then, whenever user requests to insert into the database tuple of the form

two tuples are inserted instead:

Similarly, the following “joining implication” is considered to be true (and used when evaluating any requests, etc):

(again, x, y, z are universally quantified variables.)

This is what may be called “automatic normalization”. As for any other part of this paper implications of the proposed ideas are note clear yet.

The design of the table-less data model certainly implies having duductive-database style features to define derived relations (aka VIEW in SQL). A Datalog style mechanism [Ceri] will certainly fit well into the model.

Any of these has not been designed yet for the model, but possibly the DML could have a Datalog style subset ^[3] [Ceri] for defining derived relations, consistency constraints, and probably database queries.

The author also feels that probably no special DDL will be needed if all the manipulations will be performable by updating the catalog of the database via regular DML operations.

As the original Datalog does not provide any update operations it has not yet been decided on what the whole DML for the model might look like. The question is wide open (as many others too).

While the relational model did imply at least a naive implementation technique (one relvar - one file or file fraction) implementations of table-less data model will need to carefully guess the physical data schema if one is not advised by the user (for example because the use is not an IT professional).

It is anticipated that either direct setup of phisical data schema by user or adaptive DBMS self-tune up will significantly influence performance with medium and large sized databases.

However at small and tiny data volumes even the most naive implementations are expected to deliver acceptable performance.

Concurrent data access implies acquiring implicit read and write locks for data.

The relational data model provides a good choice of objects that may be used for locking: relvars, tuple implementation-dependent groups (pages), individual tuples.

Realizations of table-less data model will need special efforts to develop an adequate locking model.