CODEWITHSUNDEEP
sqldatabase-designrelational-database
Gareth Davidson
Gareth Davidson

Reputation: 4917

Find all sets which are a subset of a superset in SQL

I'm pondering the design of an application where the main feature revolves around the ability to find the set of all sets which are subsets of a given set.

For example, given the input set A={1,2,3...50} and the set of sets B={ B1={3,5,9,12}, B2={1,6,100,123,45} ... B500={8,67,450} }, return all Bs which are a subset of A.

I guess it's similar to a search engine, except that I don't really have the luxury of set A being small and the Bs being large; in my case Bs are usually smaller than A.

I found a similar question here, but was wondering if there was anything more efficient / standard.

Upvotes: 4

Views: 2866

Answers (1)

PerformanceDBA
PerformanceDBA

Reputation: 33728

Harper's answer is correct and elegant. Certainly the "standard" among experienced SQL coders. The requirement is of course the db must be normalised: Parent is not duplicated; Parent::Child has two relations; there are two unique indices (ParentKey, ChildKey) and (ChildKey, ParentKey) in the Child table, "otherwise all bets are off". It is not possible to get better performance than that (assuming the server is configured properly for the hardware, etc). The next step is 6NF, which does provide a significant increase in performance, but you do not need to go there unless you have to. If your Bs are smaller than your As, it will be very fast.

The alternative is to use subqueries. Depending on your Db vendor, subqueries (particularly if your Bs are smaller than your As) can be faster. Eg. Sybase handles subqueries far better than MS.

Upvotes: 3

Related Questions