4

I need to have a database that starts with a table called "User" that needs to self reference itself and will have a very deep graph of related objects. It will need to be like the left side of the image below (disregard the right side).

enter image description here

I will also need to traverse through this graph both up and downwards in order to calculate percentages, totals, etc. In other words I'll need to travese the entire graph in some cases.

Is this possible and/or how is it done? Can traversing be done right in the LINQ statement? Examples?

EDIT: I'm basically trying to create a network marketing scenario and need to calculate each persons earnings.

Examples:

  1. To be able to calulate the total sales for each user under a specific user (so each user would have some sort of revenue coming in).
  2. Calculate the commission at a certain level of the tree (e.g. if the top person had 3 people below them each selling a product for $1 and the commission was 50% then there would be $1.50.)
  3. If I queried the image above (on the left) for "B" I should get "B,H,I,J,N,O"

Hopefully that helps :S

svick
  • 236,525
  • 50
  • 385
  • 514
Ryan
  • 4,354
  • 2
  • 42
  • 78

2 Answers2

3

You can't traverse the whole tree using just LINQ in a way that would translate to single SQL query (or a constant count of them). You can do it either with one query for each level or with one query, that is limited to a specific count of levels (but such a query would get really big with many levels).

In T-SQL (I assume you're using MS SQL Server), you can do this using recursive common table expressions. It should be possible to put that into a stored procedure that you can use from LINQ to get the information you actually want.

To sum up, your options are:

  1. Don't use LINQ, just SQL with recursive CTE
  2. Use recursive CTE in a stored procedure from LINQ
  3. Use LINQ, creating one query for each level
  4. Use ugly LINQ query limited to just a few levels
svick
  • 236,525
  • 50
  • 385
  • 514
  • Is this recursive CTE able to handle 3^30+ levels of data? – Ryan Sep 05 '11 at 22:40
  • 3
    Do you really mean 3^30 levels? That's an awfully huge number. If one level took just one byte, the whole tree would have 187 TB. – svick Sep 05 '11 at 22:57
  • Good point... I probably wouldnt need 3^30 but probably more like 3^16. It will be an n-ary so it won't be exactly 3^16+ but it can get that high... BTW I just tried it with 3^10 and the query took 8+ mins to run. – Ryan Sep 05 '11 at 23:20
0

I know this is late, but if you look at Directed Graph algorithms, you can bypass the recursive issues. check out these 2 articles:

http://www.sitepoint.com/hierarchical-data-database/

http://www.codeproject.com/Articles/22824/A-Model-to-Represent-Directed-Acyclic-Graphs-DAG-o

PhantomRick
  • 52
  • 5