Device trees, or Implementing recursive tree descent in Priority (part one)

One of the standard entities in Priority is called 'Catalogue of Parts w/Serial Nos.' but I prefer the name 'devices'. In its simplest form, a device is a part that has a serial number. For example, all cars of a given model would have the same part number but would have individual serial numbers. Another standard entity that vaguely exists in Priority is a 'device tree'; for example, the car that I mentioned in the previous sentence has its own serial number, but its engine has its own serial number. Together the car and the engine form a device tree, where the car is the parent/father/ancestor device and the engine is the son device.

I wrote above that this standard entity vaguely exists in Priority: there are two tables that apparently hold data about device trees, SONSERN and SONSERNENV. These tables appear to be built every time a device tree needs to be shown (in a son form of the SERNUMBERS form) by an external program called SONSERN, but I have not been able to ascertain the source of the data that SONSERN uses to build the trees. The source may be in 'Warehouse Assemblies' but I haven't been able to verify this.

One of my clients uses a hand-rolled version of device trees that I developed several years ago. These device trees are what might be called 'degenerate trees': they only have two levels (parent and sons) and so aren't really trees. Another client approached me a few days ago with a similar need for device trees, except here we are talking about trees with at least three levels of device (I don't think that there will be four levels, but one never knows).

Device trees are very similar to BOMs, at least in concept: Priority maintains a simple table (PARTARC) in which data are held regarding the sons of a given parent. Let's say that part A is a parent; it will have sons B1, B2 and B3. But these sons can also have sons of their own: B1C1, B1C2, B2C1, B2C2, B3C1, B3C2, etc. A simple database table enables access to the sons of a given parent, but this table does not allow access (or more correctly, cannot store data relating) to 'grandchildren'. In order to display the complete structure of a BOM, one uses the SONRAW program about which I have written in the past. SONRAW converts the one level data into a hierarchical format.

Conceptually, the external program SONSERN is equivalent to SONRAW, but as I wrote earlier, I do not know from where SONSERN derives its raw data and so it is essentially useless for my purposes. In order to display a complete device tree, or turn simple one level data in hierarchical data, one needs to implement what is known in computer science terms as 'recursive tree descent'. That's all well and good in programming languages that support recursion such as Pascal, C and Python (there are many more), but not good in a very basic language such as SQL and its Priority implementation. 

Computer science tells us that recursion can be replaced by iteration; sometimes the conversion is simple and sometimes complicated. The first example always given is that of calculating factorials: the factorial of 2 is 2 * 1 (* is the multiplication operator) and the factorial of 3 is 3 * 2 * 1. This is actually an iterative method; the elegant method of calculating the factorial of a number X is simply X * factorial (X - 1). This is known as a recursive function as the function invokes itself albeit with a different parameter each time.

Here is the factorial function, first written in the recursive style then in the iterative style. I'm going to write them in Pascal as this is the most natural for me. It is important to note that every function - especially a recursive one - has what is called a termination condition. Here in both versions, the termination occurs when n = 0.

Function RecursiveFactorial (n: integer): integer;
begin
 if n = 0 
  then result:= 1
  else result:= n * RecursiveFactorial (n - 1)
end;

Function IterativeFactorial (n: integer): integer;
begin
 result:= 1;
 while n > 0 do
  begin
   result:= result * n;
   dec (n)
  end
end;  

The factorial is probably the worst function to use as an example as the iterative version is just as simple to understand and will have better performance than the recursive version, especially when n becomes large.

Descending a tree is a much more complicated function than calculating a factorial. A simplistic and idealised version of this would be something like

 Procedure Search (node: tnode);
 begin
  if node = nil
   then DoSomething
   else
    begin
     search (node^.left);
     search (node^.right)
    end 
 end;
 
 search (ancestor);

This pseudocode would traverse - or descent - through what is known as a binary tree, where every parent has only two sons. Normally the binary tree is sorted so that the left son (or node) sorts prior to the right son. The above pseudocode would display all the nodes in sorted order.

But that's not what we have with a device tree: each parent can have several sons and there is no specific order between sons of a parent. As this is getting further and further away from Priority, I'll leave this now and continue in another blog entry.