Re: Nested Sets vs. Nested Intervals
Date: 12 Nov 2005 05:54:21 -0800
Message-ID: <1131803661.162985.170950_at_z14g2000cwz.googlegroups.com>
> 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
Replacing the attribute topologies in the base graph for labelled edges
subject -------------> value
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