Results 1 to 5 of 5
  1. #1
    Join Date
    Jun 2007
    Posts
    1

    Tree-like "Nesting" DB Questions

    I wish I knew what to call my little dilemma so I could search for help/examples on how to make this work. That title is just too unclear... in any case, I've been illustrating my problem with a Star Wars example in a few other forums looking for help, and this place seems pretty lively, so I'll give it another shot.

    Suppose I'm managing ship positions for the Empire. I don't need to know exact coordinates, just what objects are located inside others. Four things that need modeling: Star Systems, Death Stars, Star Destroyers, and TIE Fighters. Star Systems would have NULL in their location field. Death Stars must be located inside Star Systems. Destroyers can be located free in Star Systems or docked in a Death Star, and Fighters can be inside any of the other three objects. In addition, each of these objects has unique properties, so I'll need table for each. Four tables, coming up, and the oddly numbered IDs will make sense in a minute.

    Code:
    STARSYSTEM
    ID - Location - Name - Star Class
    0 - NULL - Aldebaran - White Dwarf
    1 - NULL - Tatooine - Red Giant
    
    DEATHSTAR
    ID - Location - Emperor On Board - Fully Operational - Planetary Shield
    2 - 0 - N - Y - N
    
    DESTROYER
    ID - Location - Bridge Decor - Hemi - Commander
    3 - 1 - Hessian - N - Tarkin
    4 - 2 - Black&Chrome - Y - Vader
    
    TIEFIGHTER
    ID - Location - SeatType
    5 - 4 - Bucket
    --- yadda yadda yadda, you get the point, only three tables are really needed to demonstrate my point.
    This isn't acceptable because the primary keys (ID) have to all be different to be able to distinguish where a thing is... So, I set up a LOCATION table that the primary keys for all the objects are pulled from, and move the common Location field to this table.

    LOCATION
    ID - Location
    0 - NULL
    1 - NULL
    2 - 1
    3 - 1
    4 - 2
    5 - 4

    This <i>works,</i> but I'm still not happy about it. I can find the ID of an objects parent, but I don't know how to tell what table that parent object is in. Even if I did something like this...

    LOCATION
    ID - Location - ParentTable
    0 - NULL - NULL
    1 - NULL - NULL
    2 - 1 - STARSYSTEM
    3 - 1 - STARSYSTEM
    4 - 2 - DEATHSTAR
    5 - 4 - DESTROYER

    I'm pretty sure that this is a long way from being valid SQL...

    SELECT * FROM (SELECT ParentTable FROM Location WHERE yadda yadda yadaa)

    So, I'm asking: Is there some kind of conditional thing I can use here to decide what table to query in regards to parent objects, or am I stuck querying all tables looking for one record?

    And if this gets answered, I've got a question or two on how to insert to Location and another table... atomicly, I believe, is the word. I can see potential... problems if it's not done in one swoop for each insert.

  2. #2
    Join Date
    Apr 2002
    Location
    Toronto, Canada
    Posts
    20,002
    Quote Originally Posted by S_Gray
    I'm pretty sure that this is a long way from being valid SQL...

    SELECT * FROM (SELECT ParentTable FROM Location WHERE yadda yadda yadaa)
    a long way, only if you're measuring distance in angstroms

    if you want a theoretical solution, redesign your database so that it cannot possibly contain a NULL in any column, anywhere (except i cannot give you any help with this—it would just take too long and you'd end up with twenty-three tables—although i do know someone who can)

    for a practical solution...

    - remove LOCATION from STARSYSTEM
    - replace LOCATION in DEATHSTAR with foreign key STARSYSTEM_ID
    - replace LOCATION in DESTROYER with two foreign keys, STARSYSTEM_ID and DEATHSTAR_ID, both NULLable, but only one of which will be NULL in any given destroyer row
    - replace LOCATION in TIEFIGHTER with three foreign keys... as you phrased it, "yadda yadda yadda, you get the point"

    let me know if this structure doesn't make sense to you

    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL

  3. #3
    Join Date
    Apr 2004
    Location
    Toronto, Canada
    Posts
    249

    Another way to solve this problem

    There is another way to solve this problem that will result in a more flexible data model and, hopefully, less code. It will be easier to add more types of things.

    I think the solution suggested earlier does not meet all the requirments of the problem.

    I'm assuming that we can call all these things objects, and that you are only storing the current location of all objects relative to other objects. Retain the current tables that you described earlier: StarSystem, DeathStar, Destroyer and TieFighter.

    Code:
     StarSystem(ID, Name, ...) [Drop the location column since it will always be null.]
    DeathStar (ID, Name, Location, ...)
    Destroyer (Id, name, location, ...)
    TieFighter (Id, name, location, ...)
    One way to ensure that the Ids are unique across all four tables is to use the same sequence generator for all four tables. (Other solutions are possible for this problem.)

    Have a table called, say, object_type, that defines these object_types.

    Code:
     object_type( type_code, name)
    This could have sample data such as:

    Row 1: 'SS', 'StarSystem'
    Row 2: 'DS', 'DeathStar'
    Row 3: 'D', 'Destroyer'
    Row 4: 'TIE', 'TIEFighter')

    The point of this is to help enforce the location rules outlined in your problem statement.

    Define another table called location_rule (say) for this purpose.

    Code:
     location_rule (parent_object_type, child_object_type)
    This table will be used to enforce the location containment rules.
    Sample data:

    Row 1: 'SS', 'DS' (says that a StarSystem can contain a DeathStar
    (or, equivalently, that a DeathStar can be located in a StarSystem.)

    Row 2: 'SS', 'D'
    Row 3: 'SS', 'TIE'
    Row 4: 'DS', 'D' (a Destroyer can be located inside a DeathStar)
    etc.


    How do you guarantee that a user/developer does not define a DeathStar to be located in a TIEFighter?

    Write a small procedure/function to determine whether a given object_type can be located within another object_type. For example, you could write a small function called is_valid_location (child_object_type, parent_object_type) that returns a boolean value (true or false)

    The call to is_valid_location('DS', 'SS') asks if a 'DeathStar' can be located in a 'StarSystem'. This should return true. While calls such as is_valid_location ('SS', 'DS') or is_valid_location('DS', 'TIE') should return false.

    This can be done most simply by querying the location_rule table with the values passed in as parameters of the funciton.

    Hope that clears up the need for the location_rule table and the object_type table.

    For each of the tables 'DeathStar', 'Destroyer' and 'TieFighter' enforce this rule before updating or inserting each row of data.


    That leaves us with the problem of determining the object_type corresponding to an ID. Create a view, say, v_object_id_type, that queries the four tables to get the types.

    Code:
    Pseudo_Code: 
        select 'SS' as object_type, id from starSystem 
        Union
        select 'DS', id from DeathStar
                        ...
    that gets information from the required tables.

    (Alternatively, you can create a table with this structure and ensure that a row of data is added or removed to this table whenever a new row of data is added or removed from any of the four tables. I prefer the view unless you plan to have millions of objects.)

    Hope that was not too long or confusing.

    One of the benefits of this design is that when a new type of object is added, it is relatively easy to make the changes. The changes will be limited only to those things that actually changed, nothing else. For example, data will need to be added to the object_type table (a new object_type is being defined), the location_rule table (what objects can this new type contain, and where can ths new object be located?); a new table for the new type of object that was created, and data for that table; and the view should be modified with the new Union for the new table.

    The function that validates the location will not need to be changed, neither will the triggers on any old tables.

    Change is limited to only those things that actually change!

    Ravi

  4. #4
    Join Date
    Apr 2002
    Location
    Toronto, Canada
    Posts
    20,002
    Quote Originally Posted by rajiravi
    I think the solution suggested earlier does not meet all the requirments of the problem.
    i think the solution offered in post #3 in untenably complex and solves requirements which were not part of the stated problem
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL

  5. #5
    Join Date
    Apr 2004
    Location
    Toronto, Canada
    Posts
    249
    Quote Originally Posted by r937
    i think the solution offered in post #3 in untenably complex and solves requirements which were not part of the stated problem
    The use of the location rule_table enforces the stated requirement about the objects location being limited to certain types, can be easily enforced and enhanced, does not contain unnecessary nulls, and simply works.

    Many of the things stated in the solution have to be done in any case, they just weren't stated earlier.

    In the first solution suggested, for example for the TieFighter table with the following foreign keys (starSystem_id, deathstar_id, destroyer_id), is it not possible to create incorrect data by putting in the following three values for the keys (0, 2, 3) that conflicts with the other data provided? Could you please show the code that would be required to ensure correctness with other data? Now, which solution has more lines of code?

    Can such incorrect data be put into the solution I had suggested? No, of course not!

    My solution is long on the description and rationale for the design, not on the code itself. Write it out, and the brevity and simplicity will become obvious.

    If the correctness of the data is not important enough, then one can use the solution suggested in message #2.

    What about the alternatives for getting the matching types from the ids? Was such an idea proposed in #2 or simply left unmentioned? In #2, was there any example given of how to accomodate a new type? Or a change in the rules for the location?

    Ravi
    Last edited by rajiravi; 06-06-07 at 17:05.

Posting Permissions

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