From: Robert Klemme <shortcutter@...>
Date: 2009-09-15T16:15:57+09:00
Subject: Re: Pre-allocate large amount of memory?

2009/9/15 Carsten Gehling <carsten@sarum.dk>:
> Robert Klemme wrote:
>
>> Is your structure strictly hierarchical (i.e. a tree) or do you need to
>> query part of a graph with cycles?  If it is strictly hierarchical there
>> is a solution that works for all RDBMS and in the latter case there are
>> solutions for some RDBMS.
>
> Unfortunately it is not strictly hierarchial. It is relations between
> companies-companies and companies-persons, that represents shareholders,
> parent-/subsidiary companies, etc.

So you do actually allow for loops, i.e. company A owns 10% of company
B which owns 10% of company A.

> My job is to - given a certain company X - to extract all its owners
> and, recursively, their owners, etc. until I reach the "top". Likewise
> the other way to extract all companies owned by company X and,
> recursively, all companies owned by them, etc.
>
> Conceptually, the table (actually a view) I am querying holds the data:
>
> CompanyA,  Direction, CompanyB,  Share
> "FooCorp", "owns",    "BarCorp", "10%"
> "BarCorp", "ownedby", "FooCorp", "10%"
> "BarCorp", "owns",    "BazCorp", "45%"
> "BasCorp", "ownedby", "BarCorp", "45%"
> "QweCorp", "owns",    "RteCorp", "20%"
> "RteCorp", "ownedby", "QweCorp", "20%"
> etc.
>
> The table is not of my doing. It is very difficult (at least for me) to
> devise a way to only query the nessecery rows in the table, without
> sorting to recursive calls.

If I understand that table design properly it is awful because
semantics of columns one, three and four change based on content of
column two.  The usual way would be to model this with fixed
semantics, i.e. only have one direction of ownership relation in the
table.  In your case you will probably have to do a normalization step
by defining a view on this table with a UNION ALL or use a WITH clause
in the query to ensure the query can be built in a reasonable way.

> In the example above: If given "FooCorp", all but the last two rows
> should be extracted and used in the result. How would you go about doing
> that?

There are features in modern RDBMS which allow for recursive querying.
 In PostgreSQL and Microsoft SQL Server you can use WITH expression:
http://www.postgresql.org/docs/8.4/static/queries-with.html
http://msdn.microsoft.com/en-us/library/ms175972%28SQL.90%29.aspx

In Oracle there is CONNECT BY
http://download.oracle.com/docs/cd/B19306_01/server.102/b14200/statements_10002.htm#i2066102

The downside is that recursive queries tend to have a performance hit
as the DB engine cannot fetch everything via a single index and needs
to look at results so far to know what other records it has to
retrieve.

The nested set model (Josh mentioned it as well) might help although I
haven't thought through all implications in your case:

http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
http://www.codeproject.com/KB/database/nestedsets.aspx

> I haven't found a solution yet. This is why I've gone and made a
> service, that holds all these data in memory (in a hash), to speed up on
> things.

You still have the issue that you maintain redundant data and must
find a way to invalidate your cache when the base data changes.  Since
a complete reload of the cache is expensive (as you have experienced)
this will get complicated soon because in order to find the data that
must be refreshed you need similar queries like those to find answers
to the questions you placed above.

> BTW: Thanks for all your great suggestions so far. :-)

You're welcome!

Kind regards

robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/