Apologies for the mass cross-posting: I haven't been able to find a single
answer or reference for the problem below (googling didn't help), and
was hoping someone could point me to something helpful. I'm convinced
there's a well-known answer here that I just can't find :(
We're modeling a collection of (finite mathematical) sets, where sets
may contain each other as subsets.
For example, set X may be defined as "{7,11,15} + Y" meaning X
contains 7, 11, 15, and all the members of set Y. Set Y could then be
"{15,20,25} + Z", and Z might be "{7,14,30}" with no subsets.
Of course, no set includes itself, directly or indirectly.
However, one set may include many other subsets (eg, X may include
both Y and Z), and one set may be included in many others (eg, X may
be included in sets V and W).
If the sets were nodes in a directed graph, the graph would be
acyclic, but not a tree. I believe this is called a "lattice"(?).
How can we efficiently model this "lattice" of sets either using SQL
or some other technique? Specifically:
% Add or remove members/subsets from a set and have the changes
"bubble up" the lattice efficiently.
% Find all members of a set X, efficiently traversing subsets. In
other words, find all nodes/leaves of the subtree rooted at X
% For a given set X, find all sets that contain X as a subset,
directly or indirectly (eg, if Y contains X, and Z contains Y, return
both Y and Z). In other words, find all the nodes that have X as a
sub-node.
The most promising lead I'd found was:
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
(which is why I'm cc'ing the MySQL list), but this only works with
trees, and I couldn't figure out how to modify it for lattices.
--
We're just a Bunch Of Regular Guys, a collective group that's trying
to understand and assimilate technology. We feel that resistance to
new ideas and technology is unwise and ultimately futile.
--
MySQL General Mailing List
For list archives: http://lists.mysql.com/mysql
To unsubscribe: http://lists.mysql.com/[EMAIL PROTECTED]
