I think the problem is the terminology we are using. Actually you don't have to think about adding a party to a relational segment. A relational segment is a simple way of grouping parties based on their rel_type to a group. It says in effect all parties that have rel_type x to group y are in the segment, like a segment of the population.
So the first step is to think of what kinds of relationships you want to be valid on a group. You then create the rel_type.
The rel_type has to have a supertype that traces back to either membership_rel or composition_rel.
Once you have a group of the right type, and a party of the right type, you can make the party a member of the group using either membership_rel__new or composition_rel__new, making sure the rel_type attribute is set to your new rel_type.
Now if you want a relational segment to group parties based on their rel_type to the group, you use rel_segment__new to do that. You just need to name the segment, and know the group_id and the rel_type for the segment.
For every party with a rel_type of the right type to the group, rows will be inserted into party_approved_member_map (assuming you used 'approved' for the member_state attribute to membership_rel__new).
What do rows in this map represent? They represent aliases for the party. All registered users have an alias id of -2. In other words, a party can get permissions on an object_id by virture of permissions given to one of their aliases.
If you look above at my printout for member_id = 823 from this mapping table, you will see all the 'alias' party_ids. These ids are joined to the grantee_id in the acs_permissions table for permission checks, therefore the map explodes the member_id into a list of grantee_ids.
All that is left is to assign the privilege you want to the alias (group, relational segment or party) or grantee.
The key to understanding all this (for me) was this sublime piece of code:
select 1
from acs_permissions p, party_approved_member_map m,
acs_object_context_index c, acs_privilege_descendant_map h
where p.object_id = c.ancestor_id
and h.descendant = permission_p__privilege
and c.object_id = permission_p__object_id
and m.member_id = permission_p__party_id
and p.privilege = h.privilege
and p.grantee_id = m.party_id
