BusinessRules to deal with circular references

ajj3085 posted on Thursday, November 20, 2008

Hi,

I'm building an inventory application.  Each inventory part (Part) has a part number and some other properties.  Nothing fancy.  Each part may also have a BOM.  The BOM is just a list of other parts which make up the parent part.  So a BOM for a computer would include RAM, HDs, MBs, etc.  RAM could have it's own BOM as well; circuits, chips, etc.

So.. here's my problem.  I'm trying to code business rules to detect and prevent circular references.  For example, you shouldn't be able to add the system RAM as a component to an HD (which may have memory... just not the kind that fits on the MB). 

My tables look like this:
BOM( BOMId, PartId, Notes )
Part( PartId, other values )
BOMPart( BOMId, PartId )

Any ideas?  For some reason I figured this out when I let product bundles contain other bundles... but something here is throwing me off (I only had two tables to worry about for that.. Product and ProductBundleItem).

Ideas?

rsbaker0 replied on Thursday, November 20, 2008

I'm not sure exactly how/when you would incorporate this into a business rule, but you could, in theory, just walk up your parent chain recursively to be sure there isn't an object of the same type in your "ancestry", so to speak.

Jack replied on Friday, November 21, 2008

I'm not sure you could use a business rule as you have a lot of recursion to deal with.  You basically need to write a recursive function to loop through all your related collection lists and those of each parent.  I find this sort of thing is best done in the database as otherwise you have to load all the data for each part and their BOM.  You could lazyload each part's BOMList but maybe you already have the hierarchy in memory for other reasons

isPartInBomTree(BOMListBO, PartBO)
{
    foreach (partBO p in BOMListBO.PartListBO)
        if (p.PartId = PartID) return true
     if (p.BOMList != null) return isPartInBomTree(p.BOMList, PartBO)
 return false;
}

Othewise you can use the database to validate the hierarchial tree on an insert to the BOM.

You probably have a few choices - pass the set of partID/BOMs to a stored proc in bulk and then loop through an exists type function for each part that does a scan to see if the part exists in the BOM/part tree.  If it fails cancel the transaction, if not keep looping.

You could also simulate this in your application one part at a time

You other choice if it fits into the paradigm would be to write a datbase function that looks for circular references and flag them.  If you are allowed to put the circular reference into the database then you can do a single query to get the parts.  You could build in a no more part/BOM edits until that is fixed sort of thing.  That sounds lousy though as I finish typing it up.

It's early in the morning so the code maybe a bit wonky but that should be the idea.

jack

ajj3085 replied on Friday, November 21, 2008

Well what I did with bundles was to call a UDF on the database which did the recrusion for me via a CTE.

The algorithm you're describing sounds like the one I did for product bundles... but for some reason I'm convincing myself that in this case it won't work.  The part I'm hung up on is if the BOM which has the parts being checked is new; my thinking is the check will miss because nothing's in the database yet.

Consider this:  Part A has a BOM, and is made up of parts B, C & D.
I try to create a BOM for part C, which would include A.  If A is added to C's list first, the check will succeed... actually it shouldn't... if I fully expands A's BOM, I should be able to check if C is part of that list.. and fail.  Ok, so it is like the bundles... I just needed to reverse my thinking.

Thanks!
Andy

rsbaker0 replied on Friday, November 21, 2008

Ah, you're talking about a circular reference for a specific part number in an hierarchical assemblage of some form. (e.g. the rule is something like "a part cannot contain itself")

We have that exact problem in our legacy application also and just band-aided it at the time versus implementing a good solution. (We just chopped off the BOM "explosion" at a certain depth to avoid runaway recursion)

I'll be interested in your solution, since I'd prefer something better. We have a "BOM" table that essentially is a set of ordered pairs of the "parent" part number and list of "child" part numbers, so I'd think it's a pretty common problem with this type of representation.

ajj3085 replied on Monday, November 24, 2008

Here's my solution.  I have a UDF in Sql Server (this solution needs 2005, but you should be able to use cursors to accomplish the same thing in earlier versions).

Basically, as each part is added to the BOM, we ask if the BOM being modified appears anywhere in the expanded BOM hierarchy of the part being added.  For example, Part A is made up of Parts B, C & D.  Part C is in turn made up of part K & L.  When editing the BOM for C, we should check to make sure that C isn't part of A's BOM anywhere in the hierarchy.  In my example using the UDF below, we'll pass the part id of C (which is the BOM we want to add A to) as the first parameter, and the part id of A as the second (the part which is to be added to C's BOM).  If the UDF returns 1, that means that C is already included somewhere on A's BOM, which means we'd create a circular reference if we allowed it.  If it's 0, everything will be fine. 

Like the products and bundles code, I execute this check on BomItem's DataPortal_Create (so we'll to hit the DB) and also while I'm doing the save for the root BOM object.

HTH someone else.
Andy

Here's the UDF I use:

ALTER FUNCTION [dbo].[IsPartInBom] (
    @PartId int, -- This is the part we are looking at
    @PartIdBom int -- This is the part who's BOM we must check
)
RETURNS bit
AS
BEGIN

    DECLARE @Result bit
    DECLARE @Count int;

    WITH ExpandedBom(
        PartId,
        BomId
    ) AS
    (
        SELECT    bpart.PartId, NULL
        FROM    BillOfMaterials bom
            INNER JOIN BillOfMaterialsPart bpart ON bom.BillOfMaterialsId = bpart.BillOfMaterialsId
        WHERE    bom.PartId = @PartIdBom

        UNION ALL

        SELECT    bpart.PartId, bpart.BillOfMaterialsId
        FROM    BillOfMaterials bom
            INNER JOIN ExpandedBom eb ON eb.PartId = bom.PartId
            INNER JOIN BillOfMaterialsPart bpart ON bom.BillOfMaterialsId = bpart.BillOfMaterialsId
    )

    SELECT    @Count = COUNT( * )
    FROM    ExpandedBom
    WHERE    PartId = @PartId

    IF @Count = 0 BEGIN
        SET @Result = 0
    END ELSE BEGIN
        SET @Result = 1
    END

    RETURN @Result

END

rsbaker0 replied on Monday, November 24, 2008

Thanks!  That gives me some good ideas.

I can't use this exact code because I have to worry about Oracle, Access, and SQL 2000, but we implemented some cross-platform views that compute the BOM to a fixed depth (basically by chaining 1 level views to each other) and I think I can use this to what you are doing.

ajj3085 replied on Tuesday, November 25, 2008

The idea should work for you though.  This just "flattens" the BOM hierarchy recursively.  You should be able to do something similar with temp tables and cursors though and it sounds like you might already be doing so.

stefan replied on Wednesday, November 26, 2008

Hi Andy,

I have an alternative way of verifying if a BomPart is valid for a given part.
In addition to your sp, I test for valid parameters (e.g. PartId == PartIdBom, >0 )
I use standard SQL so it is somehow universal:

CREATE FUNCTION IsValidBOMPart
(
    @PartId int, -- This is the part we are looking at
    @PartIdBom int --This is the part who''s BOM we must check
)
RETURNS bit
AS
BEGIN
    DECLARE @Result bit
    DECLARE @Count int;

    -- no self-reference
    IF @PartId=@PartIdBom OR @PartId<1 OR @PartIdBom<1 BEGIN

        SET @Result=0

    END ELSE BEGIN

        -- collect all Part_IDs that are not allowed inside the BOM that is examined
        WITH IllegalParts(
            PartId
        ) AS
        (
            -- all parts containing @PartIdBom INCLUDING @PartIdBom itself
            SELECT @PartIdBom
            UNION
            SELECT tblBOM.intPart_IDBOM
            FROM tblBOMPart
                INNER JOIN tblBOM ON tblBOMPart.intBOM_IDBOMPart = tblBOM.intBOM_ID
            WHERE    
                (tblBOMPart.intPart_IDBOMPart = @PartIdBom)
            UNION
            -- all parts containing @PartId INCLUDING @PartId itself
            SELECT @PartId
            UNION
            SELECT tblBOM.intPart_IDBOM
            FROM tblBOMPart
                INNER JOIN tblBOM ON tblBOMPart.intBOM_IDBOMPart = tblBOM.intBOM_ID
            WHERE    
                (tblBOMPart.intPart_IDBOMPart = @PartId)
        )

        -- now check if there are any invalid part_IDs...
        SELECT @Count = COUNT(*)
        FROM IllegalParts ip
            INNER JOIN (SELECT tblBOMPart.intPart_IDBOMPart AddedPartId
                        FROM tblBOM
                            INNER JOIN tblBOMPart ON tblBOM.intBOM_ID = tblBOMPart.intBOM_IDBOMPart
                        WHERE    
                            (tblBOM.intPart_IDBOM = @PartIdBom)
            ) bom2Check ON ip.PartId = bom2Check.AddedPartId
       
        IF @Count = 0 BEGIN
            SET @Result = 1
        END ELSE BEGIN
            SET @Result = 0
        END

    END

    RETURN @Result

END


Stefan

ajj3085 replied on Friday, November 21, 2008

Well, in the product bundle use case, I checked the rule when creating a new ProductBundleItem, and also when ProductBundleItems saved themselves.