Selecting An Adjacency Model into a Parental Model

Databases
1

This should be simple enough, but i’m apparently having a Friday Morning.

I have an adjacency model table:

id INT,
name VARCHAR,
lft INT,
rgt INT

I need to select all nodes in the table (Optional, but desired: Skipping the Root node.) , and retrieve ONLY their immediate parent, because the display model requires a (id,name,parent) tuple with a unique id.

The following pulls a row for every ancestor:

SELECT node.id id, node.name name, parent.id parent
FROM mytable AS node, 
mytable AS parent 
WHERE node.lft BETWEEN parent.lft AND parent.rgt 
AND node.lft != parent.lft
ORDER BY node.lft;

My brain keeps trying to do GROUP BY, but that doesnt tie the parent row’s columns together.

2

So maybe my brain is also in Friday mode but how is the parent defined? isn’t it just the left?

3

Left is the leftmost-bound-of-this-tree, right is the rightmost-bound-of-this-tree.

So Say you have

Root
-Node1
--Node2
-Node3

Left and right would be:

Node Left Right
Root 1 8
Node1 2 5
Node2 3 4
Node3 6 7

A node is a Leaf if Right-Left = 1; otherwise there is a tree underneath this node.

4

So you want something like this? Maybe?

SELECT node.id id
     , node.name name
     , parent.id parentID
     , parent.name parentName
  FROM mytable AS node
 INNER JOIN mytable AS parent ON node.lft = parent.id 
 WHERE node.rgt = 1
 ORDER BY node.lft;

This should skip the root since there will be no parent info. Not sure the order makes sense (maybe parent.id, node.id would make more sense?)

5

On his example I never see that a left value is equal to a right value. so your inner join will never match

6

Yeah that confused me a bit. I just changed the join to match to parent.ID (which would make more sense regardless.)

7

To describe it in words first:

you take a row and search for another row where left ist smaller then actual left and right is greater then the actual right. For this you will ge multiple results. From this results you search for the one with the smallest left, This must be your parent.

Is this correct?

8

Smallest Right, or Largest Left would be your immediate parent.

For All Entries in the Table, Find The Row Which:
My Left(or right, either works) is Between Your Left and Right, Uninclusive. (“I am a descendant of you”)
Has the closest (Left/Right) to my (Left/Right) (“My Immediate Parent”)

(EDIT: If you dont make the first condition uninclusive, the “immediate parent” is the node itself.)

9

I don’t think you can go the way getting the child from the parent. With your logic you will get all rows of your example table when the actual row is root. But you will never know, that node2 has node1 as parent as this is not part of the result.

I guess you need to go other way around. Get the parent of the row by fetching the row with left < actual left and right > actual right (is a parent) and only take the one with the smallest left (direct parent)

10

Again, it wouldnt be the smallest left.

Consider my example before:

Node Left Right
Root 1 8
Node1 2 5
Node2 3 4
Node3 6 7

If I start at Node2, and find all rows where L < 3 and R > 4, I get Node1 and Root.
The “smallest left” is Root, because 1 is the smallest. But the immediate parent is Node1. you need the largest left.

11

Sorry I meant the nearest left not the smallest

12

yeah. largest left, nearest left, smallest distance (from either end)… all will work, because the L< l, R>r will find just the encapsulating elements.

13

I have only a solution with subquery. It’s untested so not sure if it works

SELECT id, name, (SELECT id 
                  FROM nodes np 
                  WHERE np.lft < no.left and np.rgt > no.rgt 
                  ORDER BY np.lft DESC 
                  LIMIT 1) AS parent
FROM nodes no
14

I had honestly forgotten about subquerying as a field as opposed to a JOIN.

15

it’s a scalar subquery

it returns a tabular result consisting of one row of one column, i.e. a scalar value

it can be used in SQL anywhere you can have a literal, e.g. 42

16

Yeah… it’s just i dont automatically think about a scalar evaluating per-row? Like, “42” is a fixed value. And normally when you want to combine two sets of data, it’s a join between tables.

Selecting a “scalar” in this case to me doesnt… really feel like you’re selecting a scalar, because you’re actually effectively pulling a vector - a single column of per-row results that relies upon a parameter (the row’s id in this case)

In truth, it’s probably more accurate to say its no different than pulling a simple formula (like say, somecolumn + 4 ), but it feels different than that because you’re selecting? I dunno.

18

but you cannot pull more than one row

if your subquery returns more than one row, and it’s supposed to be a scalar subquery, instead of a true column of multiple rows which you might use with IN (subquery), then you get a “your subquery has returned more than one row” error message