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

To recap, this series of blog entries is discussing device trees and how to turn simple one-level (father:son) data into hierarchical  (grandparent: parents: children, etc) data. Once again, here is the tree that I am using as the example:

Father	Son
A	B1
A	B2
A	B3
B1	B1C1
B1	B1C2
B2	B2C1
B2	B2C2
B3	B3C1
B3	B3C2
B1C1	B1C1D1

In the previous installment, I showed how one can write code to descend through the tree; the devices accessed were B1, B1C1 and B1C1D1. Now the code has come to an impasse and has to backtrack (i.e. ascend back up the tree) in order to continue. When :NODE is equal to B1C1D1,the following query will fail and so control passes to LABEL 20.

LABEL 10;                                                           
SELECT SON INTO :SON                                                
FROM TEST_SERNTREE                                                  
WHERE FATHER = :NODE                                                  
AND USER = 0;                                                       
GOTO 20 WHERE :RETVAL <= 0; 
.
.
.
LABEL 20;                                                                                               
DELETE FROM STACK2 WHERE ELEMENT = :NODE;                                                                                    
GOTO 30 WHERE NOT EXISTS (SELECT 1 FROM STACK2 WHERE ELEMENT > 0);  
SELECT MAX (TYPE) INTO :MAX FROM STACK2;                            
SELECT ELEMENT INTO :NODE FROM STACK2 WHERE TYPE = :MAX;            
:LEVEL = :MAX;                                                      
LOOP 10;                                                            
LABEL 30;                      

This is the kludgey part of the code. One of the final lines prior to LABEL 20 sets :NODE equal to :SON (not shown) before the code loops back to LABEL 10. So at the first statement after LABEL 20, the current device (B1C1D1) is removed from STACK2, the table that is serving as the recursion's memory. Then there is a check that there is still data in STACK2 - this is the terminating condition. Following this, the maximal value of TYPE  is obtained - at this stage, this should be 3. Having this value enables the value of the final element in STACK2 to be copied into :NODE (or as they say in computer science circles, the value is popped off the stack). This should be B1C1. As there are no more sons of this device, LABEL 20 will be reached again and B1 popped off the stack. The code at LABEL 10 will ensure that the new value of :SON will be B1C2.

Eventually the final value (:ANCESTOR) will be deleted from STACK2 and so the code will jump to LABEL 30. At this stage, if everything has gone correctly, STACK4 will look like the following

KEY	INTDATA	INTDATA2
1	B1	2
2	B1C1	3
3	B1C1D1	4
4	B1C2	3
5	B2	2
6	B2C1	3
7	B2C2	3
8	B3	2
9	B3C1	3
10	B3C2	3

So at this stage, we have indeed achieved the goal of turning simple one-level data into hierarchical data. This is equivalent to the output of the SONRAW program. But there is one more detail that needs to be added: B1 should be displayed with the level 1, B1C1 as 1.1, B1C1D1 as 1.1.1, B1C2 as 1.2, etc. Fortunately there is no need to reinvent the wheel: I figured out how to do this with SONRAW data here. Again, this is a recursive requirement, and is turned into an iterative solution by means of a stack, again STACK2.

Below is a screen shot from Priority with the tree displayed with the levels.

 

---

Since writing these blog entries, I've been having second thoughts about some of the code. There is definitely no need for the field 'ANCESTOR' in the table TEST_SERNTREE. In the procedure that displays the tree, there is no need to access the 'USER' field either. STACK has to be given an alias in the form trigger code otherwise this doesn't work (presumably there is use of STACK somewhere else in the SERNTREE form. The first part of the procedure is now

LINK STACK4 TO :$.STK;
ERRMSG 1 WHERE :RETVAL <= 0;
LINK STACK2 TO :$.ST2;
ERRMSG 1 WHERE :RETVAL <= 0;
LINK STACK SST TO :$.ST0;
ERRMSG 1 WHERE :RETVAL <= 0;
:LINE = 0;
:LEVEL = 1;
INSERT INTO STACK2 (ELEMENT, TYPE)
VALUES (:ANCESTOR, 1);
:NODE = :ANCESTOR;
/***************************************************/
LABEL 10;
SELECT SON INTO :SON
FROM GLOB_SERNTREE
WHERE FATHER = :NODE
AND NOT EXISTS (SELECT 1 FROM STACK SST
WHERE SST.ELEMENT = GLOB_SERNTREE.SON 
GOTO 20 WHERE :RETVAL <= 0;
INSERT INTO STACK2 (ELEMENT, TYPE)
VALUES (:SON, :LEVEL + 1);
INSERT INTO STACK SST (ELEMENT) VALUES (:SON);
:LINE = :LINE + 1;
INSERT INTO STACK4 (KEY, INTDATA, INTDATA2)
VALUES (:LINE, :SON, :LEVEL + 1);
:NODE = :SON;
:LEVEL = :LEVEL + 1;
LOOP 10;

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

In the previous entry on this topic, I explained what a device tree is. In Priority, I defined a simple table (TEST_SERNTREE) that has three main fields: FATHER, SON and ANCESTOR. Using the previous example of a car and its engine, this table would hold the following tuple {Father: car serial number; Son: engine serial number; Ancestor: car serial number}. The Ancestor field* may not be needed for a strict implementation of device trees, but it helps in order to identify all the serials for a given tree. As I explained before, this is a simple one-level representation of data; it is required to write a procedure that turns this simple data into hierarchical data. A recursive procedure to create the hierarchical data in pseudocode would be something like

 Descend (ancestor);
 
 Procedure Descend (sern);
 begin
  if sern does not exist then exit;
  save data about this sern;
  node = first son of this sern that has yet to be accessed
  descend (node)
 end

As computer science tells us, any recursive algorithm can be replaced by an iterative one, and of course that is what is necessary for Priority. The above pseudocode requires some database definitions. "Save data about this sern" means saving it in a table such as STACK4. Initially I wrote a step procedure to display a hierarchical report where the data is saved in STACK4 but afterwards converted the procedure to a form trigger in order to display the data in a form; the trigger uses a dedicated table for this named TEST_SHOWSERNTREE. 

The second database definition needed handles the "sern that has yet to be accessed" requirement. Originally I saved the serns that have been accessed in a linked copy of STACK but for some reason this didn't work too well, so eventually I cheated somewhat and added a new field to the TEST_SERNTREE table, USER*. Initially the trigger sets this field to zero for every entry that has the given serial number as ancestor, then sets the value for each device encountered. 

Priority programmers are conditioned to use cursors as the primary means of extracting multiple tuples of data from the database. This is the correct means for 99.99% of all procedures, but for this particular procedure, a cursor is not the way to obtain the data. First, we have to obtain data for the first son/sern of the ancestor that has yet to be accessed (i.e. USER = 0), then use this sern in order to obtain data for its first son that has yet to be accessed, then use that sern in order to obtain data for its first son. If there is no unaccessed son left, then the procedure must back up a level and continue from there.

Here is the tree that I am using as the example:

Father	Son
A	B1
A	B2
A	B3
B1	B1C1
B1	B1C2
B2	B2C1
B2	B2C2
B3	B3C1
B3	B3C2
B1C1	B1C1D1

The output should be (ignoring A): B1, B1C1, B1C1D1, B1C2, B2, B2C1, B2C2, B3, B3C1, B3C2.

Going back to computer science, turning recursion into iteration requires a table to retain the depth of recursion. This table gets accessed when the procedure has to backtrack, i.e. after the sern B1C1D1 is accessed, the procedure would try to access the next unaccessed son of B1C1, but as there isn't one, the backtracking table is required in order to 'let the procedure know' that it should continue with B1C2. As this sern has no sons, again the procedure has to backtrack in order to know that is required to continue with B2, then the sons of B2, etc.

Let's write a little code that will be the start of the procedure.

LINK STACK4 TO :$.STK;                                              
ERRMSG 1 WHERE :RETVAL <= 0;                                     
LINK STACK2 TO :$.ST2;                                              
ERRMSG 1 WHERE :RETVAL <= 0;                                     
:LINE = 0;                                                          
:LEVEL = 1;                                                         
INSERT INTO STACK2 (ELEMENT, TYPE)                                  
VALUES (:ANCESTOR, 1);                                              
:NODE = :ANCESTOR;                                                  
UPDATE TEST_SERNTREE                                                
SET USER = 0                                                        
WHERE ANCESTOR = :ANCESTOR; 
/********************************/
LABEL 10;                                                           
SELECT SON INTO :SON                                                
FROM TEST_SERNTREE                                                  
WHERE FATHER = :NODE                                                  
AND USER = 0;                                                       
GOTO 20 WHERE :RETVAL <= 0;                                         
INSERT INTO STACK2 (ELEMENT, TYPE)                                  
VALUES (:SON, :LEVEL + 1);                                          
:LINE = :LINE + 1;                                                  
INSERT INTO STACK4 (KEY, INTDATA, INTDATA2)               
VALUES (:LINE, :SON, :LEVEL + 1);                          
UPDATE TEST_SERNTREE                                                
SET USER = SQL.USER                                                 
WHERE SON = :SON;                                                   
:NODE = :SON;                                                       
:LEVEL = :LEVEL + 1;                                                
LOOP 10;
LABEL 20;  

The code prior to label 10 sets everything up. The variable :NODE will hold 'the current device' and initially is the ancestor. The SELECT statement after LABEL 10 gets 'the first unaccessed son' of :NODE into the variable :SON. If there is no such device, then :RETVAL will be 0 and the code will leave this loop and go to label 20. Assuming that there is a son, it will be stored in STACK2 (this table is the backtrack table), then the son is stored in STACK4. Note that this table has a simple incrementing key - this will ensure that the table will hold the data in the hierarchical order as required. Then the actual sern in the real table TEST_SERNTREE has its USER field updated to show that this sern has been accessed*. Finally :NODE is set to the value of :SON, the level is incremented and the loop continues.

Thus, the first time that LABEL 10 is reached, the value of :NODE will be :ANCESTOR (i.e. A). The SELECT statement will return B1; this serial is entered into both STACK2 and STACK4 as well as being marked as used. Finally :NODE is changed from :A to :B1. The second time that LABEL 10 is reached, the SELECT statement will return B1C1. The third time around, the SELECT statement will return B1C1D1. The fourth time around, the SELECT statement will fail as B1C1D1 has no sons (or one could say that there is no tuple in which FATHER = B1C1D1). So execution jumps to LABEL 20, but I'll leave what happens there for another day.

---

* This is not optimal and will be corrected in the next installment.

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.

Using the COUNTRIES table as a parameter

One of my clients likes to use the COUNTRIES table as a parameter to reports. Unfortunately, the COUNTRY field in the CUSTOMERS table is not mandatory, so there can be customers without a defined country.

Running a procedure with this parameter set to a specific country works correctly - customers with that country are displayed. Running the procedure with country set to * returns all the customers that have a defined country. What about those customers without a defined country? Leaving the parameter empty apparently causes the error "String or binary data would be truncated (Error 8152)". I don't understand why this error message should appear.

In the past, I might have suggested 'solutions' such as setting the parameter to be 'not equal to Guadeloupe', in the hope that no existing customer is situated in Guadeloupe (where is Guadeloupe? It's "an overseas department and region of France in the Caribbean").

Yesterday my brain must have been working correctly as I saw a much better solution: define the parameter as type NFILE instead of FILE. Add to the code  this section

LINK COUNTRIES TO :$.COU;
ERRMSG 1 WHERE :RETVAL <= 0;
GOTO 1 FROM COUNTRIES WHERE COUNTRY > 0;
UNLINK COUNTRIES;
LABEL 1;

This means that if the parameter is left empty, the COUNTRIES table will be unlinked and the following query will use the original COUNTRIES table, in which the empty value exists. Indeed, after changing the parameter's type, running the procedure with the COUNTRIES parameter left empty worked perfectly.

An undocumented command - GENMSG

Maybe I'm inattentive* but it seems that I never noticed until a few days ago that there are two son forms to the 'step query' form (that in itself is a son form of Procedure Steps that is a son form of the procedure generator): 'Procedure Messages' and 'General error messages'. Maybe the son form has always been there.

Anyway, today my curiosity was piqued and I started to investigate what data this form displays and how it can be used. Both son forms are based on the EXTMSG table whose primary key is based on two fields, EXEC (the name of the form) and NUM (the message number). It turns out that there are only two general messages, both of which say something like 'An error has occurred; please contact the system manager'. I can't remember at the moment how to get the English version of these messages but that's not too important.

How does one display these messages? Here a little ingenuity is called for. I fired up the WINDBI program, chose 'Queries' then 'Find string' and wrote 'GENMSG' (that's the name of the form) before pressing enter. This useful functionality displays wherever the search string is used, be it a form trigger or a procedure. Unfortunately it doesn't work too well with strings composed of more than one word so one often gets the message back that there are too many results for all to be displayed. Of course normally the results that one wants are those that aren't displayed. Fortunately GENMSG doesn't return that many results. Here's an example of the output

ORDERITEMS           BUF69                GENMSG 1 WHERE :RETVAL <= 0;   

Obviously one uses the GENMSG command instead of WRNMSG (or ERRMSG) when one wants to display one of these messages. To be honest, this isn't very useful as I prefer the error message like 'An error has occurred' to show the name of the procedure or trigger where the error occurred so that I can immediately find the source. Otherwise one has to depend on users giving an accurate answer.

This GENMSG functionality would be useful if one could define one's own general messages instead of having to define them in every procedure. For example, I could define a message with the value 599 and the text '<P1> <P2> <P3>' so that I wouldn't have to define this string every time but simply write GENMSG 599 whenever I want some debugging information. This isn't such a good idea as I suspect that GENMSG is equivalent to ERRMSG, not WRNMSG. But I could use it for my version of error 1 that includes the procedure name. 

The value of EXEC for these strings is 208799, and getting that was slightly different from the usual method. The GENMSG form has a pre-form trigger that I copied into WINDBI in order to get the number.

:GENMSGEXEC = 0;
SELECT EXEC INTO :GENMSGEXEC
FROM EXEC
WHERE ENAME = 'GENMSG'
AND TYPE = 'C'
;

I would have expected the EXEC type to be F, not C (curiously enough, there is an EXEC number where TYPE = 'F' but it doesn't lead to the correct error messages). *As a side effect, knowing the EXEC number allows me to discover when this form was added: during the upgrade to version 23.1. It may or may not be in version 22, as we went straight from v21.1 to v23.1. I do know that my first addition with an EXEC higher than 208,799 was added on 18 April this year, after the upgrade. So I wasn't as unobservant as I thought at the beginning of this blog entry.