Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> Re: Nested Sets vs. Nested Intervals
I'll not give an algebra for RDF here since RAL is readily available
and I have my own algebra to worry about. So I'll give you a sketch of
the latter instead.
Mneson is a graph-based metamodel of data, based on a graph with the following properties:
(a) A data vertex or datum represents an atomic value of data e.g. an
integer, a real number, a symbol. The value of a data vertex is the
identity of the vertex.
(b) A pivot has no intrinsic value but it has nevertheless a unique
identity. In practice a serial number is used to identify pivot
vertices.
3. There are no island vertices. There may be, however, island subgraphs.
A database instance is expressed in the base structure by means of special subgraph topologies that represent complex data entities like attributes, lists, sets, etc. [1] A possible definition is as follows:
Attribute. An attribute of name x1 and value x2 is represented by an
attribute instance x3 such that x1 connects to x3 and x3 connects to
x2. The attribute is connected to its subject x0 by connecting x0 to
x3. For example suppose that x5 represents an employee; the fact that
x5 has Social Security Number, or SSN (the attribute name) 123456789
(the attribute value) is expressed by connecting: x5 to x6, "SSN" to
x6, x6 to 123456789.
Set. For a vertex x that represents a set, the targets of x represent the members of the set. In parlance we say x is the 'head' of the set. Note this is a different object than the algebraic type set of vertices below.
Etc.
The topologies may overlap, e.g. a vertex x that is an attribute type may also be the member of a set, or even a set itself in which case the respective attribute instance is a member of x.
An algebra (called the Mneson Calculus) is defined on the base graph as follows. The algebraic type is the set of vertices. The operations include the set operations (intersection, union, etc.) and the (unary) adjacency operators T, S for Targets, Sources, with the obvious semantics:
T (X) = {y : y is a target of x, x in X} S (X) = {y : y is a source of x, x in X}
The Mneson Calculus serves as a query language. For example, the following query retrieves the employee with SSN 123456789:
T ({Employees}) ^ S [T ({"SSN"}) ^ S({123456789})]
where ^ means set intersection.
Singleton arguments are very common so we take the liberty of ommiting the {}, for clarity; and we want to focus on algebraic issues so often we also ommit the "" around literals. With these simplifications the expression above becomes
T (Employees) ^ S [T (SSN) ^ S (123456789)]
This example of course assumes a schema where vertex Employees is the head of the set of employees.