使用MySQL从树中选择记录

Question

Note: You might want to skip to the bottom to read the actual question before reading all this additional stuff.

I'm working on a ACL implementation for CakePHP. Mainly cause I'm trying to decouple it from AuthComponeny so I can use Authsome for my projects. I have the theory of implementation down but I've hit a little stumbling block.

Obviously I want to keep the number of database queries down to a minimum. So I'm asking here on the off chance that this is possible (I seriously doubt it is.)

Assuming a table structure like this:

id - int(10), auto_increment, primary_key, not null
parent_id - int(10), null
model - varchar(255), utf8_bin, null
foreign_key - int(10), null
alias - varchar(255), utf8_bin, null,
lft - int(10), null
rght - int(10), null

And a few records to test (controllers is the root node and I might get the lft and rght values wrong):

1, null, null, null, controllers,          1,  14
2, 1,    null, null, one_test_controllers, 2,  7
3, 2,    null, null, one_action,           3,  4
4, 2,    null, null, two_action,           5,  6
5, 1,    null, null, two_test_controllers, 8,  13
6, 5,    null, null, one_action,           9,  10
7, 5,    null, null  two_action,           11, 12

And two test paths:

$test1 = '/controllers/one_test_controller/two_action';
$test2 = '/controllers/two_test_controller/two_action';

Giving these results, returning an array of ids from most relevant to least relevant:

// Result 1
array(
    0 => 4,
    1 => 2,
    2 => 1
)

// Result 2
array(
    0 => 7,
    1 => 5,
    2 => 1
)

What I'm currently doing is explode()ing the path into and array, (using $test1 for this example) first finding all records that match the alias "two_action"; then looping through the results and finding all records that match the parent id's of the last result and have the alias of "one_test_controller". Then repeat until parent_id = 0.

It works but obviously multiple recursive SQL queries are not ideal, is there a magic SQL query that can help me with this? Or am I right in assuming that this is the best it can get?

Answer 1

eh? You've already got the structure to fetch the data by parsing the path in a single pass with the adjacency tree.

However without storing the full path / requiring unique node names, you can't search from the bottom up. Consider - in both your test cases you're starting with 'two_action' but looking for 2 different leafs. If you store the entire path in the table (or can reference the nodes by id from your query) then....

SELECT ancestors.*
FROM ahier ancestors,
(SELECT lft, rght
  FROM ahier ref
  WHERE ref.path='/controllers/one_test_controller/two_action') ilv
WHERE (ancestors.lft >= ilv.left AND ancestors.rght <= ilv.rght)
ORDER BY ancestors.lft ASC;

or using ids:

SELECT ancestors.*
FROM ahier ancestors,
(SELECT lft, rght
  FROM ahier ref
  WHERE ref.id=4) ilv
WHERE (ancestors.lft >= ilv.left AND ancestors.rght <= ilv.rght)
ORDER BY ancestors.lft ASC;

Alternatively, you could write a query to return every possible path which has a specific node alias - but that's not going to be very efficient either....

SELECT treenum, ancestors.*
FROM ahier ancestors,
(SELECT lft, rght, id as treenum
  FROM ahier ref
  WHERE ref.alias='two_action') ilv
WHERE (ancestors.lft >= ilv.left AND ancestors.rght <= ilv.rght)
ORDER BY treenum, ancestors.lft ASC;

(and its easy enought to rebuild lft and rght from the parent_ids)