Oracle FAQ Your Portal to the Oracle Knowledge Grid

Home -> Community -> Usenet -> comp.databases.theory -> Re: Nested Sets vs. Nested Intervals

Re: Nested Sets vs. Nested Intervals

From: <>
Date: 12 Nov 2005 05:54:21 -0800
Message-ID: <>

> Could you please provide a more compact graph (by Nelson, Carson or
> whatever other semantic metadology) which is perhaps a little bit more
> impressive?

Sorry for the late response.

Yes, it is essential to provide more compact representations, for semantic structures, than the Mneson Calculus or the base graph, for cases where the MC or the base graph inflates the number of calculus or graph elements. One such case is the attribute structure, so I'll discuss this case briefly. Note it equates a labeled edge.

          attr. name
subject -------------> value

Replacing the attribute topologies in the base graph for labelled edges should reduce the edge count by 2 or 3 times. Try it.

Also textual languages may be created that express the semantic structures directly e.g.

attribute (subject, attr_name, value);

which can be defined with the primitives

new_vertex (x);

connect (subject, x);
connect (attr_name, x);
connect (x, value);

The base graph serves to represent all different semantic structures in the same formalism, and the Mneson Calculus (operating on the base graph) is supposed to serve as the query plan and optimization component. As I said in another message, also higher level query languages should exist that map into the Mneson Calculus e.g. the very common query pattern

members of set X having attribute Y with value Z

of which we have seen an instance before

T(Employees) ^ S[T(SSN) ^ S(123456789)]

could be a 'macro' or some such, with translation to the Mneson Calculus

TX ^ S(TY ^ SZ)

Remember ^ means intersection.

In meta-expressions (with variables only) I drop the functional parenthesis.

BTW a possible optimization of the above involves the derivation

TX ^ S(TY ^ SZ)
= TX ^ STY ^ SSZ
= T{x1} ^ ... ^ T{xm} ^ ST{y1} ^ ... ^ ST{yn} ^ SS{z1} ^ ... ^ SS{zl}

(where X = {x1, ..., xm}, etc.) because there are efficient methods to compute the n-ary intersection of A{x} terms, where A is T or S; I'm studying their extension to include AA{x} terms, see the thread "Implementing a graph algebra"

I often use the Mneson Calculus and the base graph directly when modelling examples for a number of reasons:

Received on Sat Nov 12 2005 - 07:54:21 CST

Original text of this message