Help about graphs and how to query them.

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

From: Star (----)
Date: 03/01/04 

Date: Mon, 1 Mar 2004 17:22:08 -0500

Hi,

I'm sorry if this it not the right newsgroup. My question is related with
databases, however the way I'm going to handle
everything could not be related with that (I use algorithms about reading
graphs), and maybe you guys come have a good idea.

Ok, let's see if I can explain the problem.

I have about a SQL database with 15 tables. Each table has several fields,
however each table
has a common field called 'Code'

ex.

Table Vehicles
--------------
Code
Make
Color

Table People
-------------
Code
Name
Age

Table Addresses
-----------------
Code
City
ZIP
...

Now we want to relate records from one table to another. For example, we
want to say 'John has two cars'
In order to do that, I have an external table called Links with source an
destination fields. For the example we would have

Source Dest
----------------
P132 V100
P132 V242

(P132 is a record from the People table with code 132, V100 a vehicle from
the Vehicle table with code 100, and V242 a vehicle
with code 242)

So, with all that, we know that John (P132) is related with two vehicles. If
I want to run the query 'People associated with vehicles'
it would be easy to query that table and get that information.

Now, let's suppose we have this situation:

Source Dest
----------------
P132 V100
P132 V242
P140 V500
P132 P140

In this example, John is related with Michael (P140) and Michael is related
with a vehicle (V500).
If I want to run the same query than before 'People associated with
vehicles', because of P132 is related with P140 and P140 is related with
a V500 this implies that P132 is related with V500.

Now, the query is not so simple, because it's like a graph and I need to
make a Depth First Search to get what I want. Doing that, I will get that
P132 is
related with V500 because there is a 'path' to get there.

I have done all this and it works fine. The problem that I have is that I
need to make that Depth First Search for each people that I have in the
database
in order to see if I have vehicles associated with it. If I don't have many
records it's ok, but If I have 100,000 people on the database I would have
to
make that search 100,000 times just to see if there is a path between them,
I mean, if there is a way to get from a person to a vehicle.
In this case... this solution doesn't work, because it takes forever...

What do you guys suggest I can try? I though that one solution would be to
have a process running on the server that maintains a table with ALL the
links that we have in the database and the depth of the link. So, in our
example we'd have a entry "P132 V500 with depth 2"
Having that table it would be easy to query. Inconvenience: the table is
going to be HUGE, and also the process has to be smart enough to keep track
of deleted links, new links...

I'd appreciate if you guys have any idea or suggestions about this and how I
can get a better perfomance.

Thanks a lot for reading this whole message!!

Relevant Pages

  • Re: Should I use LISP for this?
    ... > The query optimizer will look at your query and determine the best way to ... > Now, using Lisp as a front-end to your database, that's a good idea... ... >> Table Vehicles ...
    (comp.lang.lisp)
  • Re: Should I use LISP for this?
    ... Seems more like a database problem. ... The query optimizer will look at your query and determine the best way to ... If you really insit on building in-memory structures, Lisp is a good choice. ... > Table Vehicles ...
    (comp.lang.lisp)
  • Re: Help with recursive queries... BIG problem.
    ... INSERT INTO ASSOC2 ... > So, with all that, we know that John is related with two vehicles. ... > it would be easy to query that table and get that information. ... > records it's ok, but If I have 100,000 people on the database I would have ...
    (microsoft.public.sqlserver.programming)
  • Re: Mail Merge with DB to create a table of related records
    ... Now that it is hooked up to each data source is it possible to set something ... "Peter Jamieson" wrote: ... the source for the DATABASE field. ... use that to insert the databse of vehicles /as a field/ you then have ...
    (microsoft.public.word.mailmerge.fields)
  • Help with recursive queries... BIG problem.
    ... So, with all that, we know that John is related with two vehicles. ... it would be easy to query that table and get that information. ... make a Depth First Search to get what I want. ... records it's ok, but If I have 100,000 people on the database I would have ...
    (microsoft.public.sqlserver.programming)