Recursive relationship, performance problem

Performance problems with hirarchical structures realized by selfrelationship

The entries in the OBJECTS entity are forming a hirarchical structure as known from the typical employee - manager example. Every object may have a parent object in the same entity. Additional every object may be described by one ore more attributes in ATTRIBUTES.

     +-----------------+                   +-----------------------+
     |OBJECTS          |                   |ATTRIBUTES             |
     +-----------------+               1:m +-----------------------+
     |PK object_id     |-----------------+<|PK     attribute_name  |
     |   object_type   |                   |PK, FK object_id       |
     |FK parent_object |----+              |       attribute_value |
     +-----------------+    |		   +-----------------------+
                   V        |
                   +--------+
                     1:m

Here are the questions to be answered by SQL-Statements:

1. What is the root's object_id for a given node?

   Possibel solution:

	select *
	  from objects o1
	  where parent_object is null
	  and <object_id of given node> in


	(

	select object_id
	  from objects
	  start with object_id = o1.object_id
	  connect by prior object_id = parent_objectid
	);

2. What are the child objects of a certain object_type for a given root object_id?

   Possibel solution:

	select *
	  from objects
	  where object_type = <searched child object type>
	  and object_id in


	(

	select object_id
	  from objects
	  start with object_id = <object_id of node where the search shall start>
	  connect by prior object_id = parent_objectid
	);

3. What are the child objects of a certain object_type which belong to a certain root

   object_id AND which have itself leafs described by a certain attribute and an    attribute value?

   Possibel solution:

	select *
	  from objects o1
	  where o1.object_type = <searched object type>
	  and o1.object_id in


	(					/* dependency tree of given root */


	select o2.object_id
	  from objects o2
	  start with o2.object_id = <object_id of root>
	  connect by prior o2.object_id = o2.parent_objectid
	)
        and exists


	(select *				/* leafs */


	  from objects o3
	  where o3.object_type = <leaf object type>
	  and o3.object_id in
	 (					/* dependency tree of given root */
	 select o4.object_id
	   from objects o4
	   start with o4.object_id = o1.object_id  /* = possible result node = root of leafs */
	   connect by prior o4.object_id = o4.parent_objectid
	 )
	 and exists
	 (select 'x'				/* check the attribute of the leaf */
	    from attributes
	    where object_id = o3.object_id
	    and attribute_name = <searched attribute name>
	    and attribute_value = <searched attribute value>
	 )
	);

These questions are very commonly asked questions for hirarchical structures and the select statements are possible, but not very fast solutions, if OBJECTS contains a lot of entries (up to 1000000).

Does anybody have experiance with this problems or does anybody have sugestions for faster SQL statements?

Thanks for comments and hints

Wolfram Loy
SEKAS GmbH
e-mail loy_at_sekas.de Received on Mon Aug 19 1996 - 00:00:00 CEST