Hi,
In general, directed acyclic graphs can require arbitrarily large amounts
of compution to get any answers out of. If your classification scheme is a
tree, there is a neat trick I have seen a couple of times to precompute all
the answers.
One reference, I believe, is in Joe Celko's SQL for Smarties book.
Roughly, this is how it works.
Write down your entire classification scheme as an outline, one entry per
line, with say indenting indicating level of subclassification.
Number all the lines, 1 2 3 ...
All the subcategories of any entry are the lines with line # >= entry's
line # and < line # of the next entry of same indent level as starting
entry. Including a column with the line # of the next entry of same indent
level makes this even easier.
So, all kids of entry can be retrieved in one query.
Inserting/ deleting entries is a bit tricky -- you have to update all line
numbers after the modification, and the 'next entry of this indent level'
column of every entry after the modification, and one before it.
So thats a possible relational solution, precompute all the results.
If you want live recursive queries... you're going to be writing some code.
I'm working a bit on rule engine integration with jboss, this may
eventually provide some kind of declarative recursive query capability a la
prolog, although what I'm looking at so far is forward chaining only.
I'm very curious, can you tell us more about your situation in which you
need a recursive data structure managed through a transaction monitor? One
thing I'm missing with my rule engine thinking is some realistic examples.
Thanks
david jencks
On 2001.02.16 08:22:28 -0500 Keith L. Musser wrote:
> In a finder method...
>
> SELECT Things.ID FROM Things, ThingCategory WHERE
> ThingCategory.CategoryID='Animal';
>
> Is that what you want??
>
> Or do you want things which are also sub-categories of 'Animal'? In
> that case, you could enumerate the subcategories of animal, and then put
> an 'OR' clause at the end of the SELECT.
>
> -----Original Message-----
> From: Peter Routtier-Wone <[EMAIL PROTECTED]>
> To: JBoss-User <[EMAIL PROTECTED]>
> Date: Friday, February 16, 2001 8:01 AM
> Subject: Re: [jBoss-User] Recursive data structures
>
>
> >> I also fail to understand why it is a problem. How is recursive
> >references
> >> different to any other entity relationship? Just store a PK, a
> Handle,
> >> whatever...
> >
> >In a schema I have a Category table related m:m to itself via a
> Subcategory
> >table, allowing the recursive construction of taxonomies of
> indeterminate
> >depth. This is the self-referential part (what I called a recursive
> >structure).
> >
> >There is also a Thing table, and a ThingCategory table that allows
> things to
> >be assigned any number of classifications.
> >
> >It is possible for categories to apply to a thing indirectly by
> implication
> >of what might be described as taxonomic inheritance. (In fact the
> taxonomy
> >is potentially a network rather than an hierarchy, so there can be
> multiple
> >inheritance, but that is another matter.)
> >
> >Now an example of what's been bamboozling me.
> >
> >Suppose the taxonomy were of species; Butterfly would be a subclass of
> >Insect, which in turn subclasses Animal, likewise Organic. Consider a
> >particular butterfly called Jim, represented by a row in the Thing
> table.
> >
> >We assert that Jim is a butterfly by creating a suitable row in the
> >ThingCategory table. However, because Butterfly is a subcategory of
> Insect
> >(etc), by implication Jim is a member of the classes insect, animal and
> >organic. Inheritance.
> >
> >Certainly it is possible to materialise the categories that apply by
> >implication to Jim (or any other thing) but I am somewhat at a loss to
> say
> >how one might (efficiently) go about retrieving a set of Things that
> are
> >members of the category Animal.
> >
> >The problem, as I see it, is primarily one of inability on my part to
> >express the above ideas in EJB terms. It is with the semantics of the
> model
> >that I most want help. On re-reading the EJB tome currently ballasting
> my
> >desk, I now suspect that this will be done with finder methods. I am in
> the
> >process of coding a utility class that does the recursive expansion of
> >categories given a starting category, in order to succinctly express
> the
> >finder method..
> >
> >
> >
> >--
> >--------------------------------------------------------------
> >To subscribe: [EMAIL PROTECTED]
> >To unsubscribe: [EMAIL PROTECTED]
> >List Help?: [EMAIL PROTECTED]
>
>
>
> --
> --------------------------------------------------------------
> To subscribe: [EMAIL PROTECTED]
> To unsubscribe: [EMAIL PROTECTED]
> List Help?: [EMAIL PROTECTED]
>
>
>
--
--------------------------------------------------------------
To subscribe: [EMAIL PROTECTED]
To unsubscribe: [EMAIL PROTECTED]
List Help?: [EMAIL PROTECTED]
