Re: Approximate structural conditions in trees

>> Suppose I have trees (ordered node-labeled trees, vulgo XML
documents, to be precise) and I want to search them for some structural conditions. <<

Look at my nested set model. By putting the structure in a separate talbe from the values at the nodes, you can do some of these things. For every node (rgt-lft +1)/2 = the size of the subtree which is rooted at that node.

You can put all subtrees into a canonical form with

 INSERT INTO WorkingTree (root, node, lft, rgt)  SELECT :my_node_1, T1.node, T1.lft, T1.rgt    FROM Tree AS T1, Tree AS T2
  WHERE T1.node = :my_node_1
    AND T1.lft BETWEEN T2.lft AND T2.rgt;

 INSERT INTO WorkingTree (root, node, lft, rgt)  SELECT :my_node_2, T1.node, T1.lft, T1.rgt    FROM Tree AS T1, Tree AS T2
  WHERE T1.node = :my_node_2
    AND T1.lft BETWEEN T2.lft AND T2.rgt;

The test condition for structural equality is now:

(SELECT COUNT(*)
   FROM WorkingTree
  GROUP BY lft, rgt
 HAVING COUNT(*) = 2)
= (SELECT COUNT(*)
     FROM WorkingTree
    WHERE node = :my_node_1)
AND
(SELECT COUNT(*)
   FROM WorkingTree
  GROUP BY lft, rgt
 HAVING COUNT(*) = 2)
= (SELECT COUNT(*)
     FROM WorkingTree
    WHERE node = :my_node_2) Received on Thu Jul 11 2002 - 15:06:15 CEST