Dati gerarchici in Linq: opzioni e prestazioni

StackOverflow https://stackoverflow.com/questions/202912

Domanda

Ho alcuni dati gerarchici - ogni voce ha un ID e un ID voce nulla (nullable). Voglio recuperare tutte le voci nell'albero in una determinata voce. Questo si trova in un database di SQL Server 2005. Lo sto interrogando con LINQ to SQL in C # 3.5.

LINQ to SQL non supporta Common Table Expressions . Le mie scelte sono di assemblare i dati in codice con diverse query LINQ o di fare una vista sul database che presenta un CTE.

Quale opzione (o un'altra) pensi che funzionerà meglio quando i volumi di dati diventano grandi? Il HierarchyId type di SQL Server 2008 è supportato in Linq to SQL?

È stato utile?

Soluzione

Vorrei impostare una vista e una funzione basata su tabella associata basata sul CTE. Il mio ragionamento per questo è che, mentre potresti implementare la logica sul lato dell'applicazione, ciò comporterebbe l'invio dei dati intermedi sul cavo per il calcolo nell'applicazione. Utilizzando il designer DBML, la vista si traduce in un'entità tabella. È quindi possibile associare la funzione all'entità Table e richiamare il metodo creato su DataContext per derivare oggetti del tipo definito dalla vista. L'uso della funzione basata su tabella consente al motore di query di tenere conto dei parametri durante la costruzione del set di risultati anziché applicare una condizione sul set di risultati definito dalla vista dopo il fatto. 

CREATE TABLE [dbo].[hierarchical_table](
    [id] [int] IDENTITY(1,1) NOT NULL,
    [parent_id] [int] NULL,
    [data] [varchar](255) NOT NULL,
 CONSTRAINT [PK_hierarchical_table] PRIMARY KEY CLUSTERED 
(
    [id] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]

CREATE VIEW [dbo].[vw_recursive_view]
AS
WITH hierarchy_cte(id, parent_id, data, lvl) AS
(SELECT     id, parent_id, data, 0 AS lvl
      FROM         dbo.hierarchical_table
      WHERE     (parent_id IS NULL)
      UNION ALL
      SELECT     t1.id, t1.parent_id, t1.data, h.lvl + 1 AS lvl
      FROM         dbo.hierarchical_table AS t1 INNER JOIN
                            hierarchy_cte AS h ON t1.parent_id = h.id)
SELECT     id, parent_id, data, lvl
FROM         hierarchy_cte AS result


CREATE FUNCTION [dbo].[fn_tree_for_parent] 
(
    @parent int
)
RETURNS 
@result TABLE 
(
    id int not null,
    parent_id int,
    data varchar(255) not null,
    lvl int not null
)
AS
BEGIN
    WITH hierarchy_cte(id, parent_id, data, lvl) AS
   (SELECT     id, parent_id, data, 0 AS lvl
        FROM         dbo.hierarchical_table
        WHERE     (id = @parent OR (parent_id IS NULL AND @parent IS NULL))
        UNION ALL
        SELECT     t1.id, t1.parent_id, t1.data, h.lvl + 1 AS lvl
        FROM         dbo.hierarchical_table AS t1 INNER JOIN
            hierarchy_cte AS h ON t1.parent_id = h.id)
    INSERT INTO @result
    SELECT     id, parent_id, data, lvl
    FROM         hierarchy_cte AS result
RETURN 
END

ALTER TABLE [dbo].[hierarchical_table]  WITH CHECK ADD  CONSTRAINT [FK_hierarchical_table_hierarchical_table] FOREIGN KEY([parent_id])
REFERENCES [dbo].[hierarchical_table] ([id])

ALTER TABLE [dbo].[hierarchical_table] CHECK CONSTRAINT [FK_hierarchical_table_hierarchical_table]

Per usarlo dovresti fare qualcosa del genere - ipotizzando uno schema di denominazione ragionevole: 

using (DataContext dc = new HierarchicalDataContext())
{
    HierarchicalTableEntity h = (from e in dc.HierarchicalTableEntities
                                 select e).First();
    var query = dc.FnTreeForParent( h.ID );
    foreach (HierarchicalTableViewEntity entity in query) {
        ...process the tree node...
    }
}

Altri suggerimenti

Questa opzione potrebbe anche rivelarsi utile:

Metodo di estensione LINQ AsHierarchy ()
http://www.scip.be/index.php?Page=ArticlesNET18

Sono sorpreso che nessuno abbia menzionato una progettazione di database alternativa: quando la gerarchia deve essere appiattita da più livelli e recuperata con prestazioni elevate (non considerando lo spazio di archiviazione) è meglio usare un'altra tabella entità-2-entità per tenere traccia della gerarchia invece dell'approccio parent_id.

Consentirà non solo le relazioni monoparentali, ma anche relazioni multi-genitori, indicazioni di livello e diversi tipi di relazioni: 

CREATE TABLE Person (
  Id INTEGER,
  Name TEXT
);

CREATE TABLE PersonInPerson (
  PersonId INTEGER NOT NULL,
  InPersonId INTEGER NOT NULL,
  Level INTEGER,
  RelationKind VARCHAR(1)
);

Ho fatto due modi:

  1. Guidare il recupero di ogni livello dell'albero in base all'input dell'utente. Immagina un controllo di visualizzazione ad albero popolato con il nodo radice, i figli della radice e i nipoti della radice. Solo la radice e i figli vengono espansi (i nipoti vengono nascosti con il collasso). Man mano che l'utente espande un nodo figlio, vengono visualizzati i nipoti della radice (precedentemente recuperati e nascosti) e viene avviato un recupero di tutti i pronipoti. Ripeti il ??motivo per gli strati N profondi. Questo modello funziona molto bene per alberi di grandi dimensioni (profondità o larghezza) perché recupera solo la parte dell'albero necessaria.
  2. Utilizzare una procedura memorizzata con LINQ. Utilizzare qualcosa come un'espressione di tabella comune sul server per creare i risultati in una tabella piatta o creare un albero XML in T-SQL. Scott Guthrie ha un grande articolo sull'uso dei proc memorizzati in LINQ. Costruisci il tuo albero dai risultati quando tornano se in un formato piatto, oppure usa l'albero XML se è quello che restituisci.

Questo metodo di estensione potrebbe essere potenzialmente modificato per usare IQueryable. L'ho usato con successo in passato su una collezione di oggetti. Potrebbe funzionare per il tuo scenario. 

public static IEnumerable<T> ByHierarchy<T>(
 this IEnumerable<T> source, Func<T, bool> startWith, Func<T, T, bool> connectBy)
{
  if (source == null)
   throw new ArgumentNullException("source");

  if (startWith == null)
   throw new ArgumentNullException("startWith");

  if (connectBy == null)
   throw new ArgumentNullException("connectBy");

  foreach (T root in source.Where(startWith))
  {
   yield return root;
   foreach (T child in source.ByHierarchy(c => connectBy(root, c), connectBy))
   {
    yield return child;
   }
 }
}

Ecco come l'ho chiamato: 

comments.ByHierarchy(comment => comment.ParentNum == parentNum, 
 (parent, child) => child.ParentNum == parent.CommentNum && includeChildren)

Questo codice è una versione migliorata e corretta del bug trovato qui .

In MS SQL 2008 è possibile utilizzare HierarchyID direttamente, in sql2005 potrebbe essere necessario implementarli manualmente. ParentID non è quello performante su grandi set di dati. Controlla anche questo articolo per ulteriori discussioni sull'argomento.

Ho ottenuto questo approccio dal il blog di Rob Conery (controlla intorno al punto 6 per questo codice, anche su codeplex) e adoro usarlo. Questo potrebbe essere adattato per supportare più "sotto" sotto i livelli. 

var categories = from c in db.Categories
                 select new Category
                 {
                     CategoryID = c.CategoryID,
                     ParentCategoryID = c.ParentCategoryID,
                     SubCategories = new List<Category>(
                                      from sc in db.Categories
                                      where sc.ParentCategoryID == c.CategoryID
                                      select new Category {
                                        CategoryID = sc.CategoryID, 
                                        ParentProductID = sc.ParentProductID
                                        }
                                      )
                             };

Il problema con il recupero dei dati dal lato client è che non si può mai essere sicuri della profondità necessaria. Questo metodo eseguirà un roundtrip per profondità e potrebbe essere eseguito l'unione da 0 a una profondità specificata in un roundtrip. 

public IQueryable<Node> GetChildrenAtDepth(int NodeID, int depth)
{
  IQueryable<Node> query = db.Nodes.Where(n => n.NodeID == NodeID);
  for(int i = 0; i < depth; i++)
    query = query.SelectMany(n => n.Children);
       //use this if the Children association has not been defined
    //query = query.SelectMany(n => db.Nodes.Where(c => c.ParentID == n.NodeID));
  return query;
}

Tuttavia, non può fare una profondità arbitraria. Se hai davvero bisogno di una profondità arbitraria, devi farlo nel database, in modo da poter prendere la decisione corretta per interrompere.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top