Database planning - Hierarchical problem - Help needed

[Philippe]

Hi,

I'm actually on a problem i don't manage to resolve.
I want to implement a thing like this in a table :

Albert John
/ \ /
/ \ /
Bert Chuck
/ | \
/ | \
/ | \
/ | \
Donna Eddie Fred
\ /
\ /
\ /
Gilbert

All these links are work relationship between employees...
So for example, Bert superior is Albert.
And Chuck has two superiors : Albert and John

What's in ur point the best method to organize this in a table and do
simple queries on it ?

I tried a modified preorder tree traversal algorithm but since it's
not hierarchical anymore, i don't manage to get it to work... (some
item have two superiors)

Any help welcome... (here or by direct email contact)
philippe...@step.fr

Thnks in advance,
Philippe

[Philippe]

[Neo]

> a problem i don't manage to resolve...

While it can be resolved using traditions dbs, the following script
models the problem and runs some queries using an experimental db.

// Create various property classes
CREATE *age.cls = thing;
CREATE *gender.cls = thing;
CREATE *weight.cls = thing;
CREATE *color.cls = thing;
CREATE *profession.cls = thing;
CREATE *race.cls = thing;
CREATE *party.cls = thing;
CREATE *SS#.cls = thing;

// Create persons each having a different property
CREATE *person.cls = thing;
CREATE *albert.cls = person;
CREATE albert.age = +30;
CREATE *john.cls = person;
CREATE john.gender = +male;
CREATE *bert.cls = person;
CREATE bert.weight = +180;
CREATE *chuck.cls = person;
CREATE chuck.color = +black;
CREATE *donna.cls = person;
CREATE donna.profession = +doctor;
CREATE donna.profession = +engineer;
CREATE *eddie.cls = person;
CREATE eddie.race = +asian;
CREATE *fred.cls = person;
CREATE fred.party = +republican;
CREATE *gilbert.cls = person;
CREATE gilbert.SS# = +333-22-4444;

// Create verbs for hierarchy
CREATE *boss.cls = verb;
CREATE boss.vbType = kr;
CREATE *employee.cls = verb;
CREATE employee.vbType = cr;
CREATE boss.opposite = employee;

// Create hierarchy
CREATE albert.employee = bert;
CREATE albert.employee = chuck;

CREATE john.employee = chuck;

CREATE chuck.employee = donna;
CREATE chuck.employee = eddie;
CREATE chuck.employee = fred;

CREATE eddie.employee = gilbert;
CREATE fred.employee = gilbert;

// Queries:
// Find person whose boss is eddie and fred.
// Finds gilbert.
SELECT %.cls=person & %.boss=eddie & %.boss=fred;

// Find person whose boss's boss is albert & john
// and has employee gilbert.
// Finds eddie and fred.
SELECT %.boss=(%.boss=albert) & %.boss=(%.boss=john) &
%.employee=gilbert;

// Find person whose is asian and has a boss whose boss is 30.
// Finds eddie.
SELECT %.cls=person & %.race=asian & %.boss=(%.boss=(%.age=30));

// Find person who is doc and eng,
// whose boss is someone whose employee is republican.
// Finds donna.
SELECT %.cls=person & %.profession=doctor & %.profession=engineer &
%.boss=(%.employee=(%.party=republican));

The reason the above works is because XDb2 is not based on theory. It
uses random logic and an improbability drive interface directly to
hardware bits within CPU's secondary cache.

[Leandro Guimarães Faria Corsetti Dutra]

Em Mon, 29 Nov 2004 03:50:42 -0800, Philippe escreveu:

> All these links are work relationship between employees... So for example,
> Bert superior is Albert. And Chuck has two superiors : Albert and John

CREATE DOMAIN emp_id AS NUMBER;
CREATE TABLE organogram (manager emp_id, employee emp_id);

--
Leandro Guimarães Faria Corcete Dutra <lea...@dutra.fastmail.fm>
Maringá, PR, BRASIL +55 (44) 3025 6253
http://br.geocities.com./lgcdutra/ +55 (44) 8803 1729
Soli Deo Gloria! +55 (11) 9406 7191

[Lennart Jonsson]

philippe...@step.fr (Philippe) wrote in message news:<ee069cd0.04112...@posting.google.com>...

> Hi,
>
> I'm actually on a problem i don't manage to resolve.
> I want to implement a thing like this in a table :
>
> Albert John
> / \ /
> / \ /
> Bert Chuck
> / | \
> / | \
> / | \
> / | \
> Donna Eddie Fred
> \ /
> \ /
> \ /
> Gilbert
>
>
>
> All these links are work relationship between employees...
> So for example, Bert superior is Albert.
> And Chuck has two superiors : Albert and John
>
> What's in ur point the best method to organize this in a table and do
> simple queries on it ?
>
> I tried a modified preorder tree traversal algorithm but since it's
> not hierarchical anymore, i don't manage to get it to work... (some
> item have two superiors)
>

Representing such graphs in sql is a tough task. Here is one article
describing some of the problems youre facing:

Maintaining the transitive closure of graphs in SQL.
Guozhu Dong, Leonid Libkin, Jianwen Su and Limsoon Wong.
Int. Journal of Information Technology, 5 (1999), 46-78.

You can find an electronic version on the page

http://cm.bell-labs.com/who/libkin/publ.html

If you db supports recursion you can try that, but watch out for
cycles

HTH
/Lennart

[...]

[--CELKO--]

0) I have a book on TREES & HIERARCHIES IN SQL you can get at
www.amazon.com. There is no French translation yet, tho.

1) You can use an Adjacency list which is made of pairs of (boss,
employee). you will have to work with cursors.

2) You can use a Path enumerations model which is made of strings that
concatenate the keys into one string. The paths to Gilbert would be
('albert+chuck+eddie+gilbert')
('john+chuck+eddie+gilbert')
('albert+chuck+fred+gilbert')
('john+chuck+fred+gilbert')

I have not played with is a newer model that would express the paths
by a single string with opertors inside it like
this('(albert|john)+chuck+(eddie|fred)+gilbert'). The | means "or"
and that they are at the same level. The + means "followed by" . This
should model a lattice structure without directed cycles. I have no
idea how to write code for a query yet. I have no idea how to handle
a cycle.

[Jan]

this example works on Oracle 10g (should work also on Oracle 9i):

-- Creating some demo tables:

CREATE TABLE PERSONS (
ID NUMBER,
NAME VARCHAR2(20),
PRIMARY KEY (ID));

CREATE TABLE RELATIONS (
PARENT_ID NUMBER,
CHILD_ID NUMBER);

-- Creating some demo data as in your example:

INSERT INTO PERSONS (ID,NAME) VALUES (1,'Chuck');
INSERT INTO PERSONS (ID,NAME) VALUES (2,'John');
INSERT INTO PERSONS (ID,NAME) VALUES (3,'Albert');
INSERT INTO PERSONS (ID,NAME) VALUES (4,'Bert');
INSERT INTO PERSONS (ID,NAME) VALUES (5,'Donna');
INSERT INTO PERSONS (ID,NAME) VALUES (6,'Eddie');
INSERT INTO PERSONS (ID,NAME) VALUES (7,'Fred');
INSERT INTO PERSONS (ID,NAME) VALUES (8,'Gilbert');
INSERT INTO RELATIONS (PARENT_ID,CHILD_ID) VALUES (1,2);
INSERT INTO RELATIONS (PARENT_ID,CHILD_ID) VALUES (1,3);
INSERT INTO RELATIONS (PARENT_ID,CHILD_ID) VALUES (1,5);
INSERT INTO RELATIONS (PARENT_ID,CHILD_ID) VALUES (1,6);
INSERT INTO RELATIONS (PARENT_ID,CHILD_ID) VALUES (1,7);
INSERT INTO RELATIONS (PARENT_ID,CHILD_ID) VALUES (3,4);
INSERT INTO RELATIONS (PARENT_ID,CHILD_ID) VALUES (6,8);
INSERT INTO RELATIONS (PARENT_ID,CHILD_ID) VALUES (7,8);
COMMIT;

-- And then this SELECT will return the following result:

SELECT SYS_CONNECT_BY_PATH(pp.name, '/')||'/'
||(SELECT pc.name FROM PERSONS pc WHERE pc.id=r.child_id)
FROM RELATIONS r,
PERSONS pp
WHERE pp.id=r.parent_id
CONNECT BY PRIOR child_id = parent_id;

----------------
/Chuck/John
/Chuck/Albert
/Chuck/Albert/Bert
/Chuck/Donna
/Chuck/Eddie
/Chuck/Eddie/Gilbert
/Chuck/Fred
/Chuck/Fred/Gilbert
/Albert/Bert
/Eddie/Gilbert
/Fred/Gilbert
-----------------

Regards, Jan

philippe...@step.fr (Philippe) wrote in message news:<ee069cd0.04112...@posting.google.com>...