XQuery/Validating a hierarchy

Whilst schema validation can check for some aspects of model validity, business rules are often more complex than is expressible in XML schema. XQuery is a powerful language for describing more complex rules.

One such rule is that a relationship should define a tree structure,for example, the relationship between an employee and her manager.

Consider the following set of employees:

<company>
  <emp>
      <name>Fred</name>
      <mgr>Bill</mgr>
      </emp>
    <emp>
        <name>Joe</name>
        <mgr>Bill</mgr>
    </emp>
    <emp>
        <name>Alice</name>
        <mgr>Joe</mgr>
    </emp>
    <emp>
        <name>Bill</name>
     </emp>
</company>

The criteria for a valid hierarchy are:

1. one root (the boss);
2. every employee has at most one manager;
3. every employee reports finally to the boss;
4. there are no cycles

In XQuery we can define the management hierarchy from the boss down to an employee as :

declare function local:management($emp as element(emp) ,
       $hierarchy as element(emp)* ) as element(emp)*  {
     if ($emp = $hierarchy )  (: cycle detected :)
     then ()
     else 
       let $mgr :=  $emp/../emp[name=$emp/mgr]
       return
          if (count($mgr) > 1)  
          then ()  
          else
              if (empty ($mgr))  (: reached the root :)
              then ($emp,$hierarchy)
              else local:management($mgr, ($emp,$hierarchy))
};

The function is initially called as

 local:managment($emp,())

The hierarchy is built up as a parameter to allow cycles to be detected.

Finally, the condition for the management structure to be a tree is

declare function local:management-is-tree($company)) {
    let $boss := $company/emp[empty(mgr)]
    return 
       count($boss) = 1
            and
      (every $emp in $company/emp
          satisfies $boss = local:management($emp,())[1]
      )
};