<?xml version='1.0' ?>
<!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook XML V4.4//EN"
               "http://www.oasis-open.org/docbook/xml/4.4/docbookx.dtd" [
<!ENTITY % myvars SYSTEM "../variables.ent">
%myvars;
]>
<sect1 id="permissions-tediously-explained" xreflabel="OpenACS Permissions Tediously Explained"> 
  <title>OpenACS Permissions Tediously Explained</title>
  <para>
    by Vadim Nasardinov. Modified and converted to Docbook XML by Roberto Mello
  </para>
  
  <para>The code has been modified since this document was written so it is now out of date.  See <ulink url="http://openacs.org/forums/message-view?message_id=121807">this forum thread</ulink>.</para>

  <sect2 id="permissions-tedious-overview">

    <title>Permissions Overview</title>
   <para><emphasis role="strong">Who
   (<computeroutput>grantee_id</computeroutput>) can do what
   (<computeroutput>privilege</computeroutput>) on which object
   (<computeroutput>object_id</computeroutput>).
   </emphasis></para>
    <para>
      The general permissions system has a flexible (and relatively complex) data model in OpenACS.
      Developers who have not had the time to learn the internals of the data model
      may end up writing seemingly correct code that crashes their system in
      weird ways. This writeup is the result of my running into such a piece
      of code and trying to understand exactly what went wrong.
      It is geared towards developers who understand the general permissions
      system to the extent that is described in the 
      <ulink url="permissions.html">
      Groups, Context, Permissions documentation</ulink>,
      but who have not had the opportunity to take a long, careful look at the
      system internals.
    </para>

    <para>
      In OpenACS, most of the interesting tables are expected to extend (subtype)
      the <computeroutput>acs_objects</computeroutput> table, i.e. they are expected to have an integer
      primary key column that references the <computeroutput>object_id</computeroutput> column of
      <computeroutput>acs_objects</computeroutput>. 
    </para>

    <programlisting id="acs_objects" xreflabel="acs_objects">
create table <emphasis role="bold">acs_objects</emphasis> (
      object_id             integer
          not null
          constraint acs_objects_pk primary key,
      object_type
          not null
          constraint acs_objects_object_type_fk references acs_object_types (object_type),
      context_id
          constraint acs_objects_context_id_fk references acs_objects(object_id),
      security_inherit_p	  char(1) default 't'
          not null,
      constraint acs_objects_sec_inherit_p_ck
          check (security_inherit_p in ('t', 'f')),
      creation_user         integer,
      creation_date         date default sysdate not null,
      creation_ip           varchar2(50),
      last_modified         date default sysdate not null,
      modifying_user        integer,
      modifying_ip          varchar2(50),
      constraint acs_objects_context_object_un
          unique (context_id, object_id) disable
);
    </programlisting>

    <para>
      This means that items that want to use the features of the
      OpenACS object system needs to have an entry in the <computeroutput>acs_objects</computeroutput>. This
      allows developers to define relationships between any two entities <emphasis>A</emphasis>
      and <emphasis>B</emphasis> by defining a relationship between their corresponding entries
      in the <computeroutput>acs_objects</computeroutput> table.  One of the applications of this
      powerful capability is the general permissions system. 
    </para>

    <para>
      At the heart of the permission system are two tables: <computeroutput>acs_privileges</computeroutput>
      and <computeroutput>acs_permissions</computeroutput>. 
    </para>


    <programlisting id="acs_privileges" xreflabel="acs_privileges">
  create table <emphasis role="bold">acs_privileges</emphasis> (
      privilege           varchar2(100) not null
          constraint acs_privileges_pk primary key,
      pretty_name         varchar2(100),
      pretty_plural       varchar2(100)
  );
    </programlisting>

    <programlisting id="acs_permissions" xreflabel="acs_permissions">
  create table <emphasis role="bold">acs_permissions</emphasis> (
      object_id
          not null
          constraint acs_permissions_on_what_id_fk references <xref linkend="acs_objects"/> (object_id),
      grantee_id
          not null
          constraint acs_permissions_grantee_id_fk references <xref linkend="tedious-parties"/> (party_id),
      privilege
          not null
          constraint acs_permissions_priv_fk references <xref linkend="acs_privileges"/> (privilege),
      constraint acs_permissions_pk
          primary key (object_id, grantee_id, privilege)
  );
    </programlisting>

    <para>
      The <computeroutput>acs_privileges</computeroutput> table stores 
      named privileges like <emphasis>read</emphasis>, 
      <emphasis>write</emphasis>, <emphasis>delete</emphasis>, <emphasis>create</emphasis>, and 
      <emphasis>admin</emphasis>. The <computeroutput>acs_permissions</computeroutput>
      table stores assertions of the form: 
    </para>

    <para>
      Who (<computeroutput>grantee_id</computeroutput>) can do what (<computeroutput>privilege</computeroutput>) 
      on which object (<computeroutput>object_id</computeroutput>).
    </para>

    <para>
      The micromanaging approach to system security would be to require application developers
      to store permission information explicitly about every object, i.e. if the system has 100,000 and 1,000 users
      who have the <emphasis>read</emphasis> privilege on all objects, then we would need to store 100,000,000
      entries of the form: 
    </para>

    <informaltable frame="all">
      <tgroup cols="3" align="center" colsep="1" rowsep="1">
        <colspec colname="c1"/>
        <colspec colname="c2"/>
        <colspec colname="c3"/>
        <thead>
          <row>
            <entry>object_id</entry>
            <entry>grantee_id</entry>
	    <entry>privilege</entry>
	  </row>
	</thead>
	<tbody>
          <row>
	     <entry>object_id_1</entry>
             <entry>user_id_1</entry>
             <entry>'read'</entry>
          </row>
          <row>
             <entry>object_id_1</entry>
             <entry>user_id_2</entry>
	     <entry>'read'</entry>
	  </row>
          <row>
             <entry namest="c1" nameend="c3" align="center">...</entry>
          </row>
          <row>
             <entry>object_id_1</entry>
             <entry>user_id_n</entry>
             <entry>'read'</entry>
          </row>
          <row>
             <entry>object_id_2</entry>
             <entry>user_id_1</entry>
             <entry>'read'</entry>
          </row>
          <row>
             <entry>object_id_2</entry>
             <entry>user_id_2</entry>
             <entry>'read'</entry>
          </row>
          <row>
             <entry namest="c1" nameend="c3" align="center">...</entry>
          </row>
          <row>
             <entry>object_id_2</entry>
             <entry>user_id_n</entry>
             <entry>'read'</entry>
          </row>
          <row>
             <entry namest="c1" nameend="c3" align="center">...</entry>
          </row>
          <row>
             <entry namest="c1" nameend="c3" align="center">...</entry>
          </row>
          <row>
             <entry>object_id_m</entry>
             <entry>user_id_1</entry>
             <entry>'read'</entry>
          </row>
          <row>
             <entry>object_id_m</entry>
             <entry>user_id_2</entry>
             <entry>'read'</entry>
          </row>
          <row>
             <entry namest="c1" nameend="c3" align="center">...</entry>
          </row>
          <row>
             <entry>object_id_m</entry>
             <entry>user_id_n</entry>
             <entry>'read'</entry>
          </row>
        </tbody>
      </tgroup>
    </informaltable>

    <para>
      Although quite feasible, this approach fails to take advantage of the fact
      that objects in the system are commonly organized hierarchally,
      and permissions usually follow the hierarchical structure, so that if user
      <emphasis>X</emphasis> has the <emphasis>read</emphasis> privilege on object <emphasis>A</emphasis>, she typically
      also has the <emphasis>read</emphasis> privilege on all objects attached under <emphasis>A</emphasis>.
    </para>
    <para>
      The general permission system takes advantage
      of the hierarchical organization of objects to unburden developers of the
      necessity to explicitly maintain security information for every single
      object.  There are three kinds of hierarchies involved.
      These are discussed in the following sections.
    </para>
  </sect2>

  <sect2 id="permissions-tedious-context-hierarchy">
    <title>Context Hierarchy</title>

    <para>
      Suppose objects <emphasis>A</emphasis>, <emphasis>B</emphasis>, ..., 
      and <emphasis>F</emphasis> form the following hierarchy. 
    </para>

    <table frame="all">
      <title>Context Hierarchy Example</title>
      <tgroup cols="3" align="center" colsep="1" rowsep="1">
        <colspec colname="c1"/>
        <colspec colname="c2"/>
        <colspec colname="c3"/>
        <tbody>
	  <row>
            <entry namest="c1" nameend="c3">
	      <emphasis role="bold">A</emphasis>
	      <para>
  	        <computeroutput>object_id=10</computeroutput>
              </para>
	    </entry>
	  </row>
          <row>
            <entry namest="c1" nameend="c2">
	      <emphasis role="bold">B</emphasis>
	      <para>
  	        <computeroutput>object_id=20</computeroutput>
              </para>
	    </entry>
            <entry>
	      <emphasis role="bold">C</emphasis>
	      <para>
  	        <computeroutput>object_id=30</computeroutput>
              </para>
	    </entry>
          </row>
	  <row>
            <entry>
	      <emphasis role="bold">D</emphasis>
	      <para>
  	        <computeroutput>object_id=40</computeroutput>
              </para>
	    </entry>
            <entry>
	      <emphasis role="bold">E</emphasis>
	      <para>
  	        <computeroutput>object_id=50</computeroutput>
              </para>
	    </entry>
            <entry>
	      <emphasis role="bold">F</emphasis>
	      <para>
  	        <computeroutput>object_id=60</computeroutput>
              </para>
	    </entry>
          </row>
        </tbody>
      </tgroup>
    </table>
    
    <para>
      This can be represented in the 
      <xref linkend="acs_objects"/> table
      by the following entries: 
    </para>

    <table frame="all">
      <title>acs_objects example data</title>
      <tgroup cols="2" align="center" colsep="1" rowsep="1">
        <colspec colname="c1"/>
        <colspec colname="c2"/>
        <thead>
          <row>
            <entry>object_id</entry>
            <entry>context_id</entry>
	  </row>
	</thead>
	<tbody>
          <row>
	     <entry>20</entry>
             <entry>10</entry>
          </row>
          <row>
	     <entry>30</entry>
             <entry>10</entry>
          </row>
          <row>
	     <entry>40</entry>
             <entry>20</entry>
          </row>
          <row>
	     <entry>50</entry>
             <entry>20</entry>
          </row>
          <row>
	     <entry>60</entry>
             <entry>30</entry>
          </row>
        </tbody>
      </tgroup>
    </table>
    
    <para>
      The first entry tells us that object 20 is the descendant of object 10, and
      the third entry shows that object 40 is the descendant of object 20. By
      running a <ulink url="http://www.oradoc.com/ora817/server.817/a85397/expressi.htm#1023748">CONNECT BY</ulink> query,
      we can compute that object 40 is the second-generation descendant of object 10.
      With this in mind, if we want to record the fact that user Joe has the <emphasis>read</emphasis> privilege on objects
      <emphasis>A</emphasis>, ..., <emphasis>F</emphasis>, we only need to record one entry in the
      <xref linkend="acs_permissions"/> table. 
    </para>

    <informaltable frame="all">
      <tgroup cols="3" align="center" colsep="1" rowsep="1">
        <colspec colname="c1"/>
        <colspec colname="c2"/>
        <colspec colname="c3"/>
        <thead>
          <row>
            <entry>object</entry>
            <entry>grantee</entry>
            <entry>privilege</entry>
	  </row>
	</thead>
	<tbody>
          <row>
	     <entry align="center">A</entry>
	     <entry align="center">Joe</entry>
	     <entry align="center">read</entry>
          </row>
        </tbody>
      </tgroup>
    </informaltable>

    <para>
      The fact that Joe can also read <emphasis>B</emphasis>, <emphasis>C</emphasis>, 
      ..., and <emphasis>F</emphasis> can be derived by ascertaining that these objects 
      are children of <emphasis>A</emphasis> by traversing the context hierarchy.
      As it turns out, hierarchical queries are expensive.  As
      Rafael Schloming put it so aptly, <emphasis>Oracle can't deal with hierarchies for shit.</emphasis> 
    </para>

    <para>
      One way to solve this problem is to cache a flattened view of the context tree like so: 
    </para>

    <informaltable frame="all">
      <tgroup cols="3" align="center" colsep="1" rowsep="1">
        <colspec colname="c1"/>
        <colspec colname="c2"/>
        <colspec colname="c3"/>
        <thead>
          <row>
            <entry>object</entry>
            <entry>ancestor</entry>
            <entry>n_generations</entry>
	  </row>
	</thead>
	<tbody>
          <row>
	     <entry align="center">A</entry>
	     <entry align="center">A</entry>
	     <entry align="center">0</entry>
          </row>
          <row>
	     <entry align="center">B</entry>
	     <entry align="center">B</entry>
	     <entry align="center">0</entry>
          </row>
          <row>
	     <entry align="center">B</entry>
	     <entry align="center">A</entry>
	     <entry align="center">1</entry>
          </row>
          <row>
	     <entry align="center">C</entry>
	     <entry align="center">C</entry>
	     <entry align="center">0</entry>
          </row>
          <row>
	     <entry align="center">C</entry>
	     <entry align="center">A</entry>
	     <entry align="center">1</entry>
          </row>
          <row>
	     <entry align="center">D</entry>
	     <entry align="center">D</entry>
	     <entry align="center">0</entry>
          </row>
          <row>
	     <entry align="center">D</entry>
	     <entry align="center">B</entry>
	     <entry align="center">1</entry>
          </row>
          <row>
	     <entry align="center">D</entry>
	     <entry align="center">A</entry>
	     <entry align="center">2</entry>
          </row>
          <row>
	     <entry align="center">E</entry>
	     <entry align="center">E</entry>
	     <entry align="center">0</entry>
          </row>
          <row>
	     <entry align="center">E</entry>
	     <entry align="center">B</entry>
	     <entry align="center">1</entry>
          </row>
          <row>
	     <entry align="center">E</entry>
	     <entry align="center">A</entry>
	     <entry align="center">2</entry>
          </row>
          <row>
	     <entry align="center">F</entry>
	     <entry align="center">F</entry>
	     <entry align="center">0</entry>
          </row>
          <row>
	     <entry align="center">F</entry>
	     <entry align="center">C</entry>
	     <entry align="center">1</entry>
          </row>
          <row>
	     <entry align="center">F</entry>
	     <entry align="center">A</entry>
	     <entry align="center">2</entry>
          </row>
        </tbody>
      </tgroup>
    </informaltable>

    <para>
      Note that the number of entries in the flattened view grows exponentially with
      respect to the depth of the context tree.  For instance, if you have a fully
      populated binary tree with a depth of <emphasis>n</emphasis>, then the number of entries
      in its flattened view is
    </para>
    
    <para>
      1 + 2*2 + 3*4 + 4*8 + 5*16 + ... + (n+1)*2<superscript>n</superscript> = n*2<superscript>n+1</superscript> + 1</para>

    <para>
      Despite its potentially great storage costs, maintaining a
      flattened representation of the context tree is exactly what OpenACS
      does.  The flattened context tree is stored in the
      <computeroutput>acs_object_context_index</computeroutput> table.
    </para>
   
    <programlisting id="acs_object_context_index" xreflabel="acs_object_context_index">
  create table <emphasis role="bold">acs_object_context_index</emphasis> (
      object_id
          not null
          constraint acs_obj_context_idx_obj_id_fk references <xref linkend="acs_objects"/> (object_id),
      ancestor_id
          not null
          constraint acs_obj_context_idx_anc_id_fk references <xref linkend="acs_objects"/> (object_id),
      n_generations	    integer
          not null
          constraint acs_obj_context_idx_n_gen_ck check (n_generations <markup>></markup>= 0),
      constraint acs_object_context_index_pk
          primary key (object_id, ancestor_id)
  ) organization index;
    </programlisting>

    <para>
      A few things to note about this table are these.  Number one, it is
      an <ulink url="http://www.oradoc.com/ora817/server.817/a85397/statem3e.htm#2061922">index-organized
      table</ulink>, which means it is substantially optimized for access by primary key.
      Number two, as the above computations suggest, the size of the table
      grows <emphasis role="strong">polynomially</emphasis>
      with respect to the average number of descendants that an object
      has, and <emphasis role="strong">exponentially</emphasis>
      with respect to the depth of the context tree. 
    </para>

    <para>
      The <computeroutput>acs_object_context_index</computeroutput> is kept in sync with the
      <xref linkend="acs_objects"/>
      table by triggers like this: 
    </para>

    <programlisting>
create or replace trigger acs_objects_context_id_in_tr
after insert on <xref linkend="acs_objects"/>
for each row
begin
    insert into <xref linkend="acs_object_context_index"/>
     (object_id, ancestor_id, n_generations)
    values
     (:new.object_id, :new.object_id, 0);

    if :new.context_id is not null and :new.security_inherit_p = 't' then
      insert into <xref linkend="acs_object_context_index"/>
       (object_id, ancestor_id,
        n_generations)
      select
       :new.object_id as object_id, ancestor_id,
       n_generations + 1 as n_generations
      from <xref linkend="acs_object_context_index"/>
      where object_id = :new.context_id;
    elsif :new.object_id != 0 then
      -- 0 is the id of the security context root object
      insert into <xref linkend="acs_object_context_index"/>
       (object_id, ancestor_id, n_generations)
      values
       (:new.object_id, 0, 1);
    end if;
end;
</programlisting>

    <para>
      One final note about 
      <xref linkend="acs_objects"/>. By setting
      an object's <computeroutput>security_inherit_p</computeroutput> column to 'f', you can stop permissions
      from cascading down the context tree. In the following example, Joe does not have
      the read permissions on <emphasis>C</emphasis> and <emphasis>F</emphasis>. 
    </para>

    <informaltable frame="all">
      <tgroup cols="3" align="center" colsep="1" rowsep="1">
        <colspec colname="c1"/>
        <colspec colname="c2"/>
        <colspec colname="c3"/>
        <tbody>
	  <row>
            <entry namest="c1" nameend="c3">
	      <literallayout>
<emphasis role="bold">A</emphasis>
<computeroutput>object_id=10</computeroutput>
<emphasis>readable by Joe</emphasis>
	      </literallayout>
	    </entry>
	  </row>
          <row>
            <entry namest="c1" nameend="c2">
	      <literallayout>
<emphasis role="bold">B</emphasis>
<computeroutput>object_id=20</computeroutput>
<emphasis>readable by Joe</emphasis>
              </literallayout>
	    </entry>
            <entry>
	      <literallayout>
<emphasis role="bold">C</emphasis>
<computeroutput>object_id=30</computeroutput>
security_inherit_p = 'f'
<emphasis>not readable by Joe</emphasis>
	      </literallayout>
	    </entry>
          </row>
	  <row>
            <entry>
	      <literallayout>
<emphasis role="bold">D</emphasis>
<computeroutput>object_id=40</computeroutput>
	      </literallayout>
	    </entry>
            <entry>
	      <literallayout>
<emphasis role="bold">E</emphasis>
<computeroutput>object_id=50</computeroutput>
	      </literallayout>
	    </entry>
            <entry>
	      <literallayout>
<emphasis role="bold">F</emphasis>
<computeroutput>object_id=60</computeroutput>
security_inherit_p = 'f'
<emphasis>not readable by Joe</emphasis>
	      </literallayout>
	    </entry>
          </row>
        </tbody>
      </tgroup>
    </informaltable>
    
  </sect2>

  <sect2 id="permissions-tedious-privilege-hierarchy">
    <title>Privilege Hierarchy</title>

    <para>
      Privileges are also organized hierarchically.  In addition to
      the five main system privileges defined in the ACS Kernel data
      model, application developers may define their own. Note,
      however, that this is no longer recommended practice. 
    </para>

    <para>
      By defining parent-child relationship between privileges, the
      OpenACS data model makes it easier for developers to manage
      permissions.  Instead of granting a user explicit
      <emphasis>read</emphasis>, <emphasis>write</emphasis>,
      <emphasis>delete</emphasis>, and <emphasis>create</emphasis>
      privileges on an object, it is sufficient to grant the user the
      <emphasis>admin</emphasis> privilege to which the first four
      privileges are tied. Privileges are structured as follows.
    </para>

    <informaltable frame="all">
      <tgroup cols="4" align="center" colsep="1" rowsep="1">
        <colspec colname="c1"/>
        <colspec colname="c2"/>
        <colspec colname="c3"/>
        <colspec colname="c4"/>
        <tbody>
	  <row>
            <entry namest="c1" nameend="c4">admin</entry>
	  </row>
	  <row>
            <entry namest="c1" nameend="c1">create</entry>
            <entry namest="c2" nameend="c2">delete</entry>
            <entry namest="c3" nameend="c3">read</entry>
            <entry namest="c4" nameend="c4">write</entry>
	  </row>
	</tbody>
       </tgroup>
     </informaltable>

    <para>
      Note that <computeroutput>admin</computeroutput> privileges are
      greater than read, write, create and delete privileges combined.
       Issuing someone read, write, create and delete privileges will
      not result in the person getting
      <computeroutput>admin</computeroutput> privileges.</para>
    <para>The parent-child relationship between privileges is represented in
      the <computeroutput>acs_privilege_hierarchy</computeroutput> table: 
    </para>


    <programlisting id="acs_privilege_hierarchy" xreflabel="acs_privilege_hierarchy">
  create table <emphasis role="bold">acs_privilege_hierarchy</emphasis> (
      privilege
          not null
          constraint acs_priv_hier_priv_fk references <xref linkend="acs_privileges"/> (privilege),
      child_privilege
          not null
          constraint acs_priv_hier_child_priv_fk references <xref linkend="acs_privileges"/> (privilege),
      constraint acs_privilege_hierarchy_pk
          primary key (privilege, child_privilege)
  );
    </programlisting>

    <para>
      As in the case of the context hierarchy, it is convenient to have a flattened representation
      of this hierarchal structure.  This is accomplished by defining the following view. 
    </para>

    <programlisting id="acs_privilege_descendant_map" xreflabel="acs_privilege_descendant_map">
  create or replace view <emphasis role="bold">acs_privilege_descendant_map</emphasis>
  as
  select
    p1.privilege,
    p2.privilege as descendant
  from
    <xref linkend="acs_privileges"/> p1,
    <xref linkend="acs_privileges"/> p2
  where
    p2.privilege in 
      (select
         child_privilege
       from
         <xref linkend="acs_privilege_hierarchy"/>
       start with
         privilege = p1.privilege
       connect by
         prior child_privilege = privilege
      )
    or p2.privilege = p1.privilege;
    </programlisting>

    <para>
      As the number of different privileges in the system is expected to be
      reasonably small, there is no pressing need to cache the flattened ansector-descendant
      view of the privilege hierarchy in a specially maintained table like
      it is done in the case of the context hierarchy.
    </para>
    
  </sect2>

  <sect2 id="permissions-tedious-party-hierarchy">
    <title>Party Hierarchy</title>

    <para>
      Now for the third hierarchy playing a promiment role in the permission system. The party
      data model is set up as follows. 
    </para>

    <informaltable frame="all">
      <tgroup cols="2" align="center" colsep="1" rowsep="1">
        <colspec colname="c1"/>
        <colspec colname="c2"/>
        <tbody>
	  <row>
	    <entry namest="c1" nameend="c2">
	      <xref linkend="tedious-parties"/>
	    </entry>
	  </row>
	  <row>
            <entry>
	      <xref linkend="persons"/>
	    </entry>
	    <entry morerows="1" valign="top">
	      <xref linkend="groups"/>
	    </entry>
	  </row>
	  <row>
	    <entry>
              <xref linkend="users"/>
	    </entry>
	  </row>
	</tbody>
      </tgroup>
    </informaltable>

    <programlisting id="tedious-parties" xreflabel="parties">
  create table <emphasis role="bold">parties</emphasis> (
      party_id
          not null
          constraint parties_party_id_fk references <xref linkend="acs_objects"/> (object_id)
          constraint parties_pk primary key,
      email               varchar2(100)
          constraint parties_email_un unique,
      url                 varchar2(200)
  );
    </programlisting>
 
    <programlisting id="persons" xreflabel="persons">
  create table <emphasis role="bold">persons</emphasis> (
      person_id
          not null
          constraint persons_person_id_fk references <xref linkend="tedious-parties"/> (party_id)
          constraint persons_pk primary key,
      first_names          varchar2(100)
          not null,
      last_name            varchar2(100)
          not null
  );
    </programlisting>

    <programlisting id="users" xreflabel="users">
  create table <emphasis role="bold">users</emphasis> (
      user_id
          not null
          constraint users_user_id_fk references <xref linkend="persons"/> (person_id)
          constraint users_pk primary key,
      password        char(40),
      -- other attributes
  );
    </programlisting>

    <programlisting id="groups" xreflabel="groups"> 
  create table <emphasis role="bold">groups</emphasis> (
      group_id
          not null
          constraint groups_group_id_fk references <xref linkend="tedious-parties"/> (party_id)
          constraint groups_pk primary key,
      group_name           varchar2(100) not null
  );
    </programlisting>

    <para>
      Recall that the <computeroutput>grantee_id</computeroutput> column of the
      <xref linkend="acs_permissions"/> table references 
      <computeroutput>parties.party_id</computeroutput>.
      This means that you can grant a privilege on an object to a party, person, user, or group.
      Groups represent aggregations of parties. The most common scenario that you are likely
      to encounter is a group that is a collection of users, although you could also
      have collections of persons, groups, parties, or any mix thereof.
    </para>
    
    <para>
      Given that the most common use of groups is to partition users, how do you
      build groups?  One way is to grant membership explicitly. If you have
      a group named <emphasis>Pranksters</emphasis>, you can assign membership to Pete,
      Poly, and Penelope. The fact that these users are members of the
      <emphasis>Pranksters</emphasis> group will be recorded in the
      <computeroutput>membership_rels</computeroutput> and <computeroutput>acs_rels</computeroutput> tables: 
    </para>
      
    <programlisting id="acs_rels" xreflabel="acs_rels">
  create table <emphasis role="bold">acs_rels</emphasis> (
      rel_id
          not null
          constraint acs_rels_rel_id_fk references <xref linkend="acs_objects"/> (object_id)
          constraint acs_rels_pk primary key,
      rel_type
          not null
          constraint acs_rels_rel_type_fk references acs_rel_types (rel_type),
      object_id_one
          not null
          constraint acs_object_rels_one_fk references <xref linkend="acs_objects"/> (object_id),
      object_id_two
          not null
          constraint acs_object_rels_two_fk references <xref linkend="acs_objects"/> (object_id),
      constraint acs_object_rels_un
          unique (rel_type, object_id_one, object_id_two)
  );
    </programlisting>

    <programlisting id="membership_rels" xreflabel="membership_rels">
  create table <emphasis role="bold">membership_rels</emphasis> (
      rel_id
          constraint membership_rel_rel_id_fk references <xref linkend="acs_rels"/> (rel_id)
          constraint membership_rel_rel_id_pk primary key,
      -- null means waiting for admin approval
      member_state         varchar2(20)
          constraint membership_rel_mem_ck
           check (member_state in ('approved', 'banned', 'rejected', 'deleted'))
  );
    </programlisting>

    <para>
      The <xref linkend="acs_rels"/>
      table entries would look like so: 
    </para>

    <informaltable frame="all">
      <tgroup cols="3" align="center" colsep="1" rowsep="1">
        <colspec colname="c1"/>
        <colspec colname="c2"/>
        <colspec colname="c3"/>
        <thead>
	  <row>
	    <entry>
              <computeroutput>rel_type</computeroutput>
	    </entry>
	    <entry>
              <computeroutput>object_one</computeroutput>
	    </entry>
	    <entry>
	      <computeroutput>object_two</computeroutput>
	    </entry>
	  </row>
	</thead>
	<tbody>
	  <row>
	    <entry>
	      membership_rel
	    </entry>
	    <entry>
	      Pranksters
	    </entry>
	    <entry>
	      Pete
	    </entry>
	  </row>
	  <row>
	    <entry>
	      membership_rel
	    </entry>
	    <entry>
	      Pranksters
	    </entry>
	    <entry>
	      Poly
	    </entry>
	  </row>
	  <row>
	    <entry>
	      membership_rel
	    </entry>
	    <entry>
	      Pranksters
	    </entry>
	    <entry>
	      Penelope
	    </entry>
	  </row>
	</tbody>
      </tgroup>
    </informaltable>
<para>Read <computeroutput>acs_rels</computeroutput>: right-side is a
        subset of left-side, ie
        <computeroutput>object2</computeroutput> is a part of
        <computeroutput>object1</computeroutput>.
</para>
    <para>
      Another way of building up groups is by adding subgroups.  Suppose
      we define <emphasis>Merry Pranksters</emphasis> and <emphasis>Sad Pranksters</emphasis> as subgroups
      of <emphasis>Pranksters</emphasis>.  We say that the <emphasis>Pranksters</emphasis> group
      is <emphasis role="strong">composed</emphasis> of 
      groups <emphasis>Merry Pranksters</emphasis> and <emphasis>Sad Pranksters</emphasis>.  This
      information is stored in the <xref linkend="acs_rels"/>
      and <computeroutput>composition_rels</computeroutput> tables. 
    </para>
      
    <programlisting id="composition_rels" xreflabel="composition_rels">
create table <emphasis role="bold">composition_rels</emphasis> (
    rel_id
        constraint composition_rels_rel_id_fk references <xref linkend="acs_rels"/> (rel_id)
        constraint composition_rels_rel_id_pk primary key
);
    </programlisting>

    <para>
      The relevant entries in the 
      <xref linkend="acs_rels"/> look like so. 
    </para>

    <informaltable frame="all">
      <tgroup cols="3" align="center" colsep="1" rowsep="1">
        <colspec colname="c1"/>
        <colspec colname="c2"/>
        <colspec colname="c3"/>
        <thead>
	  <row>
	    <entry>
              <computeroutput>rel_type</computeroutput>
	    </entry>
	    <entry>
              <computeroutput>object_one</computeroutput>
	    </entry>
	    <entry>
	      <computeroutput>object_two</computeroutput>
	    </entry>
	  </row>
	</thead>
	<tbody>
	  <row>
	    <entry>
	      composition_rel
	    </entry>
	    <entry>
	      Pranksters
	    </entry>
	    <entry>
	      Merry Pranksters
	    </entry>
	  </row>
	  <row>
	    <entry>
	      composition_rel
	    </entry>
	    <entry>
	      Pranksters
	    </entry>
	    <entry>
	      Sad Pranksters
	    </entry>
	  </row>
	</tbody>
      </tgroup>
    </informaltable>

    <para>
      The composition relationship means that if I add Matt, Mel, and Mary to the 
      <emphasis>Merry Pranksters</emphasis>,
      they should also automatically become members of the <emphasis>Pranksters</emphasis> group. 
      The situation we are
      facing in trying to determine whether or not a user is member of a group is similar to the one
      discussed above in the case of the context hierarchy.  Groups can form hierarchies with
      respect to the composition relationship.  The compositon relationship is transitive.  If
      <emphasis>G1</emphasis> is a subgroup of <emphasis>G2</emphasis>, and <emphasis>G2</emphasis> is a subgroup of <emphasis>G3</emphasis>, then
      <emphasis>G1</emphasis> is a subgroup of <emphasis>G3</emphasis>; that is, any member of <emphasis>G1</emphasis> is also a member
      of <emphasis>G3</emphasis>. 
    </para>

    <para>
      Traversing the group composition hierarchy requires running
      <ulink url="http://www.oradoc.com/ora817/server.817/a85397/expressi.htm#1023748">hierarchical queries</ulink>,
      which are expensive in Oracle. As we saw in the <emphasis>Context Hierarchy</emphasis> section, one way of
      reducing the performance hit incurred by hierarchical queries is to cache query results in
      a table maintained by triggers.  The OpenACS data model defines two such tables:
    </para>
    
    <programlisting id="group_component_index" xreflabel="group_component_index">
 create table <emphasis role="bold">group_component_index</emphasis> (
          group_id        not null
                          constraint group_comp_index_group_id_fk
                          references <xref linkend="groups"/> (group_id),
          component_id    not null
                          constraint group_comp_index_comp_id_fk
                          references <xref linkend="groups"/> (group_id),
          rel_id          not null
                          constraint group_comp_index_rel_id_fk
                          references composition_rels (rel_id),
          container_id    not null
                          constraint group_comp_index_cont_id_ck
                          references <xref linkend="groups"/> (group_id),
          constraint group_component_index_ck
          check (group_id != component_id),
          constraint group_component_index_pk
          primary key (group_id, component_id, rel_id)
  ) organization index;
    </programlisting>
 
    <programlisting id="group_member_index" xreflabel="group_member_index">
  create table <emphasis role="bold">group_member_index</emphasis> (
      group_id
          not null
          constraint group_member_index_grp_id_fk references <xref linkend="groups"/> (group_id),
      member_id
          not null
          constraint group_member_index_mem_id_fk references <xref linkend="tedious-parties"/> (party_id),
      rel_id
          not null
          constraint group_member_index_rel_id_fk references <xref linkend="membership_rels"/> (rel_id),
      container_id
          not null
          constraint group_member_index_cont_id_fk references <xref linkend="groups"/> (group_id),
      constraint group_member_index_pk
          primary key (member_id, group_id, rel_id)
  ) organization index;
    </programlisting>

    <para>
      The <computeroutput>group_component_index</computeroutput> table stores a flattened representation of the
      group composition hierarchy that is maintained in sync with the <xref linkend="acs_rels"/>
      and <computeroutput>composition_rels</computeroutput> tables through triggers. 
    </para>
      
   <para><emphasis role="strong">additional comments</emphasis></para>
    <para>
      As far as the <computeroutput>group_member_index</computeroutput> table goes, I am not sure I understand its
      purpose.  It maintains group-member relationships that are resolved with respect
      to group composition.  Note that information stored in
      <xref linkend="group_member_index"/> can be trivially derived by joining
      <xref linkend="membership_rels"/>,
      <xref linkend="acs_rels"/>,
      and <xref linkend="group_component_index"/>. Here
      is a view that does it. (This view is <emphasis>not</emphasis> part of the OpenACS Kernel data model.)
    </para>
      
    <programlisting>
create or replace view group_member_view
as
select
  gci.group_id, r.object_id_two as member_id
from
  (
   select
     group_id, group_id as component_id
   from
     <xref linkend="groups"/>
   union
   select
     group_id, component_id
   from
     group_component_index
  ) gci,
  <xref linkend="membership_rels"/> mr,
  <xref linkend="acs_rels"/> r
where
  mr.rel_id = r.rel_id
  and r.object_id_one = gci.component_id;
    </programlisting>

    <para>
      A heuristic way to verify that <computeroutput>group_member_view</computeroutput> is essentially identical
      to <xref linkend="group_member_index"/> is to compute the
      symmetric difference between the two: 
    </para>

    <programlisting>
select
  group_id, member_id
from
  (
   select group_id, member_id from group_member_view
   minus
   select group_id, member_id from <xref linkend="group_member_index"/>
  )
union
select
  group_id, member_id
from
  (
   select group_id, member_id from <xref linkend="group_member_index"/>
   minus
   select group_id, member_id from group_member_view
  )
    </programlisting>

    <para>
      The query returns no rows.  The important point is, if we
      have a flattened view of the composition hierarchy -- like one provided
      by the <xref linkend="group_component_index"/> table --
      membership relationship resolution can be computed trivially with no hierarchical
      queries involved. There is no need to keep the view in a denormalized
      table, unless doing so results in substantial performance gains.
    </para>
    
  </sect2>

  <sect2 id="permissions-tedious-putting-all-together">
    <title>Putting It All Together</title>

    <para>
      Security information is queried by calling the <computeroutput>acs_permission.permission_p</computeroutput>
      function in OpenACS. This is accessible from Tcl via the
      <computeroutput>permission::permission_p</computeroutput> procedure. 
    </para>

    <programlisting>  
  create or replace package body acs_permission
  as
    -- some stuff removed for the sake of brevity
  
    function <emphasis role="bold">permission_p</emphasis> (
      object_id	 acs_objects.object_id%TYPE,
      party_id	 parties.party_id%TYPE,
      privilege	 acs_privileges.privilege%TYPE
    ) return char
    as
      exists_p char(1);
    begin
      -- XXX This must be fixed: -1 shouldn't be hardcoded (it is the public)
      select decode(count(*),0,'f','t') into exists_p
        from <xref linkend="acs_object_party_privilege_map"/>
       where object_id = permission_p.object_id
         and party_id in (permission_p.party_id, -1)
         and privilege = permission_p.privilege;
      return exists_p;
    end;

  end acs_permission;
    </programlisting>
<para><emphasis role="strong">problem avoidance</emphasis></para>
    <para>
      The function queries 
      <xref linkend="acs_object_party_privilege_map"/>,
      which is a humongous view that joins three flattened hierarchies:
      the context tree, the privilege hierarchy,
      the party composition (and membership) hierarchy. 
      It contains an extremely large number of rows. About
      the only kind of query you can run against it is the one
      performed by the <computeroutput>acs_permission.permission_p</computeroutput>
      function.  Anything other than that would take forever to
      finish or would ultimately result in a query error.
    </para>
    
    <para>
      For example, do not try to do things like
    </para>
    
    <programlisting>
select count(*)
  from <xref linkend="acs_object_party_privilege_map"/>;
    </programlisting>

    <para>
      To give another example of things to avoid, I have seen code like this: 
    </para>

    <programlisting>
  declare
      cursor cur is
        select
           object_id, party_id
        from
           <xref linkend="acs_object_party_privilege_map"/>
        where
           privilege = 'foo_create';
  begin
      -- revoke all 'foo_create' permissions
      for rec in cur
      loop
          acs_permission.revoke_permission (
              object_id  =<markup>></markup> rec.object_id,
              grantee_id =<markup>></markup> rec.party_id,
              privilege  =<markup>></markup> 'foo_create'
          );
      end loop;

      acs_privilege.remove_child('admin','foo_create');
      acs_privilege.drop_privilege('foo');

  end;
  /
    </programlisting>

    <para>
      The <computeroutput>acs_permission.revoke_permission</computeroutput> function merely runs a
      delete statement like so: 
    </para>

    <programlisting>  
  delete from
     acs_permissions
  where
     object_id = revoke_permission.object_id
     and grantee_id = revoke_permission.grantee_id
     and privilege = revoke_permission.privilege;
    </programlisting>

    <para>
      Note that in the above example, <computeroutput>acs_permissions</computeroutput> had only
      one entry that needed to be deleted: 
    </para>

    <informaltable frame="all">
      <tgroup cols="3" align="center" colsep="1" rowsep="1">
        <colspec colname="c1"/>
        <colspec colname="c2"/>
        <colspec colname="c3"/>
        <thead>
	  <row>
	    <entry>
              <computeroutput>object_id</computeroutput>
	    </entry>
	    <entry>
	      <computeroutput>grantee_id</computeroutput>
	    </entry>
	    <entry>
	      <computeroutput>privilege</computeroutput>
	    </entry>
	  </row>
	</thead>
	<tbody>
	  <row>
	    <entry>
	      default_context
	    </entry>
	    <entry>
	      registered_users
	    </entry>
	    <entry>
	      foo_create
	    </entry>
	  </row>
	</tbody>
      </tgroup>
    </informaltable>

    <para>
      The above script would never get around to deleting this entry because it had
      to loop through a gazillion rows in the humongous
      <computeroutput>acs_object_party_privilege_map</computeroutput> view. 
    </para>

  </sect2>

  <sect2 id="permissions-tedious-appendix">
    <title>Appendix: Various View Definitions</title>
    
    <programlisting id="acs_object_party_privilege_map" xreflabel="acs_object_party_privilege_map">
create or replace view <emphasis role="bold">acs_object_party_privilege_map</emphasis>
as
select
  ogpm.object_id,
  gmm.member_id as party_id,
  ogpm.privilege
from
  <xref linkend="acs_object_grantee_priv_map"/> ogpm,
  <xref linkend="group_member_map"/> gmm
where
  ogpm.grantee_id = gmm.group_id
union
select
  object_id,
  grantee_id as party_id,
  privilege
from
  <xref linkend="acs_object_grantee_priv_map"/>;
    </programlisting>

    <programlisting id="acs_object_grantee_priv_map" xreflabel="acs_object_grantee_priv_map">
create or replace view <emphasis role="bold">acs_object_grantee_priv_map</emphasis>
as
select
  a.object_id,
  a.grantee_id,
  m.descendant as privilege
from
  <xref linkend="acs_permissions_all"/> a,
  <xref linkend="acs_privilege_descendant_map"/> m
where
  a.privilege = m.privilege;
    </programlisting>


    <programlisting id="acs_permissions_all" xreflabel="acs_permission_all"> 
create or replace view <emphasis role="bold">acs_permissions_all</emphasis>
as
select
  op.object_id,
  p.grantee_id,
  p.privilege
from
  <xref linkend="acs_object_paths"/> op,
  <xref linkend="acs_permissions"/> p
where
  op.ancestor_id = p.object_id;
    </programlisting>

    <programlisting id="acs_object_paths" xreflabel="acs_object_paths">
create or replace view <emphasis role="bold">acs_object_paths</emphasis>
as
select
  object_id,
  ancestor_id,
  n_generations
from
  <xref linkend="acs_object_context_index"/>;
    </programlisting>

    <programlisting id="group_member_map" xreflabel="group_member_map"> 

create or replace view <emphasis role="bold">group_member_map</emphasis>
as
select
  group_id,
  member_id,
  rel_id,
  container_id
from
  <xref linkend="group_member_index"/>;
    </programlisting>

  </sect2>

</sect1>

