nhibernate query for double linked list

Question

CREATE TABLE [dbo].[Field](
    [FieldId] [int] IDENTITY(1,1) NOT NULL,
    [Name] [varchar](500) NULL,
    [NextTaskTemplateFieldId] [int] NULL,
    [PreviousTaskTemplateFieldId] [int] NULL
) ON [PRIMARY]

insert into field values('chicken',2,3)
insert into field values('the',1,null)
insert into field values('home',null,2)
insert into field values('runs',3,1)

Fluent nhibernate mapping is

public FieldMap()
        {
            Table("Field");
            Id(x => x.Id).Column("FieldId");
            Map(entity => entity.Name);
            Map(entity => entity.PreviousTaskTemplateFieldId);
            Map(entity => entity.NextTaskTemplateFieldId);
        }

Hi can someone help me with the nhibernate query which will give me the correct ordering of the double linked list.

Should return in the order of: 'the','Chicken' 'runs' 'home'

thanks niall

Answer 1

Before I get started, your example has a cycle in it, meaning that any attempt to iterate over the list will result in an infinite loop:

chicken --> the --> chicken --> the --> (etc)

The rest of this answer assumes there's valid data in your linked list structure.

---

There are basically two ways to approach this, and I'll go over the pros and cons of each one.

First off, all of these strategies involve changing your Field class and your mapping slightly:

Class:

public class Field
{
    public virtual int Id { get; set; }

    public virtual string Name { get; set; }

    public virtual Field NextTaskTemplateField { get; set; }

    public virtual Field PreviousTaskTemplateField { get; set; }
}

Mapping:

public class FieldMap : ClassMap<Field>
{
    public FieldMap()
    {
        Table("Field");
        Id(f => f.Id).Column("FieldId");
        Map(f => f.Name);
        References(f => f.NextTaskTemplateField)
            .Column("NextTaskTemplateFieldId");

        References(f => f.PreviousTaskTemplateField)
            .Column("PreviousTaskTemplateFieldId");
    }
}

The main point here is that we've mapped references to adjacent fields in the list rather than just keeping Ids of the next and previous nodes in the list.

1. Query for the "head" of the linked list and simply iterate through related nodes.

   This is simple and easy to understand, but it generates one select statement for each node, which is not ideal. Basically, just grab the first node (the node with no PreviousTaskTemplateField) and loop until the node you're on doesn't have a NextTaskTemplateField:

   Field head = session.QueryOver<Field>()
       .Where(f => f.PreviousTaskTemplateField == null)
       .TransformUsing(Transformers.RootEntity)
       .SingleOrDefault();
   
   // If you know the FieldId of the Field you want to get as the front of the list,
   // just use session.Get<Field>(1);
   
   Field node = head;
   while (node != null)
   {
       Console.WriteLine(node.Name);
       node = node.NextTaskTemplateField;
   }
   

   Again, this is not really an ideal solution if you care about performance. Every time you load the next Field in the list, a new select statement goes out.

2. Use a recursive CTE and a named query

   Since it looks like you're using SQL server, you may be able to use a recursive CTE to get the entire list in one go. Here's what the CTE would look like:

   with [Field_CTE]
   as
   (
       -- Base case: The node with no previous item
       select
           [Field].[FieldId],
           [Field].[Name],
           [Field].[NextTaskTemplateFieldId],
           [Field].[PreviousTaskTemplateFieldId],
           0 as [Index]
       from
           dbo.[Field]
       where
           [Field].[PreviousTaskTemplateFieldId] is null
   
       union all
   
       select
           [Field].[FieldId],
           [Field].[Name],
           [Field].[NextTaskTemplateFieldId],
           [Field].[PreviousTaskTemplateFieldId],
           [Field_CTE].[Index] + 1 as [Index]
       from
           dbo.[Field]
           inner join [Field_CTE] on 
               [Field_CTE].[NextTaskTemplateFieldId] = [Field].[FieldId]
   )
   select
       [Field_CTE].[FieldId],
       [Field_CTE].[Name],
       [Field_CTE].[NextTaskTemplateFieldId],
       [Field_CTE].[PreviousTaskTemplateFieldId]
   from
       [Field_CTE]
   order by
       [Field_CTE].[Index] asc;
   

   This will get us the linked list in its entirety in one query. One change you would possibly have to make is to add the ability to get a list head by Id instead of just grabbing the Field with no previous Field. This code assumes that there's only one list in the database, but you should be able to expand on it.

   Unfortunately we cannot translate this into an NHibernate query, so we'll have to create a named query. It's easiest to wrap the CTE in a stored procedure before doing this, so I created a stored procedure called SP_GetFieldList:

   create procedure SP_GetFieldList
   as
   begin
       -- CTE code above
   end
   

   Then, we'll need to create an *.hbm.xml file containing the named query:

   <?xml version="1.0" encoding="utf-8"?>
   <hibernate-mapping xmlns="urn:nhibernate-mapping-2.2">
     <sql-query name="FieldListQuery">
       <!-- replace the "class" attribute with the location of your class -->
       <return alias="field" class="ConsoleApplication2.Field,ConsoleApplication2" />
       exec SP_GetFieldList
     </sql-query>
   </hibernate-mapping>
   

   Finally, we can call the named query and map to a List<Field>:

   IEnumerable<Field> linkedList = session.GetNamedQuery("FieldListQuery")
       .SetResultTransformer(Transformers.DistinctRootEntity)
       .List<Field>();
   

   The major advantage of this strategy is that we're only executing one SQL query for the entire list.