Determine inductively defined data in MsAccess/SQL Server

Question

I need to retrieve data from MsAccess/SQL Server (two separate projects in which I face similar problem) using c#.net (3.5), preferably fast and with code that is understandable/maintainable/simple.

I have the following tables with columns. For each, the columns in bold are the key (indexed as well).

• SKU info (~1000 000 records) : PNO, description,leadtime, price, etcetera
• Usage information (~200 000 records) : OrderNO, PNO, description,date, quantity, unit of measure, etcetera
• InterchangeAbility (~100 000 records) : PNO,description (PNO1, description1, etcetera)

The last table indicates that (PNO1, description1) is the successor SKU of (PNO,description). Note that (PNO1, description1) may in turn have a successor as well.

I need to retrieve and store in memory:

1. All usage
2. SKU information for any part with for which there is usage (about 20000 parts)
3. All relevant interchangeability records, which say something about parts for which there was usage or parts that are the successor variants of parts for which there was usage etcetera.
4. SKU information for any relevant preferred parts (about 2000 parts)

Does anybody have a good maintainable solution for this problem?

The most promising approach seems to be to determine on the database side with SKUs are relevant. Problem is, that relevancy is inductively defined. How to do this?

Answer 1

Willem, it sounds like what you have is an ancestry tree.

Take an example where you have part A that was succeeded by part B, and part B was succeeded by parts C or D. Then say, D was succeeded with part E. This gives you:

Part  | All Successors                   A
----------------------                  / 
A     | B, C, D, E                     B
B     | C, D, E                       / \
C     | -                            C   D
D     | E                                 \
E     | -                                  E

So, perhaps what you need to keep track of in your database is the root part that another part succeeds, and not just its immediate ancestor.

If you are able to change the schema, I would add another two fields to your InterchangeAbility table, that track the RootPNO, RootDescription (indexed together). Each time a part succeeds another, you need to record that succession for all ancestors as well.

Then you could join from your usage table directly to the Root fields in InterchangeAbility to get all possible sucessors for a part.

Answer 2

You could look at caching the data.

For example, memcached (http://sourceforge.net/projects/memcacheddotnet/).

Basically syncs with your underlying data using standing queries, and then that data is always available to you in memory.

Answer 3

Attempted to figure out how the problem of finding relevant interchangeability might be solved using a CTE. Quickly got out of hand. You might be able to get something from it still. It shouldn't be too inefficient, despite it's size, assuming my thinking isn't completely wrong.

Each of the queries inside the CTE is basically a temporary view you can access from the CTE. The Preferred, Roots and HasUsage bits don't depend on any of the other CTE tables, so they could actually even be views if you needed.

;WITH Preferred AS (
   -- Find leaves (Any PNO which replaces a PNO but is never replaced.)
  SELECT PNO1 FROM InterchangeAbility l 
  LEFT JOIN InterchangeAbility r ON l.PNO1 = r.PNO
  WHERE r.PNO IS NULL  
)
, Roots AS (
  -- Find roots (Any PNO which gets replaced, but never replaces anything.)
  SELECT PNO FROM InterchangeAbility l
  LEFT JOIN InterchangeAbility R ON l.PNO = r.PNO1
  WHERE r.PNO1 IS NULL
)
, HasUsage AS (
   -- Count number of records in usage for each PNO in usage (including 0)
   -- Ideally this step wouldn't be necessary, but a LEFT JOIN isn't allowed in 
   -- The recursive part of a CTE.  There may be a more efficient way around this step.
  SELECT SkuInfo.PNO, COUNT(Usage.PNO) AS num_records
  FROM SkuInfo
  LEFT JOIN Usage ON SkuInfo.PNO = SkuInfo.Usage
  GROUP BY SkuInfo.PNO
)
, TreeHasUsage AS (
  -- Traverse from root to leaf, used leaves will have nonzero usage
  -- This is a recursive query, The usage of each root will be the base case.
  SELECT p.PNO AS root, p.PNO AS curr, hu.num_records 
  FROM Roots p
  INNER JOIN HasUsage hu ON p.PNO = hu.PNO 
  UNION ALL
  -- This is the recursive part of the query, it finds the PNO which replaces
  -- the root element (and so on) and does a running total of the usage associated
  -- with this tree branch.  By the time we get to a leaf any relevant preferred PNOs
  -- will have a nonzero num_records.
  SELECT tu.root, hu.PNO, tu.num_records + hu.num_records 
  FROM TreeHasUsage tu 
  INNER JOIN InterchangeAbility i ON tu.curr = i.PNO1 
  INNER JOIN HasUsage hu ON i.PNO = hu.PNO  
)
, RelevantRoots AS (
  -- Important tree nodes are the ones which have a non zero 
  -- num_records on one or more leaves. Select the roots of those trees.
  SELECT DISTINCT hu.root FROM Preferred p 
  INNER JOIN TreeHasUsage hu WHERE p.PNO1 = hu.curr
  WHERE hu.num_records > 0 
)
-- Select every record in InterchangeAbility which belongs to one of the 
-- just determined relevant roots.
SELECT * FROM InterchangeAbility i 
INNER JOIN RelevantRoots rr ON i.PNO = rr.root