[sc34wg3] Re: Going beyond SIPs?

[Jan Algermissen]

Robert Barta wrote:
> 
> On Thu, Sep 02, 2004 at 10:40:48AM +0200, Jan Algermissen wrote:
> > In TMTK (publication pending, I know) you would create a TMA (ultimately
> > an object that is loaded at run time and drives the whole engine) and in that
> > TMA a property that serves as the SIDP that 'controls' *your* merging
> > desire.
> ...
> > Theoretically, this is actually quite easy....it just took me about a year
> > to get the generic merging algorithm in place and provide some other
> > complexity than O(N^4) :-)
> 
> What can we do to press you to come forward with a description for
> this? Bribe? Or would threats work? :-)

The problem is that you would not understand it, unless I explain quite
a bit of my implementation approach. Unfortunately I don't have the 
time to do all that typing right now. Also, the merging section of the code
is not really documented. As soon as it is a bit more understandable, I
will write something up.

The basic story is, that TMTK totally decouples value types and their storage
implementations from the core engine. Value types are basically classes that
are constrained to at least provide a minimal set of methods (the ones needed
by the core) and value stores are specialized storage implementations that
also need to implement a certain interface. The value stores really are doing
the difficult stuff and that is to provide reasonably fast implementations of
the various functions called on them (primarily during merging).

Example: During merging, there are *LOTS* of invocations of the not_disjoint(v1,v2)
operator on values of type 'locator-set'. More precisely, scans are opened on the
value store in the form

scan = value_store.openScan(value1,operator,args)
while( scan.hasMore() )
	value2 = scan.next()

so, given operator to be "not_disjoint", this scan will find all values that are
not disjoint with value1

The burdon to implement this operator in O(log(N)) is on the value store
implementation (where else could it be, given that arbitrary value types
are allowed).

That's basically the hot spot. If you have Date's book at hand, it might be
interesting to read chapter 25 (7th ed.) "Object Relational Databases",
especially the explanation why RDBMS vendors do NOT allow arbitrary data types
(in my book 25.4 "Implementation Issues"), although covered by the relational
model as such.

Hope I can send you more merging documentation some day.


Jan





> 
> \rho
> _______________________________________________
> sc34wg3 mailing list
> sc34wg3@isotopicmaps.org
> http://www.isotopicmaps.org/mailman/listinfo/sc34wg3

-- 
Jan Algermissen                           http://www.topicmapping.com
Consultant & Programmer	                  http://www.gooseworks.org