Maintainting Heirarchies in SQL

I've refined my thinking a little about the optimal way to keep track of tasks in a relational database. Here is the newer version:

CREATE TABLE task (
 id BIGSERIAL PRIMARY KEY,
 parentid BIGINT REFERENCES task (id),
 taskname varchar(50) NOT NULL
 CONSTRAINT name_not_empty
 CHECK (taskname <> '')
);
CREATE TABLE leaftask (
 id BIGINT PRIMARY KEY REFERENCES task (id),
 weight INT4 NOT NULL DEFAULT 1000,
 starttime TIMESTAMPTZ,
 endtime TIMESTAMPTZ,
 CONSTRAINT startbeforefinish
 CHECK ((starttime < endtime) or (endtime IS NULL))
);

I want my tasks to follow certain rules:

• All sub-tasks of a given parent task should add up to 100% of the parent task.
• A task can never have exactly one sub-task because - according to the rule above - the subtask would by synonymous with its parent.
• All tasks that have no descendants - and none that don't - should have a corresponding "leaftask" record.
• All tasks must have a final root that has no parent - i.e. no looping back on your descendants.

I want to build structures into the database that will prevent invalid states (as defined by the above rules) from occurring. Today I am going to tackle the problem of a task descending from itself. To prevent that case, I need what in PostgreSQL is called a trigger. I'm getting ahead of myself though. First I need a way to list the descendants of a given task. Since I want it to happen all in the database, I need a stored function.

Stored functions in PostgreSQL can be written in many languages. I'm going to write mine in PL/pgSQL, a sort of SQL-related procedural language, because it is included by default with PostgreSQL. (PL/pgSQL is intentionally similar to Oracle's PL/SQL, if you're an Oracle person.)

CREATE OR REPLACE FUNCTION taskdescendants(parenttaskid bigint, OUT decid bigint)
 RETURNS SETOF bigint AS $fun$
BEGIN
 FOR decid IN SELECT id FROM task WHERE parentid = parenttaskid LOOP
  RETURN NEXT;
  FOR decid IN SELECT * FROM taskdescendants(decid) LOOP
   RETURN NEXT;
  END LOOP;
 END LOOP;
 RETURN;
END;
$fun$ LANGUAGE plpgsql;

This function will return the ids (each as a separate row) of any descendants a given task might have. I can use it in my SQL statements as if it were a table. For example, this will select all tasks descending from task 57:

SELECT decid, taskname FROM taskdescendants(57) INNER JOIN task ON decid = id;

That's all well and good for a generic function, but trigger functions have slightly different requirements. This will check that the new parentid doesn't show up in the list of descendants:

CREATE OR REPLACE FUNCTION taskrecursioncheck() RETURNS trigger AS $fun$
BEGIN
 IF NEW.parentid IN (SELECT decid FROM taskdescendants(NEW.id)) THEN
  RAISE EXCEPTION 'task cannot descend from one of its own descendants';
 END IF;
 IF NEW.parentid = NEW.id THEN
  RAISE EXCEPTION 'task cannot descend from itself';
 END IF;
 RETURN NEW;
END;
$fun$ LANGUAGE plpgsql;

CREATE TRIGGER parent_trap BEFORE UPDATE ON task
 FOR EACH ROW EXECUTE PROCEDURE taskrecursioncheck();

There - now it raises an error on invalid relationships and I got a handy function that my front end can call. Later I will have to figure out some way to ensure my other rules are followed.

Creating a Tree-based Task List in a Relational Database

Things we want:

• tasks
• subtasks
• task owners (responsible for that task)
• task start time
• task end time
• prerequisite tasks

How do we represent these things in a relational database? Tasks are represented as a tree. Only leaf tasks will have owners and start/end times. This is because any non-leaf task will be made up entirely of its subtasks. In other words, when all the subtasks are done, the parent task is done. The start time of a non-leaf task is the earliest start time from among its descendants. Likewise, its end time equals the last end time from among its descendants (null if any are not yet finished).

Note: "bigserial" and "serial" are PostgreSQL abstractions for 8-byte and 4-byte integers that have an auto-incrementing default. They're mostly used for primary keys.

CREATE TABLE task (
    taskid BIGSERIAL NOT NULL PRIMARY KEY,
    parentid BIGINT REFERENCES task(taskid),
    jobid INTEGER NOT NULL REFERENCES job(jobid),
    taskname VARCHAR(200) NOT NULL
);

CREATE TABLE taskleaf (
    taskid BIGINT NOT NULL PRIMARY KEY
      REFERENCES task(taskid),
    employeeid INTEGER NOT NULL
      REFERENCES employee(employeeid),
    starttime TIMESTAMPTZ,
    endtime TIMESTAMPTZ
);

Problems:

Every task has a "jobid" - only the root task really needs this. Make the jobs themselves the root tasks? That wouldn't work in my pre-existing job scheme. Also, if performance was database-bound in my application, I could shift the tree-decoding work to the web server by selecting all the tasks by jobid.

Prevent circular references? I could make a trigger or rule in the database that would check the path back to a root node before allowing a parentid to be assigned. While I am at it, I can check to make sure the parent's "jobid" matches.

I looked at the "adjacency list" method, but I don't think it would work well for my needs.