Get total count of object's elements and all children objects` elements

Question

I have a table, Taxonomy, with data that looks something like the following:

TaxID | ParentID | Name
-----------------------------------
1 | NULL | Animal
2 | 1 | Cat
3 | 1 | Dog
4 | 1 | Fish
5 | 3 | Poodle
6 | 3 | Golden Retriever
7 | 4 | Goldfish

I then have a second table, Table2, that has records that reference the TaxIDs in Taxonomy. I've labeled the foreign key column referencing Taxonomy, FK_TaxID.

FK_TaxID | Field2
------------------
1 | value
1 | value
1 | value
2 | value
2 | value
2 | value
3 | value

The resulting hierarchy looks something like the following:

- Parent (TaxID=1; #elements=15)
 - Child (TaxID=2; #elements=3)
 - Child (TaxID=3; #elements=8)
 - GrandChild (TaxID=6; #elements=2)
 - GrandChild (TaxID=5; #elements=0)
 - Child (TaxID=4; #elements=5)
 - GrandChild (TaxID=7; #elements=10)

The #elements is based on how many times the TaxID appears in Table2.

I have a method that takes in a Taxonomy ID, and returns the total element count for the record and its sub-children.

For example:

• If ID = 1, count should = 43.
• If ID = 3, count should = 10.
• If ID = 5, count should = 0.

Here is the code I am currently using:

public int GetCount(int ID)
{
 List<int> childrenIDs = DbContext.Taxonomy
 .Where(x => x.ParentID == ID)
 .Select(x => x.TaxID)
 .ToList();
 List<int> grandchildrenIDs = DbContext.Taxonomy
 .Where(x => childrenIDs.Contains(x.ParentID))
 .Select(x => x.TaxID)
 .ToList();
 int count = DbContext.Table2.Count(x => x.FK_TaxID == ID
 || childrenIDs.Contains(x.FK_TaxID)
 || grandchildrenIDs.Contains(x.FK_TaxID));
 return count;
}

This code gets the count in three steps:

1. Sets childrenIDs to equal the list of records where the ParentID equals the given ID.
2. Sets grandchildrenIDs to equal the list of records where childrenIDs contains the ParentID.
3. Gets the count of Table2 records where the FK_TaxID equals the inputted ID, or childrenIDs contains the FK_TaxID or grandchildrenIDs contains the FK_TaxID.

This method returns the correct results, yet it is quite slow, and seems overly complicated.

How can I simplify this method? Can I somehow get rid or one of the lists and get all the IDs in one call? Is there a more efficient way of doing this than using Contains() twice?

• Maxim: Maybe it is worth to grab all IDs from the first table and turn them into tree. Traversing a tree is a very simple operation so I think it will be quick. Here you can find an algorithm that turns flat structure of IDs to tree – How to efficiently build a tree from a flat structure?. Seems like it is your case.
• Bobson: If your tree is relatively static, you might want to consider something like Modified Preorder Tree Traversal which trades really slow update performance (it has to recalculate every node in the entire tree) for really fast read performance - every possible traversal of the tree is a single simple select statement, and counts can be simple arithmetic (not even a count() statement!).

Answer 1

Why do you need to make the .ToList() call instead of keeping the IEnumerable objects returned by Select methods?

 public int GetCount(int ID) 
 { 
 var childrenIDs = DbContext.Taxonomy 
 .Where(x => x.ParentID == ID) 
 .Select(x => x.TaxID); 
 var grandchildrenIDs = DbContext.Taxonomy 
 .Where(x => childrenIDs.Contains(x.ParentID)) 
 .Select(x => x.TaxID); 
 var count = DbContext.Table2.Count(x => 
 x.FK_TaxID == ID ||
 childrenIDs.Contains(x.FK_TaxID) ||
 grandchildrenIDs.Contains(x.FK_TaxID)); 
 return count; 
}

This way, the only call to database is the last one.

Answer 2

You should be able to do something recursively like this. Note: I could not validate, may need some tweaking.

public int GetCount(int ID)
{
 return 
 DbContext.Taxonomy
 .Where(x => x.ParentID == ID)
 .Select(x => x.TaxID)
 .ToList() 
 .Select(x => GetCount(x))
 .Sum() + DbContext.Table2.Count(x => x.FK_TaxID == ID);
}