Checking inherited attributes in an 'ancestry' based SQL table

Question

I'm using the ancestry gem to help organise my app's tree structure in the database. It basically writes a childs ancestor information to a special column called 'ancestry'. The ancestry column for a particular child might look like '1/34/87' where the parent of this child is 87, and then 87's parent is 34 and 34's is 1.

It seems possible that we could select rows from this table each with a subquery that checks all the ancestors to see if a certain attribute it set. E.g. in my app you can hide an item and its children just by setting the parent element's visibility column to 0.

I want to be able to find all the items where none of their ancestors are hidden. I tried converting the slashes to comma's with the REPLACE command but IN required a set of comma separated integers rather than one string with comma separated string numbers.

It's funny, because I can do this query in two steps, e.g. retrieve the row, then take its ancestry column, split out the id's and make another query that checks that the id is IN that set of id's and that visibility isn't ever 0 and whala! But joining these into one query seems to be quite a task. Much searching has shown a few answers but none really do what I want.

SELECT * FROM t1 WHERE id = 99;

99's ancestry column reads '1/34/87'

SELECT * FROM t1 WHERE visibility = 0 AND id IN (1,34,87);

kind of backwards, but if this returns no rows then the item is visible.

Has anyone come across this before and come up with a solution. I don't really want to go the stored procedure route. It's for a rails app.

Answer 1

What you might want to do is create a Split function, if you do not already have one (Split a Delimited String in SQL ) and then use that as the IN selection.

There is also another way, but it might degrade performance on large tables. Something like

SELECT  *
FROM    Table t INNER JOIN
        Table tParents      
        ON  (   t.Path LIKE CAST(tParents.ID AS VARCHAR(20)) + '/%'
                OR  t.Path LIKE +'%/' + CAST(tParents.ID AS VARCHAR(20)) + '/%'
                OR  t.Path LIKE +'%/' + CAST(tParents.ID AS VARCHAR(20)))

WHERE   t.ID = 99
AND     tParents.Visible = 0

Answer 2

If you insist on getting away from stored/procedural why not switch to nested sets from your materialized paths approach?

Otherwise, do the two queries from the application side (or use stored procedure as suggested by astander).

Good links for hierarchies in SQL here

EDIT: It seems that you are storing information about the state of the tree control in the database.

Assuming that this is really justified and that you need to store the visibility in the database you might investigate the following scenarios (these are ideas, not immediate solutions):

1. open a cursor/recordset/whatever-row-based-approach-is-called-in-your-framework and pass that to the tree control so that the number of updates and fetches from the database are related to the actions on the tree (making branches visible, updating visibility, hiding branches, etc). In this case (depending on the framework) you don't have to preselect the proper elements (nor issue select statement every time user closes or opens a branch).

2. update the visibility in the database for all children. it seems that you are updating visibility only on a node that is expanded/collapsed (if you need to preserve visibility of collapsed branches and leafs then you might have two fields; this is not elegant, but I would test this option, too)

3. investigate nested sets again; with nested sets required queries might become faster. Also it becomes a bit easier to write SQL (here's SQL that returns nodes that have all parents visible, assuming visibility is tinyint(1); BIT_AND will do aggregate AND on all the parents in a single query)

   SELECT node.name AS name
   FROM t1 AS node,
   t1 AS parent
   WHERE node.visibility = 1 AND node.lft BETWEEN parent.lft AND parent.rgt
   GROUP BY node.name
   HAVING BIT_AND(parent.visibility) = 1
   ORDER BY node.lft

(this is tested, I took example from here, and added visibility)

Also, when you test and benchmark each solution do not forget to benchmark all the operations (selecting visible branches, opening hidden branches, marking node invisible, etc..).