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:

  • some very common semantic structures e.g. set map directly to a base structure (untyped link)
  • it allows to mix structures
  • I don't have a higher level device of choice yet
  • I'm familiar with the MC and the base structure and the topologies
  • I'm studying the MC as a query planning and optimization device
Received on Sat Nov 12 2005 - 14:54:21 CET

Original text of this message