none
HELP, HELP!!! CONVERT A DATA STRUCTURE IN C# TO A ACCESS DATABASE RRS feed

  • Question

  • Hello:

     

    Recently I’m migrating from data structures to databases. I’ve converted a Customers, Products and PendingOrders collections into a Microsoft Access 2003 data base. But I must convert many other data structures.

    Now, the problem is a graph. In this project, there are cities and transportation means. Traveling to one city to another we must use a car, a bus, a train, an airplane, or a boat  but we can’t  travel between two if the transportation mean is not available, this is there are cities unreachable using a car (like cities located in islands) , a airplane (the destination city does not have airplane) and so on.

    I’ve used the graph data structure as solution. The nodes are the cities and the arcs are a relation between the city and the transportation mean. In math, this is

    Destination (city, transportation mean) = {city1, city2}

    I’ve implemented this relation between two sets.

    C: the set of cities

    T: the set of transportation means

    D: the set of destination cities given a city and transportation mean. It is a subset of C.

    For this purpose, the arc, called destination, is of the form

    (startCity,  transportationMean,  destinationCities)

    For implementation I’ve used list structures:

    City1-------|---------àMean1---------------- à{city1, city2}

                        |-------àMean2---------------- à{city1, city3, city5}

                        .

                        .

                        .

    City2-------|---------àMean1---------------- à{city3, city4}

                        |-------àMean3---------------- à{city1, city4, city7}

                        .

                        .

                        .

    Where, basically, there is a list of cities, each city points to its proper list of transportation means, and transportation mean point to its proper list of destination cities.

    |  |--------->| |-------->| | | | |

            |----->| |-------->| | | | |

            |----->| |-------->| | | | |

            |----->| |-------->| | | | |

     

    |  |--------->| |-------->| | | | |

            |----->| |-------->| | | | |

            |----->| |-------->| | | | |

            |----->| |-------->| | | | |

            |----->| |-------->| | | | |

    I’ve red databases examples, but I don’t found a similar model and I don’t know how to design this recursive relation in Microsoft Access.

    Help for this problem!

    e-mail me: monin712@hotmail.com

     

    Saturday, June 16, 2007 3:59 PM

All replies

  • The typical way to represent a graph in a database is with two tables, Node and Edge.  Each Node row has an ID; each Edge row has an ID and the IDs of the two nodes the edge connects.

    Thus, all of the edges which connect to a node:

       SELECT EdgeID FROM Edge WHERE NodeID1 = @NodeID OR NodeID2 = @NodeID

    If you want to find all of the nodes connected to edges which share a common characteristic (e.g. transportation means):

       SELECT NodeID FROM (
          SELECT NodeID1 AS NodeID FROM Edge WHERE Means = @Means
          UNION
          SELECT NodeID2 AS NodeID FROM Edge WHERE Means = @Means
       ) GROUP BY NodeID

    If you want to find all nodes that are exactly one edge away from a single node:

       SELECT DestinationNodeID FROM (
          SELECT NodeID2 AS DestinationNodeID FROM Edge WHERE NodeID1 = @OriginNodeID
          UNION
          SELECT NodeID1 AS DestinationNodeID FROM Edge WHERE NodeID2 = @OriginNodeID
       ) GROUP BY DestinationNodeID

    There aren't a lot of nontrivial graph problems that SQL is the right solution for.  For instance, all of the two-edge paths are found by this query:

       SELECT e1.EdgeID AS EdgeID1, e2.EdgeID AS EdgeID2
       FROM Edge e1
       JOIN Edge e2 ON e1.NodeID1 <> e2.NodeID1 AND e1.NodeID1 <> e2.NodeID2 AND (e1.NodeID2 = e2.NodeID1 OR e1.NodeID2 = e2.NodeID2)

    but if you want to find the endpoints of those paths, the query gets crazy:

       SELECT
          CASE WHEN e1.NodeID1 <> e2.NodeID1 AND e1.NodeID1 <> e2.NodeID2 THEN e1.NodeID1 ELSE e1.NodeID2 END AS NodeID1,
          CASE WHEN e2.NodeID1 <> e1.NodeID1 AND e2.NodeID1 <> e1.NodeID2 THEN e2.NodeID1 ELSE e2.NodeID2 END AS NodeID2
       FROM Edge e1
       JOIN Edge e2 ON e1.NodeID1 <> e2.NodeID1 AND e1.NodeID1 <> e2.NodeID2 AND (e1.NodeID2 = e2.NodeID1 OR e1.NodeID2 = e2.NodeID2)

    which is why most of the time if you're doing anything with a graph, you only use the database to store the data.
    Saturday, June 16, 2007 8:21 PM
  • Hello:

     

    Well, this is an interesting solution but I first try using Access rather than SQL. I need much more knowledge about SQL, I’m looking for a Microsoft Access solution, but I think that in little time remoting access will be required but not now. I’ll try to implement your solution in Access. Write me additional comments.

    Saturday, June 16, 2007 10:40 PM
  • I don't think I used any SQL features that Access doesn't support.
    Sunday, June 17, 2007 10:05 AM