Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-11-19
2004-11-23
Homere, Jean (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C713S152000
Reexamination Certificate
active
06823338
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
This invention relates generally to providing directory services in a distributed computing environment and, in particular, to processing sparse hierarchical access control list (ACL) data stored in a relational database.
2. Description of the Related Art
A directory service is the central point where network services, security services and applications can form a integrated distributed computing environment. The current use of a directory services may be classified into several categories. A “naming service” (e.g., DNS and DCE Cell Directory Service (CDS)) uses the directory as a source to locate an Internet host address or the location of a given server. A “user registry” (e.g., Novell NDS) stores information of all users in a system composed of a number of interconnected machine. The central repository of user information enables a system administrator to administer the distributed system as a single system image.
With more applications and system services demanding a central information repository, the next generation directory service will need to provide system administrators with a data repository that can significantly ease administrative burdens. In addition, the future directory service must also provide end users with a rich information data warehouse that allows them to access department or company employee data, as well as resource information, such as name and location of printers, copy machines, and other environment resources. In the Internet/intranet environment, it will be required to provide user access to such information in a secure manner.
To this end, the Lightweight Directory Access Protocol (LDAP) has emerged as an IETF open standard to provide directory services to applications ranging from e-mail systems to distributed system management tools. LDAP is an evolving protocol that is based on a client-server model in which a client makes a TCP/IP connection to an LDAP server, sends requests, and receives responses. The LDAP information model in particular is based on an “entry,” which contains information about some object. Entries are typically organized in a specified tree structure, and each entry is composed of attributes. The directory tree is organized in a predetermined manner, with each entry uniquely named relative to its sibling entries by a “relative distinguished name” (RDN). An RDN comprises at least one distinguished attribute value from the entry and, at most, one value from each attribute is used in the RDN. According to the protocol, a globally unique name for an entry, referred to as a “distinguished name” (DN), comprises a concatenation of the RDN sequence from a given entry to the tree root.
LDAP provides the capability for directory information to be efficiently queried or updated. It offers a rich set of searching capabilities with which users can put together complex queries to get desired information from a backing store. Increasingly, it has become desirable to use a relational database for storing LDAP directory data. Representative database implementations include DB/2, Oracle, Sybase, Informix and the like. As is well known, Structured Query Language (SQL) is the standard language used to access such databases. Security for the information kept within the LDAP directory is provided through ACLs (Access Control Lists). The ACL contains the information about what distinguished names have permission to perform particular actions on an entry. The model breaks this information into two pieces: the entry owner, and the ACL entry. While the owner and the ACL are distinct, their behavior conceptually follows similar logic.
The ACL model requirements further specify that every entry must have an owner and at least one ACL. However, in the interest of usability, it is known in the art that an administrator does not have to set an ACL and an owner on every entry. This leads to a so-called sparse ACL model. If an ACL (owner) is not explicitly set on a particular entry, its value is inherited from an ancestor node within the directory. Given that the LDAP directory is hierarchical, this inheritance property means that an administrator may put an ACL (owner) at strategic points within the tree and have that ACL propagate to all entries below that point. Additionally, all changes to the ACL will also propagate. In this scheme, propagation of an ACL value continues until another propagating value is reached.
Although the entry owner and the ACL entry are both concepts within the known ACL model, they are not directly related. Because the ACL and owner are distinct, an entry with an owner specified may or may not have an explicit ACL. Similarly, an entry with an explicitly set ACL may or may not have an explicitly set owner.
To maintain the integrity of the sparse, hierarchical ACL data, it would be desirable to store such data in the database along with the information it protects. In the past, such data has been stored in an editable flat file. As is well-known, however, it is quite difficult to manage hierarchical data within a relational database. It is even more challenging to handle sparse heierarchical information, like ACLs, within relational tables. Storing the ACL and owner information with the entry is not feasible. It defeats some of the benefits of a sparse model because the space and processing requirements are burdensome.
BRIEF SUMMARY OF THE INVENTION
The present invention solves the problem of efficiently storing and processing sparse, hierarchical information in a relational database. The particular invention is particularly useful for storing and processing ACL data in a relational database used as a backing store to a Lightweight Directory Access Protocol (LDAP) directory service.
The ACL data is stored in the relational database using a plurality of tables. A first table, the owner table, contains owner information. The second table, the propagation table, contains propagation data. The third table, the permissions table, contains the ACL information. Thus, three separate tables are created and used to store two sets (ACL and owner) of related, but distinct sparse data. Because there can only be one entry owner DN per object, only one table is needed for the owner data. Likewise, because there can be multiple ACL entries per object, the propagation information is supported in its own table. Updates to propagation information therefore do not require excessive updates to multiple rows within the ACL entry table. Information is selectively pulled from these tables whenever an operation is requested.
In particular, the first, second and third tables are used to determine an entry owner and ACL for a given object. In one preferred method, a SELECT operation is performed based on an identifier of the object. If an ACL or owner is found, that value is kept. If, however, either the ACL or owner is not determined, the parent is checked. If the needed value is then found, a propagation flag is checked. If the propagation flag is TRUE, that value is kept. If the propagation flag is FALSE, then processing continues recursively until both an owner and an ACL value have been found. If the top of the tree (the suffix) has been reached without locating a propagating value, then system defaults are returned.
While this processing produces the desired results, search speed is enhanced significantly according to the present invention by implementing a fourth table, a source table. This table keeps track of the actual entry that holds the owner information (the owner source) and the entry that holds the ACL information (the ACL information) for each object within the directory. For a given object, the first, second, third and fourth tables are used to find the ACL and owner information using only a single SQL call. Use of this table provides the added advantage of avoiding ACL propagation when an explicit ACL or owner information is modified.
The foregoing has outlined some of the more pertinent objects and features of the present invention. These objects and features should be construed to be
Byrne Debora Jean
Shi Shaw-Ben
Homere Jean
LaBaw Jeffrey S.
Wassum Luke S
Winstead Sechrest & Minick P.C.
LandOfFree
Method, mechanism and computer program product for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method, mechanism and computer program product for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, mechanism and computer program product for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3315852