Another implementation option that I've recently worked on...
My tree is very simple.
public class Node
{
public int NodeID { get; set; }
public string Name { get; set; }
public virtual Node ParentNode { get; set; }
public int? ParentNodeID { get; set; }
public virtual ICollection<Node> ChildNodes { get; set; }
public int? LeafID { get; set; }
public virtual Leaf Leaf { get; set; }
}
public class Leaf
{
public int LeafID { get; set; }
public string Name { get; set; }
public virtual ICollection<Node> Nodes { get; set; }
}
My requirements, not so much.
Given a set of leaves and a single ancestor, show children of that ancestor who have descendants that have leaves within the set
An analogy would be a file structure on disk. The current user has access to a subset of files on the system. As the user opens nodes in the file system tree, we only want to show that user nodes that will, eventually, lead them to the files they can see. We don't want to show them file paths to files they do not have access to (for security reasons, e.g., leaking the existence of a document of a certain type).
We want to be able to express this filter as an IQueryable<T>, so we can apply it to any node query, filtering out unwanted results.
To do this, I created a Table Valued Function that returns the descendants for a node in the tree. It does this via a CTE.
CREATE FUNCTION [dbo].[DescendantsOf]
(
@parentId int
)
RETURNS TABLE
AS
RETURN
(
WITH descendants (NodeID, ParentNodeID, LeafID) AS(
SELECT NodeID, ParentNodeID, LeafID from Nodes where ParentNodeID = @parentId
UNION ALL
SELECT n.NodeID, n.ParentNodeID, n.LeafID from Nodes n inner join descendants d on n.ParentNodeID = d.NodeID
) SELECT * from descendants
)
Now, I'm using Code First, so I had to use
https://www.nuget.org/packages/EntityFramework.Functions
in order to add the function to my DbContext
[TableValuedFunction("DescendantsOf", "Database", Schema = "dbo")]
public IQueryable<NodeDescendant> DescendantsOf(int parentID)
{
var param = new ObjectParameter("parentId", parentID);
return this.ObjectContext().CreateQuery<NodeDescendant>("[DescendantsOf](@parentId)", param);
}
with a complex return type (couldn't reuse Node, looking into that)
[ComplexType]
public class NodeDescendant
{
public int NodeID { get; set; }
public int LeafID { get; set; }
}
Putting it all together allowed me, when the user expands a node in the tree, to get the filtered list of child nodes.
public static Node[] GetVisibleDescendants(int parentId)
{
using (var db = new Models.Database())
{
int[] visibleLeaves = SuperSecretResourceManager.GetLeavesForCurrentUserLol();
var targetQuery = db.Nodes as IQueryable<Node>;
targetQuery = targetQuery.Where(node =>
node.ParentNodeID == parentId &&
db.DescendantsOf(node.NodeID).Any(x =>
visibleLeaves.Any(y => x.LeafID == y)));
// Notice, still an IQueryable. Perform whatever processing is required.
SortByCurrentUsersSavedSettings(targetQuery);
return targetQuery.ToArray();
}
}
It's important to note that the function is executed on the server, not in the application. Here's the query that gets executed
SELECT
[Extent1].[NodeID] AS [NodeID],
[Extent1].[Name] AS [Name],
[Extent1].[ParentNodeID] AS [ParentNodeID],
[Extent1].[LeafID] AS [LeafID]
FROM [dbo].[Nodes] AS [Extent1]
WHERE ([Extent1].[ParentNodeID] = @p__linq__0) AND ( EXISTS (SELECT
1 AS [C1]
FROM ( SELECT
[Extent2].[LeafID] AS [LeafID]
FROM [dbo].[DescendantsOf]([Extent1].[NodeID]) AS [Extent2]
) AS [Project1]
WHERE EXISTS (SELECT
1 AS [C1]
FROM ( SELECT 1 AS X ) AS [SingleRowTable1]
WHERE [Project1].[LeafID] = 17
)
))
Note the function call within the query above.
