[Techtalk] Efficiently modeling sets and subsets in lattice-like structure

[Kelly Jones]

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.