Results 1 to 6 of 6
  1. #1
    Join Date
    Nov 2003
    Posts
    1

    Recursive relationships

    I'm an experienced ATL/COM developer, but I have no dB background. I'm playing around with a toy app using VB and MS Access in order to learn some of the concepts and procedures. I'd appreciate your opinions on a design problem. The simplified scenario is:

    1) I have two conceptual objects, a location and an asset.
    2) Locations can have subordinate locations, which themselve can have subordinate locations, etc. I do not wish to restrict the level of nesting.
    3) An asset is related to a location. I want the asset to be related to the any location (one with or without a subordinate location)
    4) The tree implied by item 2 does not have to be of uniform depth
    5) I want to be able to identify all the locations subordinate (at any depth) to a given location

    My initial design:

    Table Location:
    LocationID AutoNumber (primary key)
    Location Text
    ParentLocation Number (foreign key) <-- proper term?
    Points to LocationID

    Table Asset:
    AssetID AutoNumber (primary key)
    Asset Text
    LocationID Number

    Example location table: (note that it is intentionally filled out unevenly)
    USA (parent = NULL)
    Michigan (parent = USA)
    Macomb County (parent = Michigan)
    Washtenaw County (parent = Michigan)
    Ann Arbor (parent = Washtenaw County)
    4th district (parent = Ann Arbor )
    Ypsilanti (parent = Washtenaw County)
    Maryland (parent = USA)
    Virginia (parent = USA)
    Newport News (parent = Virginia)
    York County (parent = Virginia)
    Yorktown (parent = York County)
    Tabb (parent = York County)
    Grafton (parent = York County)
    Denmark (parent = NULL)
    Italy (parent = NULL)

    Example asset table: (note that not all assets related to leaf nodes)
    (sorry - no creative names here)
    asset1, location = Michigan
    asset2, location = Newport News
    asset3, location = York County
    asset4, location = 4th district
    asset5, location = Denmark

    Example of item 5)
    Given the ID for Michigan, I want to get
    Macomb County (parent = Michigan)
    Washtenaw County (parent = Michigan)
    Ann Arbor (parent = Washtenaw County)
    4th district (parent = Ann Arbor )
    Ypsilanti (parent = Washtenaw County)

    None of the several coworkers (with at least some dB experience) that I queried liked the recursive nature of the first table. Their objections, other than the possibility of a loop, were not clear to me. I believe one of them was that many locations would not have a parent, so some field entries are wasted. The alternative was to list relationships in a separate table. Is there a prefered method for this common parent/child relationship? Different options that are favored under certain conditions?

    The other problem is item 5. With my limited knowledge, I can only generate this list (from VB) using a separate query for each level of the "location" tree. Also, the list ends up in a VB Collection, not a single recordset. My coworkers said this was horrible, and that I should come up with a design that only requires one query (performance issue, perhaps considering distributed dBs?). One alternative I read online was to read in the whole table and do the recursion in VB code. Although my database will never be very large, I want to learn the concepts, and that doesn't seem to scale very well.

    Hope this isn't too much information!! Any advice?

    Thanks,

    Greg

  2. #2
    Join Date
    Sep 2003
    Location
    The extremely Royal borough of Kensington, London
    Posts
    778
    The decision to use the first relation (recursive) or a many to many comes down to your decision. Specifically which choice has a higher weighting, by choice I mean If more than 50% will have parents then use recursion, otherwise use many to many. Note. This will most likely not be 50 - 50 rather 60/70 etc.

    Your comment->
    "Their objections, other than the possibility of a loop, were not clear to me. I believe one of them was that many locations would not have a parent, so some field entries are wasted. The alternative was to list relationships in a separate table" Each entry is required to be recorded thus by using the recursive approach you will have a few nulls (see above note about weighting), whereas if you use a many to many not only will a table join be required but the candidate / primary key will need to be copied into the many - many table. So although data is not wasted it's to an extent duplicated.

    For example if 90%+ of records will have a parent then creating a many to many may not be appropiate as 90% of the primary keys will be duplicated into the many to many table. However if only say 10% or some other small number had parents then the many to many would be suitable.

    Regarding the query, it is the same as a parts database where a typical query would be list all parts and the total price needed to assemble this machine. Indeed this is recursive, the SQL "With" handles this problem I think.
    Last edited by r123456; 11-25-03 at 11:48.
    Bessie Braddock: Winston, you are drunk!
    Churchill: And Madam, you are ugly. And tomorrow, I'll be sober, and you will still be ugly.

  3. #3
    Join Date
    Oct 2003
    Posts
    87
    Had to make the assumption that you may have assets that aren't assigned, else asset is simply an attribute of location.

    create table location
    locationID autoNumber,
    location Text,
    primary key (location)

    create table locationAssociation
    ordinateLocationID autoNumber,
    subordinateLocationID autoNumber,
    primary key (ordinateLocationID, subordinateLocationID)
    foreign key (ordinateLocationID)
    references locationID
    on delete restrict

    create table asset
    assetID autoNumber,
    Asset text,
    primary key (assetID)

    create table locationAsset
    locationID autoNumber,
    assetID text,
    primary key (locationID, assetID)
    foreign key (locationID)
    references location
    on delete restrict,
    foreign key (assetID)
    references asset
    on delete restrict
    Oracle - DB2 - MS Access -

  4. #4
    Join Date
    Oct 2002
    Location
    Baghdad, Iraq
    Posts
    697

    Re: Recursive relationships

    Table Location:
    LocationID AutoNumber (primary key)
    Location Text
    ParentLocation Number (foreign key) <-- proper term?
    Points to LocationID
    Foreign key is correct, but it "refers" to LocationID, it doesn't point. A pointer is a physical construct and the relational model tries to separate logical and physical concerns.

    Their objections, other than the possibility of a loop, were not clear to me. I believe one of them was that many locations would not have a parent, so some field entries are wasted. The alternative was to list relationships in a separate table. Is there a prefered method for this common parent/child relationship? Different options that are favored under certain conditions?
    I've tried designing systems like this and the main problem is devising a reasonable system of constraints. In practice, most hierarchies don't need or want to be as freeform as you suggest. For example, consider this:

    Location
    LocationID (Primary key)
    Name

    Country
    LocationID refs Location
    Shortname

    State
    LocationID refs Location
    Country refs Country(LocationID)
    Abbreviation

    City
    LocationID refs Location
    State refs State(LocationID)

    ...

    Granted, here you have a profusion of tables, but the upside is that you're guaranteeing that a City lies within a State lies within a Country, you're preventing the possibility of loops, and it still allows an asset to be fixed to any scope of location. This also allows you to affix information to, say, cities but not countries or prevent assets from being associated with some levels. Note that there's a "Shortname" and "Abbreviation" associated with Country and State which wouldn't be appropriate for Cities.

    My coworkers said this was horrible, and that I should come up with a design that only requires one query (performance issue, perhaps considering distributed dBs?). One alternative I read online was to read in the whole table and do the recursion in VB code. Although my database will never be very large, I want to learn the concepts, and that doesn't seem to scale very well.
    You can really shoot yourself in the foot by worrying about scaling before you're sure your design is correct. The only way to be sure something scales is to test it so there's a limit to how much you should worry about that when designing.

    If you want to learn, I suggest you read Chris Date's Introduction to Database Systems. (It covers many quite advanced topics in spite of being an "introduction.") I've also heard Fabian Pascal's Practical Issues in Database Management is highly recommended, and it might be more applicable to the issues you're wrestling with.

  5. #5
    Join Date
    Oct 2003
    Posts
    706

    Re: Recursive relationships

    Originally posted by gkh01
    2) Locations can have subordinate locations, which themselve can have subordinate locations, etc. I do not wish to restrict the level of nesting.
    3) An asset is related to a location. I want the asset to be related to the any location (one with or without a subordinate location)
    4) The tree implied by item 2 does not have to be of uniform depth
    5) I want to be able to identify all the locations subordinate (at any depth) to a given location.

    In this scenario, the "thorny" problem is how to represent the relationship tree, and yet produce fast and efficient results when searching. You state the essential objective most succintly in your bullet-point #5.

    The best way to handle this, I believe, is to build one table which simply lists each of the "arcs" in your tree: Location*, Is_Related_To_Location*. ("*" = primary key.)

    Now you construct a second table which "explodes" that information into a list of all the locations to which a particular location is related: Location*, Is_Related_To_Location*, At_Depth_N.

    You algorithmically prepare this table from the first table, growing the tree outward with successive depths. This involves selecting the records having depth 'n' and finding the locations to which the related_to location is linked, then trying to insert those rows into the table with depth 'n+1.' Since the two location fields comprise the primary-key, any duplicates will "bounce off." Eventually all the dupes will bounce-off and there will be no new rows created at all with depth 'n+1' at which time the goal-state has been reached.

    This fairly-expensive process only need be performed once, and repeated only when the tree actually changes. Once this "exploded" table has been finished, the desired searches can be performed very quickly.
    ChimneySweep(R): fast, automatic
    table repair at a click of the
    mouse! http://www.sundialservices.com

  6. #6
    Join Date
    Oct 2003
    Posts
    87
    Check out the "connect by" clause of select. Chases a hierarchy for you.
    Oracle - DB2 - MS Access -

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •