Bill of Materials and Hierarchical Queries – Which Component contains a component that…

My two previous posts discussed presenting data in a tree-like fashion and filtering hierarchical data sets on certain query conditions while still returning a tree-like result set. This post discusses a subject along the same lines.

We have a data model with a “components” table that is linked to itself through an “components relations” intersections table, one that describes instances where a component is part of another component. Note that a component may contain many other components and a component can be part of many components.
Bill of Materials and Hierarchical Queries - Which Component contains a component that... BOM ERD
Instead of component, you may also read ingredient when discussing recipees, subject when discussing a thesaurus or book index, social clustering etc. I ran into the “bill of materials” recently while working on our new Skill Management application, where all skills of the AMIS staff are recorded and maintained. We are talking about some 70 developers with skills in over 600 tools, technologies, roles and versions. Having to select one ‘subject’ or ‘component’ such as Hibernate Release 3 or PL/SQL Collections from the list of 600 items can be a pain. Especially since this list is really organized quite hierarchically. In the above two cases, what you actually select is: Java/J2EE – OO/R and Persistency – Hibernate – Hibernate Release 3 or Oracle – Oracle Database Development – PL/SQL – PL/SQL Collections. Both for maintaining the list of “knowledge components” as for selecting elements from this list, it would be very convenient if we present the list as a tree. Let’s see how to do that.

Using the Connect By query for Bill of Materials

The Oracle CONNECT BY clause is typically used to present data in the form of an hierarchy. Usually the CONNECT BY makes use of a self-referencing foreign key on the table whose records are the nodes in the tree. However, in this particular case the hierarchy is defined across two tables.

We will first combine the two tables in an in-line view. We are selecting all component nodes: every occurrence of a component as child in a relation with another component. To ensure we also select root-nodes – components that only exist in the tree as top-level parent – we use the left outer join.

select cpt.id
,      cpt.name
,      rel.cpt_part_of
from   components cpt
       left outer join
       component_relations rel
       on (cpt.id = rel.cpt_containee)
/

The result of this query is a list of all components – or rather all component nodes – their id and their parent. Note that each component may occur multiple times:

   ID NAME                                               CPT_PART_OF
----- -------------------------------------------------- ----------
  241 Operating Systems
  242 VMS                                                       241
  243 Unix                                                      241
  244 HP-Unix                                                   241
  245 Solaris                                                   241
  246 AIX                                                       241
  247 Windows                                                   241
  248 OS/2                                                      241
  249 Mac OS                                                    241
  251 Oracle Portal                                               4
  251 Oracle Portal                                             341
  251 Oracle Portal                                             332
  251 Oracle Portal                                             258
  252 JetSpeed                                                  332
  253 SQL*Net                                                   202
  254 OCI                                                       202
  255 Oracle Data Cartridge                                     202
  256 Database Tuning
  257 CORBA
  258 Content Management
  259 Vignette                                                  258
....

The CPT_PART_OF can now be seen as the self-referencing foreign key within this result set. Constructing the tree-style result set has become very easy:

with component_nodes as
(select cpt.id
,      cpt.name
,      rel.cpt_part_of
from   components cpt
       left outer join
       component_relations rel
       on (cpt.id = rel.cpt_containee)
)
select name
,      sys_connect_by_path(name,'---') scbp
from   component_nodes
connect
by     prior id = cpt_part_of
start
with   cpt_part_of is null
/

A small subset from the results:

Java/J2EE
-Java/J2EE
Java View Technology
-Java/J2EE-Java View Technology
Java Applets
-Java/J2EE-Java View Technology-Java Applets
Java Web Start
-Java/J2EE-Java View Technology-Java Web Start
ADF JClient
-Java/J2EE-Java View Technology-ADF JClient
Swing/AWT
-Java/J2EE-Java View Technology-Swing/AWT
SWT
-Java/J2EE-Java View Technology-SWT
JSP
-Java/J2EE-Java View Technology-JSP
JSTL
-Java/J2EE-Java View Technology-JSTL
Custom Tag Libraries
-Java/J2EE-Java View Technology-Custom Tag Libraries
Velocity
-Java/J2EE-Java View Technology-Velocity
Java Server Faces (JSF)
-Java/J2EE-Java View Technology-Java Server Faces (JSF)
Java Web Controllers
-Java/J2EE-Java Web Controllers
Struts
-Java/J2EE-Java Web Controllers-Struts
Spring MVC
-Java/J2EE-Java Web Controllers-Spring MVC
...

Finally I will discuss how we can select all components that contain the term ‘java’ or the word ‘sql’ and still present the results in a tree – even though the ancestors of the nodes that satisfy these search conditions may very well be outside the set of selected components. This was discussed at length in a previous post: filtering hierarchical data sets on certain query conditions while still returning a tree-like result set.

What we will do is first select all nodes from our Components-tree. Then we will add a marker column to each node in the tree, indicating whether or not that node satisfies the search conditions. Next we build the components tree again, BOTTOM UP, starting from all marked nodes. This bottom up tree contains all selected Components – we start building the tree on those nodes after all – as well as all their ancestors, since the tree is built from the selected nodes all the way to the root. Finally, we reconstruct a tree from all selected nodes – either because of ancestor-ship or because they directly satisfy our search condition.

with component_nodes as  -- all component nodes anywhere in the tree, including the root level without leafs/children (because of the left outer join)
( with component_nodes as
(select cpt.id
,      cpt.name
,      rel.cpt_part_of
from   components cpt
       left outer join
       component_relations rel
       on (cpt.id = rel.cpt_containee)
)
,    selected_components as  -- all components with a marker column for those that satisfy the search requirement: somewhere in their name appears the string java (case insensitive)
( select cpt.*
  ,      case
         when lower(name) like '%java%'
         then 'X'
         end marker
 from   component_nodes cpt
)
,    tree_nodes as  -- build a tree, bottom up, starting only from the nodes that passed the requirements (marker=X)
( select distinct
         id
  ,      cpt_part_of
  ,      name
  from   selected_components
  connect
  by     prior cpt_part_of = id -- note that the connect by condition is the reverse from what you usually find
  start with marker is not null  --start with the nodes that qualify and work upwards to the root component
)
select lpad(' ', 2+level * 4)||name  Component_Nodes -- given all the nodes in the tree (qualifying nodes as well as their ancestors), now build the tree properly, top to bottom
from   tree_nodes
connect
by     prior id = cpt_part_of    -- cpt_part_if is the reference to the parent node
start  with  cpt_part_of is null -- start from the root nodes; the cpt_part_of parent reference is null obviously
/


COMPONENT_NODES
-------------------------------------------------------------------------
      Oracle
          Oracle Development Tools
              Oracle Forms
                  Forms PJC (Pluggable Java Components
              Oracle Java/J2EE Development
      Web Technologie
          JavaScript
      Programmeer Talen
          JavaScript
          Java
      O/R Mapping
          Javax Persistence (EJB 3.0)
      Java/J2EE
          Java IDE
          Java View Technology
              Java Server Faces (JSF)
              Java Applets
              Java Web Start
          Java Web Controllers
          J2EE APIs
              Javax Persistence (EJB 3.0)
      Portal
          Portlets (Java)
      Java/J2EE Tools and Frameworks

24 rows selected.

One Response

  1. Sam Forisa April 20, 2009