Search Results

Search found 24 results on 1 pages for 'hierarchyid'.

Page 1/1 | 1 

  • Question about SQL Server HierarchyID depth-first performance

    - by AndalusianCat
    I am trying to implement hierarchyID in a table (dbo.[Message]) containing roughly 50,000 rows (will grow substantially in the future). However it takes 30-40 seconds to retrieve about 25 results. The root node is a filler in order to provide uniqueness, therefor every subsequent row is a child of that dummy row. I need to be able to traverse the table depth-first and have made the hierarchyID column (dbo.[Message].MessageID) the clustering primary key, have also added a computed smallint (dbo.[Message].Hierarchy) which stores the level of the node. Usage: A .Net application passes through a hierarchyID value into the database and I want to be able to retrieve all (if any) children AND parents of that node (besides the root, as it is filler). A simplified version of the query I am using: @MessageID hierarchyID /* passed in from application */ SELECT m.MessageID, m.MessageComment FROM dbo.[Message] as m WHERE m.Messageid.IsDescendantOf(@MessageID.GetAncestor((@MessageID.GetLevel()-1))) = 1 ORDER BY m.MessageID From what I understand, the index should be detected automatically without a hint. From searching forums I have seen people utilizing index hints, at least in the case of breadth-first indexes, as apparently CLR calls may be opaque to the query optimizer. I have spent the past few days trying to find a solution for this issue, but to no avail. I would greatly appreciate any assistance, and as this is my first post, I apologize in advance if this would be considered a 'noobish' question, I have read the MS documentation and searched countless forums, but have not came across a succinct description of the specific issue.

    Read the article

  • SQL 2008 HierarchyID - Select X descendants down

    - by NTulip
    How can I query a table which has a column of data type HIERARCHYID and get a list of descendants X levels deep under an employee? Here is the current structure: CREATE TABLE [dbo].[Employees]( [NodeId] [hierarchyid] NOT NULL, [EmployeeId] [int] IDENTITY(1,1) NOT NULL, [FirstName] [varchar](120) NULL, [MiddleInitial] [varchar](1) NULL, [LastName] [varchar](120) NULL, [DepartmentId] [int] NULL, [Title] [varchar](120) NULL, [PhoneNumber] [varchar](20) NULL, [IM] [varchar](120) NULL, [Photo] [varbinary](max) NULL, [Bio] [varchar](400) NULL, [Active] [bit] NULL, [ManagerId] [int] NULL )

    Read the article

  • SqlMetal, Sql Server 2008 database, Table with HierachyID, dal cs file is created sometimes ?

    - by judek.mp
    I have 2 databases with a 2 tables with HierachyID fields. For one database I can get a dal cs file, for the other database I cannot get a dal cs file ? HBus is a database I can get the dal cs for, ... SqlMetal /server:.\SQLSERVER2008 /database:HBus /code:HBusDC.cs /views /functions /sprocs /namespace:HBusDC /context:HBusDataContext This kicks me out a file, ... which works, but excludes the HierarchyID field for the table and includes all other fields for that table. This is OK I do not mind. The above cmd line kicks out an warning but still produces a file, like so SqlMetal /server:.\SQLSERVER2008 /database:HBus /code:HBusDC.cs /views /functions /sprocs /namespace:HBusDC /context:HBusDataContext Microsoft (R) Database Mapping Generator 2008 version 1.00.30729 for Microsoft (R) .NET Framework version 3.5 Copyright (C) Microsoft Corporation. All rights reserved. Warning : SQM1021: Unable to extract column 'OrgNode' of Table 'dbo.HMsg' from SqlServer because the column's DbType is a user-defined type (UDT). Warning : SQM1021: Unable to extract column 'OrgNode' of Table 'dbo.vwHMsg' from SqlServer because the column's DbType is a user-defined type (UDT). HMsg is a table with a HierarchyID field. I have another database, Elf, almost the same thing but I get a warning and an Error when using sql metal and I do not get a dal cs file ... SqlMetal /server:.\SQLSERVER2008 /database:Elf /code:ElfDataContextDal.cs /views /functions /sprocs /namespace:HBusDC /context:HBusDataContext An error as well as the warning and the cs file fails to appear on my disc, ... :-( SqlMetal /server:.\SQLSERVER2008 /database:Elf /code:ElfDataContextDal.cs /views /functions /sprocs /namespace:HBusDC /context:HBusDataContext Microsoft (R) Database Mapping Generator 2008 version 1.00.30729 for Microsoft (R) .NET Framework version 3.5 Copyright (C) Microsoft Corporation. All rights reserved. Warning : SQM1021: Unable to extract column 'OrgNode' of Table 'dbo.EntityLink' from SqlServer because the column's DbType is a user-defined type (UDT). Error : Requested value 'ELF.SYS.HIERARCHYID' was not found. The fields are declared the same way in Elf db OrgNode [HierarchyID] null , in HBus db ... OrgNode [HierarchyID] null , Both databases are in the same instance of sql server 2008, so the HierarchyID is an inbuilt type, neither db has HierarchyID udt ,... cheers in advance for any replies ...

    Read the article

  • Aggregate path counts using HierarchyID

    - by austincav
    Business problem - understand process fallout using analytics data. Here is what we have done so far: Build a dictionary table with every possible process step Find each process "start" Find the last step for each start Join dictionary table to last step to find path to final step In the final report output we end up with a list of paths for each start to each final step: User Fallout Step HierarchyID.ToString() A 1/1/1 B 1/1/1/1/1 C 1/1/1/1 D 1/1/1 E 1/1 What this means is that five users (A-E) started the process. Assume only User B finished, the other four did not. Since this is a simple example (without branching) we want the output to look as follows: Step Unique Users 1 5 2 5 3 4 4 2 5 1 The easiest solution I could think of is to take each hierarchyID.ToString(), parse that out into a set of subpaths, JOIN back to the dictionary table, and output using GROUP BY. Given the volume of data, I'd like to use the built-in HierarchyID functions, e.g. IsAncestorOf. Any ideas or thoughts how I could write this? Maybe a recursive CTE?

    Read the article

  • Should I worry about running out of HierarchyIDs?

    - by Bruno Martinez
    When you ask for a new HierarchyID between two others, the result gets progressively longer. For example, between 2/5.6 and 2/5.7 there's only 2/5.6.1 and other 4 component paths. The HierarchyID data type is limited to 800 some bytes, so you can't repeat this forever. Then again, integer types are also limited, but it isn't a problem in practice. Should I periodically defragment my table so that height doesn't grow unbounded?

    Read the article

  • Challenge 19 – An Explanation of a Query

    - by Dave Ballantyne
    I have received a number of requests for an explanation of my winning query of TSQL Challenge 19. This involved traversing a hierarchy of employees and rolling a count of orders from subordinates up to superiors. The first concept I shall address is the hierarchyId , which is constructed within the CTE called cteTree.   cteTree is a recursive cte that will expand the parent-child hierarchy of the personnel in the table @emp.  One useful feature with a recursive cte is that data can be ‘passed’ from the parent to the child data.  The hierarchyId column is similar to the hierarchyId data type that was introduced in SQL Server 2008 and represents the position of the person within the organisation. Let us start with a simplistic example Albert manages Bob and Eddie.  Bob manages Carl and Dave. The hierarchyId will represent each person’s position in this relationship in a single field.  In this simple example we could append the userID together into a varchar field as detailed below. This will enable us to select a branch of the tree by filtering using Where hierarchyId  ‘1,2%’ to select Bob and all his subordinates.  Naturally, this is not comprehensive enough to provide a full solution, but as opposed to concatenating the Id’s together into a varchar datatyped column, we can apply the same theory to a varbinary.  By CASTing the ID’s into a datatype of varbinary(4) ,4 is used as 4 bytes of data are used to store an integer and building a hierarchyId  from those.  For example: The important point to bear in mind for later in the query is that the binary data generated is 'byte order comparable'. ie We can ORDER a dataset with it and the resulting data, will be in the order required. Now, would probably be a good time to download the example file and, after the cte ‘cteTree’, uncomment the line ‘select * from cteTree’.  Mark this and all prior code and execute.  This will show you how this theory directly relates to the actual challenge data.  The only deviation from the above, is that instead of using the ID of an employee, I have used the row_number() ranking function to order each level by LastName,Firstname.  This enables me to order by the HierarchyId in the final result set so that the result set is in the required order. Your output should be something like the below.  Notice also the ‘Level’ Column that contains the depth that the employee is within the tree.  I would encourage you to ‘play’ with the query, change the order in the row_number() or the length of the cast in the hierarchyId to see how that effects the outcome.  The next cte, ‘cteTreeWithOrderCount’, is a join between cteTree and the @ord table, and COUNT’s the number of orders per employee.  A LEFT JOIN is employed here to account for the occasion where an employee has made no sales.   Executing a ‘Select * from cteTreeWithOrderCount’ will return the result set as below.  The order here is unimportant as this is only a staging point of the data and only the final result set in a cte chain needs an Order by clause, unless TOP is utilised. cteExplode joins the above result set to the tally table (Nums) for Level Occurances.  So, if level is 2 then 2 rows are required.  This is done to expand the dataset, to create a new column (PathInc), which is the (n+1) integers contained within the heirarchyid.  For example, with the data for Robert King as given above, the below 3 rows will be returned. From this you can see that the pathinc column now contains the values for Andrew Fuller and Steven Buchanan who are Robert King’s superiors within the tree.    Finally cteSumUp, sums the orders for each person and their subordinates using the PathInc generated above, and the final select does the final simple mathematics and filters to restrict the result set to only the ‘original’ row per employee.

    Read the article

  • Sorting tree with other column in SQL Server 2008

    - by bodziec
    Hi, I have a table which implements a tree using hierarchyid column Sample data: People \ Girls \1\ Zoey \1\1\ Kate \1\2\ Monica \1\3\ Boys \2\ Mark \2\1\ David \2\2\ This is the order using hierarchyid column as sort column I would like to sort data using hierarchyid but also using name so it would look like this: People \ Boys \2\ David \2\2\ Mark \2\1\ Girls \1\ Kate \1\2\ Monica \1\3\ Zoey \1\1\ Is there a simple solution to do this? Czy da sie to zrobic w jednym zapytaniu sql ?

    Read the article

  • How to call a scalar function in a stored procedure

    - by Luke101
    I am wacking y head over the problem with this code. DECLARE @root hierarchyid declare @lastchild hierarchyid SELECT @root = NodeHierarchyID from NodeHierarchy where ID = 1 set @lastchild = getlastchild(@root) it says it does not recognize getlastchild function. What am I doing wrong here

    Read the article

  • SQL SERVER – Four Tutorial for SQL Server 2012 New Features

    - by pinaldave
    One of the very common question I receive on my facebook is that if there is any tutorial for SQL Server 2012 new enhanced features and solutions. I see this demand a bit increasing as the SQL Server 2012 is more and more being adopted. Here is the list of four tutorial which is specifically created for SQL Server 2012 by Microsoft. Multidimensional Modeling (Adventure Works Tutorial) This tutorial teaches you how to develop and deploy an Analysis Services project that enables the employees of Adventure Works Cycles to analyze various aspects of their business. Tabular Modeling (Adventure Works Tutorial) This tutorial teaches you how to create a SQL Server 2012 Analysis Services tabular model that enable sales and marketing teams to easily analyze internet sales data in the AdventureWorksDW2012 data warehouse. You will build the tabular model in SQL Server Data Tools. Tutorials and Demos for Power View Create Power View reports and explore Power View features. View demos, videos, and tutorials that help you get started quickly with Power View and successfully build reports with interactive filters and visualizations such as bubble charts, tiles, and cards. Tutorial: Using the hierarchyid Data Type This tutorial is intended for users who are experienced with Transact-SQL, but are new to the hierarchyid data type. In this tutorial, you convert an existing table to a hierarchical structure, and you also create a new table to store and manage hierarchical data efficiently. Note: The description of the course is taken from original course description. You will need to install SQL Server 2012 AdventureWorks for all this tutorial. Reference: Pinal Dave (http://blog.sqlauthority.com) Filed under: PostADay, SQL, SQL Authority, SQL Query, SQL Server, SQL Tips and Tricks, SQL Training, T SQL, Technology

    Read the article

  • Bound a treeview control to user-defined complex type using EF 4

    - by GIbboK
    Hi, I use Asp.net, SQL 2008 and EF 4. I need display hierarchy data in a treeview control, Data is stored in a DB that use HierarchyId. Unfortunately, EF4 doesn't support HierarchyId. So in this case, I thought to have a stored procedure that deals with my hierarchy and return a result set back to EF that EF4 can turn into a collection of user-defined complex type that can then be bound directly to the treeview control. I imported a SPROC in EF 4 using Import Function and now I have a Complex DataType called: CategoryHierarchy_Result An image of my Model: Here some data from the Complex Type (in a GridView for example GridView1.DataSource = context.CategoryHierarchy(1);): My questions is: How to display my data from my Complex Type in a TreeView Control, showing a Tree structure that respect CategoryNodeString? I am a beginner an I never use TreeView before, any help or resource would be appreciated! Thanks!. Here some useful resource: http://www.robbagby.com/entity-framework/entity-framework-modeling-action-stored-procedures/

    Read the article

  • Hierarchies in SQL, Part II, the Sequel

    In a followup to his first article on Hierarchies, Gus Gwynn takes a look at the performance of a few different methods of querying a hierarchy. Learn how the HierarchyID stacks up. Are you sure you can restore your backups? Run full restore + DBCC CHECKDB quickly and easily with SQL Backup Pro's new automated verification. Check for corruption and prepare for when disaster strikes. Try it now.

    Read the article

  • Is there a way to turn this query to regular inline SQL

    - by Luke101
    I would like to turn this query to regular inline sql without using stored procedures declare @nod hierarchyid select @nod = DepartmentHierarchyNode from Organisation where DepartmentHierarchyNode = 0x6BDA select * from Organisation where @nod.IsDescendantOf(DepartmentHierarchyNode) = 1 Is there a way to do it?

    Read the article

  • Hierarchical data in Linq - options and performance

    - by Anthony
    I have some hierarchical data - each entry has an id and a (nullable) parent entry id. I want to retrieve all entries in the tree under a given entry. This is in a SQL Server 2005 database. I am querying it with LINQ to SQL in C# 3.5. LINQ to SQL does not support Common Table Expressions directly. My choices are to assemble the data in code with several LINQ queries, or to make a view on the database that surfaces a CTE. Which option (or another option) do you think will perform better when data volumes get large? Is SQL Server 2008's HierarchyId type supported in Linq to SQL?

    Read the article

  • Storing website hierarchy in Sql Server 2008

    - by Mika Kolari
    I want to store website page hierarchy in a table. What I would like to achieve is efficiently 1) resolve (last valid) item by path (e.g. "/blogs/programming/tags/asp.net,sql-server", "/blogs/programming/hello-world" ) 2) get ancestor items for breadcrump 3) edit an item without updating the whole tree of children, grand children etc. Because of the 3rd point I thought the table could be like ITEM id type slug title parentId 1 area blogs Blogs 2 blog programming Programming blog 1 3 tagsearch tags 2 4 post hello-world Hello World! 2 Could I use Sql Server's hierarchyid type somehow (especially point 1, "/blogs/programming/tags" is the last valid item)? Tree depth would usually be around 3-4. What would be the best way to achieve all this?

    Read the article

  • Something for the weekend - Whats the most complex query?

    - by simonsabin
    Whenever I teach about SQL Server performance tuning I try can get across the message that there is no such thing as a table. Does that sound odd, well it isn't, trust me. Rather than tables you need to consider structures. You have 1. Heaps 2. Indexes (b-trees) Some people split indexes in two, clustered and non-clustered, this I feel confuses the situation as people associate clustered indexes with sorting, but don't associate non clustered indexes with sorting, this is wrong. Clustered and non-clustered indexes are the same b-tree structure(and even more so with SQL 2005) with the leaf pages sorted in a linked list according to the keys of the index.. The difference is that non clustered indexes include in their structure either, the clustered key(s), or the row identifier for the row in the table (see http://sqlblog.com/blogs/kalen_delaney/archive/2008/03/16/nonclustered-index-keys.aspx for more details). Beyond that they are the same, they have key columns which are stored on the root and intermediary pages, and included columns which are on the leaf level. The reason this is important is that this is how the optimiser sees the world, this means it can use any of these structures to resolve your query. Even if your query only accesses one table, the optimiser can access multiple structures to get your results. One commonly sees this with a non-clustered index scan and then a key lookup (clustered index seek), but importantly it's not restricted to just using one non-clustered index and the clustered index or heap, and that's the challenge for the weekend. So the challenge for the weekend is to produce the most complex single table query. For those clever bods amongst you that are thinking, great I will just use lots of xquery functions, sorry these are the rules. 1. You have to use a table from AdventureWorks (2005 or 2008) 2. You can add whatever indexes you like, but you must document these 3. You cannot use XQuery, Spatial, HierarchyId, Full Text or any open rowset function. 4. You can only reference your table once, i..e a FROM clause with ONE table and no JOINs 5. No Sub queries. The aim of this is to show how the optimiser can use multiple structures to build the results of a query and to also highlight why the optimiser is doing that. How many structures can you get the optimiser to use? As an example create these two indexes on AdventureWorks2008 create index IX_Person_Person on Person.Person (lastName, FirstName,NameStyle,PersonType) create index IX_Person_Person on Person.Person(BusinessentityId,ModifiedDate)with drop_existing    select lastName, ModifiedDate   from Person.Person  where LastName = 'Smith' You will see that the optimiser has decided to not access the underlying clustered index of the table but to use two indexes above to resolve the query. This highlights how the optimiser considers all storage structures, clustered indexes, non clustered indexes and heaps when trying to resolve a query. So are you up to the challenge for the weekend to produce the most complex single table query? The prize is a pdf version of a popular SQL Server book, or a physical book if you live in the UK.  

    Read the article

  • please help me to add the html fields in the following link [closed]

    - by user237389
    Link Name: http://business.careerbuilderinstitute.com/testportal/webservices/iscapi.asmx/CreateUser html code register.html <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <title>Web-Service User Registration Form</title> </head> <body> <b style="font-size:20px; color:#3366CC">CreateUser</b><br/><br/> Create a user account. User may be assigned to a particular hierarchy level.<br/><br/> <b>Test</b><br/><br/> To test the operation using the HTTP POST protocol, click the 'Invoke' button. <form action="http://business.careerbuilderinstitute.com/testportal/webservices/iscapi.asmx/CreateUser" method="POST"/> <table width="542" border="0" style="margin-left:25px;"> <tr> <th width="172" style="background-color:#c0c0c0;">Parameter</th> <th width="360" style="background-color:#c0c0c0;">Value</th> </tr> <tr> <input name="authorizationId" type="text" value="TestService" size="60" /> </tr> <tr> <input name="passcode" type="hidden" value="welcome" size="60"/> </tr> <tr> <input name="organizationId" type="hidden" value="27" size="60"/> </tr> <tr> <input name="globalUniqueId" type="hidden" value="GUID" size="60"/> </tr> <tr> <input name="hierarchyID" type="hidden" value="0" size="60"/> </tr> <tr> <input name="hireDate" type="hidden" value="1" size="60"/> </tr> <tr> <input name="studentProfileId" type="hidden" value="0" size="60"/> </tr> <tr> <input name="alternateId" type="hidden" value="0" size="60"/> </tr> <tr> <input name="alternateId2" type="hidden" value="0" size="60"/> </tr> <tr> <input name="alternateId3" type="hidden" value="0" size="60"/> </tr> <tr> <input name="ssn" type="hidden" value="0" size="60"/> </tr> <tr> <input name="license" type="hidden" value="0" size="60"/> </tr> <tr> <input name="comments" type="hidden" value="0" size="60"/> </tr> <tr> <input name="clientDrive" type="hidden" value="0" size="60"/> </tr> <tr> <input name="nickname" type="hidden" value="0" size="60"/> </tr> <tr> <input name="photoIcon" type="hidden" value="0" size="60"/> </tr> <tr> <input name="cellPhone" type="hidden" value="0" size="60"/> </tr> <tr> <input name="blogUniformResourceLocator" type="hidden" value="0" size="60"/> </tr> <tr> <input name="userResume" type="hidden" value="0" size="60"/> </tr> <tr> <input name="resumeAttach" type="hidden" value="0" size="60"/> </tr> <tr> <input name="education" type="hidden" value="0" size="60"/> </tr> <tr> <input name="experience" type="hidden" value="0" size="60"/> </tr> <tr> <input name="reflections" type="hidden" value="0" size="60"/> </tr> <tr> <input name="storeFrontID" type="hidden" value="0" size="60"/> </tr> <!-- <tr> <input name="resumeAttach" type="hidden" value="0" size="60"/> </tr> --> <tr> <input name="siteadministrator" type="hidden" value="0" size="60" /> </tr> <tr> <input name="instructor" type="hidden" value="0" size="60" /> </tr> <tr> <input name="student" type="hidden" value="1" size="60" /> </tr> <tr> <input name="supervisor" type="hidden" value="0" size="60"/> </tr> <!-- "This field should be passed in the URL with Account did" <tr> <input name="hierarchyID" type="hidden" value="0" size="60"/> </tr> "This field is not required" <tr> <input name="studentProfileId" type="hidden" value="" /> </tr> <tr> --> </tr> <tr> <th scope="row" align="left">firstName:</th> <td><input name="firstName" type="text" size="60" id="firstName"/></td> </tr> <tr> <th scope="row" align="left">lastName:</th> <td><input name="lastName" type="text" size="60"/></td> </tr> <tr> <th scope="row" align="left">userName:</th> <td><input name="userName" type="text" size="60" /></td> </tr> <tr> <th scope="row" align="left">password:</th> <td><input name="password" type="password" size="60" /></td> </tr> <tr> <th scope="row" align="left">email:</th> <td><input name="email" type="text" size="60" /></td> </tr> <tr> </tr> <tr> <th scope="row" align="left">organization:</th> <td><input name="organization" type="text" size="60" /></td> </tr> <tr> <th scope="row" align="left">jobTitle:</th> <td><input name="jobTitle" type="text" size="60" /></td> </tr> <tr> <th scope="row" align="left">department:</th> <td><input name="department" type="text" size="60" /></td> </tr> <tr> <th scope="row" align="left">location:</th> <td><input name="location" type="text" size="60" /></td> </tr> <th scope="row" align="left">phone:</th> <td><input name="phone" type="text" size="60" /></td> </tr> <tr> <th scope="row" align="left">fax:</th> <td><input name="fax" type="text" size="60" /></td> </tr> <tr> <th scope="row" align="left">address:</th> <td><input name="address" type="text" size="60" /></td> </tr> <tr> <th scope="row" align="left">address2:</th> <td><input name="address2" type="text" size="60" /></td> </tr> <tr> <th scope="row" align="left">city:</th> <td><input name="city" type="text" size="60" /></td> </tr> <tr> <th scope="row" align="left">state:</th> <td><input name="state" type="text" size="60" /></td> </tr> <tr> <th scope="row" align="left">country:</th> <td><input name="country" type="text" size="60" /></td> </tr> <tr> <th scope="row" align="left">zip:</th> <td><input name="zip" type="text" size="60" /></td> </tr> <tr> </tr> <tr> </tr> <tr> </tr> <tr> </tr> <tr> </tr> <tr> </tr> <tr> </tr> <tr> </tr> <tr> </tr> <tr> </tr> <tr> </tr> <tr> </tr> <tr> <input name="languagePreference" type="hidden" value="1" size="60" /> </tr> <tr> <input name="active" type="hidden" value="1" size="60" /> </tr> <tr> <th scope="row" align="left"></th> <td><input name="Invoke" type="submit" value="Invoke" /></td> </tr> </table> </form> </body> </html>

    Read the article

  • What are the Options for Storing Hierarchical Data in a Relational Database?

    - by orangepips
    Good Overviews One more Nested Intervals vs. Adjacency List comparison: the best comparison of Adjacency List, Materialized Path, Nested Set and Nested Interval I've found. Models for hierarchical data: slides with good explanations of tradeoffs and example usage Representing hierarchies in MySQL: very good overview of Nested Set in particular Hierarchical data in RDBMSs: most comprehensive and well organized set of links I've seen, but not much in the way on explanation Options Ones I am aware of and general features: Adjacency List: Columns: ID, ParentID Easy to implement. Cheap node moves, inserts, and deletes. Expensive to find level (can store as a computed column), ancestry & descendants (Bridge Hierarchy combined with level column can solve), path (Lineage Column can solve). Use Common Table Expressions in those databases that support them to traverse. Nested Set (a.k.a Modified Preorder Tree Traversal) First described by Joe Celko - covered in depth in his book Trees and Hierarchies in SQL for Smarties Columns: Left, Right Cheap level, ancestry, descendants Compared to Adjacency List, moves, inserts, deletes more expensive. Requires a specific sort order (e.g. created). So sorting all descendants in a different order requires additional work. Nested Intervals Combination of Nested Sets and Materialized Path where left/right columns are floating point decimals instead of integers and encode the path information. Bridge Table (a.k.a. Closure Table: some good ideas about how to use triggers for maintaining this approach) Columns: ancestor, descendant Stands apart from table it describes. Can include some nodes in more than one hierarchy. Cheap ancestry and descendants (albeit not in what order) For complete knowledge of a hierarchy needs to be combined with another option. Flat Table A modification of the Adjacency List that adds a Level and Rank (e.g. ordering) column to each record. Expensive move and delete Cheap ancestry and descendants Good Use: threaded discussion - forums / blog comments Lineage Column (a.k.a. Materialized Path, Path Enumeration) Column: lineage (e.g. /parent/child/grandchild/etc...) Limit to how deep the hierarchy can be. Descendants cheap (e.g. LEFT(lineage, #) = '/enumerated/path') Ancestry tricky (database specific queries) Database Specific Notes MySQL Use session variables for Adjacency List Oracle Use CONNECT BY to traverse Adjacency Lists PostgreSQL ltree datatype for Materialized Path SQL Server General summary 2008 offers HierarchyId data type appears to help with Lineage Column approach and expand the depth that can be represented.

    Read the article

  • Handling inheritance with overriding efficiently

    - by Fyodor Soikin
    I have the following two data structures. First, a list of properties applied to object triples: Object1 Object2 Object3 Property Value O1 O2 O3 P1 "abc" O1 O2 O3 P2 "xyz" O1 O3 O4 P1 "123" O2 O4 O5 P1 "098" Second, an inheritance tree: O1 O2 O4 O3 O5 Or viewed as a relation: Object Parent O2 O1 O4 O2 O3 O1 O5 O3 O1 null The semantics of this being that O2 inherits properties from O1; O4 - from O2 and O1; O3 - from O1; and O5 - from O3 and O1, in that order of precedence. NOTE 1: I have an efficient way to select all children or all parents of a given object. This is currently implemented with left and right indexes, but hierarchyid could also work. This does not seem important right now. NOTE 2: I have tiggers in place that make sure that the "Object" column always contains all possible objects, even when they do not really have to be there (i.e. have no parent or children defined). This makes it possible to use inner joins rather than severely less effiecient outer joins. The objective is: Given a pair of (Property, Value), return all object triples that have that property with that value either defined explicitly or inherited from a parent. NOTE 1: An object triple (X,Y,Z) is considered a "parent" of triple (A,B,C) when it is true that either X = A or X is a parent of A, and the same is true for (Y,B) and (Z,C). NOTE 2: A property defined on a closer parent "overrides" the same property defined on a more distant parent. NOTE 3: When (A,B,C) has two parents - (X1,Y1,Z1) and (X2,Y2,Z2), then (X1,Y1,Z1) is considered a "closer" parent when: (a) X2 is a parent of X1, or (b) X2 = X1 and Y2 is a parent of Y1, or (c) X2 = X1 and Y2 = Y1 and Z2 is a parent of Z1 In other words, the "closeness" in ancestry for triples is defined based on the first components of the triples first, then on the second components, then on the third components. This rule establishes an unambigous partial order for triples in terms of ancestry. For example, given the pair of (P1, "abc"), the result set of triples will be: O1, O2, O3 -- Defined explicitly O1, O2, O5 -- Because O5 inherits from O3 O1, O4, O3 -- Because O4 inherits from O2 O1, O4, O5 -- Because O4 inherits from O2 and O5 inherits from O3 O2, O2, O3 -- Because O2 inherits from O1 O2, O2, O5 -- Because O2 inherits from O1 and O5 inherits from O3 O2, O4, O3 -- Because O2 inherits from O1 and O4 inherits from O2 O3, O2, O3 -- Because O3 inherits from O1 O3, O2, O5 -- Because O3 inherits from O1 and O5 inherits from O3 O3, O4, O3 -- Because O3 inherits from O1 and O4 inherits from O2 O3, O4, O5 -- Because O3 inherits from O1 and O4 inherits from O2 and O5 inherits from O3 O4, O2, O3 -- Because O4 inherits from O1 O4, O2, O5 -- Because O4 inherits from O1 and O5 inherits from O3 O4, O4, O3 -- Because O4 inherits from O1 and O4 inherits from O2 O5, O2, O3 -- Because O5 inherits from O1 O5, O2, O5 -- Because O5 inherits from O1 and O5 inherits from O3 O5, O4, O3 -- Because O5 inherits from O1 and O4 inherits from O2 O5, O4, O5 -- Because O5 inherits from O1 and O4 inherits from O2 and O5 inherits from O3 Note that the triple (O2, O4, O5) is absent from this list. This is because property P1 is defined explicitly for the triple (O2, O4, O5) and this prevents that triple from inheriting that property from (O1, O2, O3). Also note that the triple (O4, O4, O5) is also absent. This is because that triple inherits its value of P1="098" from (O2, O4, O5), because it is a closer parent than (O1, O2, O3). The straightforward way to do it is the following. First, for every triple that a property is defined on, select all possible child triples: select Children1.Id as O1, Children2.Id as O2, Children3.Id as O3, tp.Property, tp.Value from TriplesAndProperties tp -- Select corresponding objects of the triple inner join Objects as Objects1 on Objects1.Id = tp.O1 inner join Objects as Objects2 on Objects2.Id = tp.O2 inner join Objects as Objects3 on Objects3.Id = tp.O3 -- Then add all possible children of all those objects inner join Objects as Children1 on Objects1.Id [isparentof] Children1.Id inner join Objects as Children2 on Objects2.Id [isparentof] Children2.Id inner join Objects as Children3 on Objects3.Id [isparentof] Children3.Id But this is not the whole story: if some triple inherits the same property from several parents, this query will yield conflicting results. Therefore, second step is to select just one of those conflicting results: select * from ( select Children1.Id as O1, Children2.Id as O2, Children3.Id as O3, tp.Property, tp.Value, row_number() over( partition by Children1.Id, Children2.Id, Children3.Id, tp.Property order by Objects1.[depthInTheTree] descending, Objects2.[depthInTheTree] descending, Objects3.[depthInTheTree] descending ) as InheritancePriority from ... (see above) ) where InheritancePriority = 1 The window function row_number() over( ... ) does the following: for every unique combination of objects triple and property, it sorts all values by the ancestral distance from the triple to the parents that the value is inherited from, and then I only select the very first of the resulting list of values. A similar effect can be achieved with a GROUP BY and ORDER BY statements, but I just find the window function semantically cleaner (the execution plans they yield are identical). The point is, I need to select the closest of contributing ancestors, and for that I need to group and then sort within the group. And finally, now I can simply filter the result set by Property and Value. This scheme works. Very reliably and predictably. It has proven to be very powerful for the business task it implements. The only trouble is, it is awfuly slow. One might point out the join of seven tables might be slowing things down, but that is actually not the bottleneck. According to the actual execution plan I'm getting from the SQL Management Studio (as well as SQL Profiler), the bottleneck is the sorting. The problem is, in order to satisfy my window function, the server has to sort by Children1.Id, Children2.Id, Children3.Id, tp.Property, Parents1.[depthInTheTree] descending, Parents2.[depthInTheTree] descending, Parents3.[depthInTheTree] descending, and there can be no indexes it can use, because the values come from a cross join of several tables. EDIT: Per Michael Buen's suggestion (thank you, Michael), I have posted the whole puzzle to sqlfiddle here. One can see in the execution plan that the Sort operation accounts for 32% of the whole query, and that is going to grow with the number of total rows, because all the other operations use indexes. Usually in such cases I would use an indexed view, but not in this case, because indexed views cannot contain self-joins, of which there are six. The only way that I can think of so far is to create six copies of the Objects table and then use them for the joins, thus enabling an indexed view. Did the time come that I shall be reduced to that kind of hacks? The despair sets in.

    Read the article

1