Hierarchical Inheritance
in a Relational Database
Mark J. Norton
March 6, 2004
Recently, some concerns have been raised about the ability to efficiently resolve implied authorizations using implementations of osid.authorization using a relational database as the peristant storage method. This paper presents a method of performing heirarchical inhertance in relational tables and examines its using in handling implied authorizations.
Consider a hierarchically organized tree of objects:
Object A is at the root of the tree. Objects B and C inherit characteristics from A. Etc.
Trees of this nature are common in the kinds of data managed by OKI OSIDs which led to the creation of an OSID to handle them called osid.hierarchy. The hierarchy OSID allows general tree structures to be represented including those with merging branches and shared ancestors. For the purpose of this analysis, we shall assume that branches do not merge and that each child has one and only one parent.
Implementing inheritance functions (such as those required by osid.authorization) are straightforward using an in-memory tree structure. Inheritance is done by walking up the tree until the desired property is found or the root is reached. The matter becomes more complicated, however, when the objects are persisted in a relational database and for efficiency reasons, there is a desire to perform inheritance directly from the database.
This document explores how a database might be set up to efficiently perform inheritance. This is intended to resolve concerns about implicit authorizations in osid.authorization.
Based on the tree example given above, we can create an Inheritance_Table
|
OBJECT_ID |
ANCESTOR_ID |
RANK |
|
A |
0 | |
| B | A | 1 |
| C | A | 1 |
| D | B | 2 |
| D | A | 2 |
| E | B | 2 |
| E | A | 2 |
| F | C | 2 |
| F | A | 2 |
| G | F | 3 |
| G | C | 3 |
| G | A | 3 |
This table allows us to easily retrieve all ancestors of a give tree node. The following query, for example:
SELECT ANCESTOR_ID WHERE OBJECT_ID=”G” SORT BY RANK
gives us a result set of:
F, C, A
which is an ordered set of all of the ancestors of object “G”. This gets us part of the way there.
Suppose a person is authorized to perform a function on “C”, but doesn’t have explicit authorization to perform this function on F or G. Because C is an ancestor of F and G, the person has an implied authorization to perform functions on children of any node they have authorizations for.
The Qualifier class in osid.authorization is the “what” in the “who can-do what” authorization triplet. Course offerings in a course management system or digital assets in a repository are examples of Qualifiers. These are often organized hierarchically.
Suppose we have three persons, “Mark”, “Chuck”, “Lance” and two kinds of operations that can be performed on objects (defined by the tree above), “Read”, “Edit”. This leads to as set of explicit authorizations (Authorization_Table):
|
AGENT_ID |
FUNCTION_ID |
OBJECT_ID |
|
Mark |
Read | A |
| Mark | Edit | A |
| Chuck | Read | A |
| Chuck | Edit | B |
| Lance | Read | G |
| Lance | Read | D |
| Lance | Edit | G |
This table provides Mark with the implicit authorization to read and edit any object Chuck, on the other hand, can read any object, but can only edit B, C, and D. Lance has been given explicit authorization to read D and G, and edit to G. He has no implicit authorizations.
This table can be used to answer questions about explicit authorizations, such as, “Can Lance Edit G?” The query:
SELECT ASSET_ID WHERE (AGENT_ID=”Lance”, FUNCTION_ID=”Edit”, ASSET_ID=”G”)
Gives a result set of one record, indicated that, yes, Lance can edit G, because it is explicitly represented in the table. If we pose the same query with an AGENT_ID=”Mark”, we’d get a result set of zero, because there is not explicit authorization for editing G. Editing for G by Mark is implied by the hierarchical organization of assets in the Inheritance_Table.
By combining the Authorization_Table with the Inheritance_Table we can use a query similar to:
SELECT Interitance_Table.ANCESTOR_ID FROM Inheritance_Table INNER JOIN Authorization_Table ON Inheritance_Table.OBJECT_ID=Authorization_Table.OJBECT_ID WHERE (Authorization_Table.AGENT_ID=”Mark”, Authorization_Table.FUNCTION_ID=”Edit”, Inheritance_Table.OBJECT_ID=”G”)
for the purpose of resolving questions with implied authorization.
The only remaining question is how to handle more complex organizations of Qualifiers in Authorization structures. The osid.hierarchy interface allows for nodes to have more than one parent. This capability is needed for authorizations, at times. While the organization of classes and class offerings is likely to be a strict hierarchy, assets in a digital library may be included in more than one collection. For example, a “Best of” collection that spans other collections. We might want to give wider access to a Best-of collection that any of the individual collections.
The Inheritance_Table described above is not limited to single inheritance. Multiple inheritance can be represented as long as all ancestor paths are included in the table. While this potentially increases the size of this table considerably, it should allow implied authorizations with complex hierarchical organizations to be resolved.
Other References
http://www.agiledata.org/essays/mappingObjects.html#MappingInheritance
http://www-106.ibm.com/developerworks/webservices/library/ws-mapping-to-rdb/
http://www.solarmetric.com/Software/Documentation/2.3.2/docs/jdo_overview_why.html
http://www-db.stanford.edu/pub/keller/1995/high-perf.pdf