Linq query recursion

Question

I work in C# and Entity framework. I have a table in my database named Genre. Here are its attributes: idGenre, name, idParentGenre.

For example. the values would be:

(idGenre = 1, name = "acoustic", idParentGenre=2)

(idGenre = 2, name = "rock", idParentGenre=2)

(idGenre = 3, name = "country", idParentGenre=4)

(idGenre = 4, name = "folk", idParentGenre=5)

(idGenre = 5, name = "someOtherGenre", idParentGenre=5)

As you can see, it's kind of a tree.

Now, I have a method for searching through this table. The input parameter is idGenre and idParentGenre. I should return if the genre (idGenre) is a son/grandchild/grandgrandchild/... of idParentGenre.

For example, I get idGenre=3, idParentGenre=5, I should return true.

However, there isn't recursion in Linq. Is there a way I can do this?

What do you mean by "recursion in Linq". Can you show the method that you have? What is wrong with it? — alf, Dec 28 '11 at 20:57
Do it the old fashion way. LINQ is great, but it cannot solve every problem. — cadrell0, Dec 28 '11 at 20:59

score 4 · Accepted Answer · edited Oct 03 '13 at 11:48

I would make a method to handle this instead of using LINQ:

bool HasParent(int genre, int parent)
{
    Genre item = db.Genres.FirstOrDefault(g => g.IdGenre == genre);
    if (item == null)
        return false;

    // If there is no parent, return false, 
    // this is assuming it's defined as int?
    if (!item.idParentGenre.HasValue)
        return false;

    if (item.idParentGenre.Value == parent)
        return true;

    return HasParent(item.idParentGenre, parent);
}

This lets you handle this in a single recursive function.

score 2 · Answer 2 · edited May 23 '17 at 10:32

It looks like you're trying to implement a tree without using a tree.

Have you considered...using a tree? Here's a great question and some answers you could build off (including one with code:

delegate void TreeVisitor<T>(T nodeData);

class NTree<T>
{
    T data;
    LinkedList<NTree<T>> children;

    public NTree(T data)
    {
        this.data = data;
        children = new LinkedList<NTree<T>>();
    }

    public void addChild(T data)
    {
        children.AddFirst(new NTree<T>(data));
    }

    public NTree<T> getChild(int i)
    {
        foreach (NTree<T> n in children)
            if (--i == 0) return n;
        return null;
    }

    public void traverse(NTree<T> node, TreeVisitor<T> visitor)
    {
        visitor(node.data);
        foreach (NTree<T> kid in node.children)
            traverse(kid, visitor);
    }        
}

I can't use a tree. I have a table in my database for this purpose. — petko_stankoski, Dec 28 '11 at 21:05

Sergey Kalinichenko · Answer 3 · 2011-12-28T21:15:55.760

1

Bring the table of genres in the memory (it cannot be that big), and recursively traverse it to create a mapping between an idGenre and a transitive closure of its descendents, like this:

1: {1, 2}
2: {2}
3: {3, 4, 5}
4: {4, 5}
5: {5}

The data above stays only in memory. You recompute it every time on start-up, and on updates to the genres table.

When it is time to query for all songs in a specific genre, use the pre-calculated table in an idGenre in ... query, like this:

IEnumerable<Song> SongsWithGenreId(int idGenre) {
    var idClosure = idToIdClosure[idGenre];
    return context.Songs.Where(song => idClosure.Contains(song.idGenre));
}

edited Dec 28 '11 at 21:15

answered Dec 28 '11 at 21:02

Sergey Kalinichenko

714,442
84
1,110
1,523

But this isn't a perfect solution. I already have a place where I place the id of the parent (this place is the table), I don't think another place for the same purpose is good. – petko_stankoski Dec 28 '11 at 21:07
@Srcee It isn't "another place" to store your data, it's a cache of the same data, only preprocessed. Your queries would be very fast - much faster than anything else suggested so far, because there will be only one roundtrip. All the recursion would be baked into the structure of the `idToIdClosure` dictionary, which is good, because genres do not change all that often. – Sergey Kalinichenko Dec 28 '11 at 21:12

Linq query recursion

3 Answers3