Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-05-06
2001-01-16
Alam, Hosain T. (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C711S171000
Reexamination Certificate
active
06175836
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a data retrieval system and methods of optimising access to the system.
BACKGROUND OF THE INVENTION
LDAP (lightweight directory access protocol) has been adapted as an Internet standard. An LDAP directory of the known type comprises a collection of hierarchically related objects, an example of which is shown in FIG.
1
. The structure of the directory and content of its objects are typically determined by the contents of a schema object which is normally itself stored in the directory. The contents of this schema object comprise a set of object class definitions and a set of structural rules, as shown for the above example in FIG.
2
. The class definitions include a) a list of both mandatory (M) and optional (O) attributes for each object class allowed in the directory; and b) a list defining the hierarchical relationships between object classes and hence the inheritance rules for class definitions. In the above example, all object classes other than top are subclasses of the class top, thus inheriting the attribute objectclass.
The structural rules control the arrangement of objects in the directory hierarchy and comprise a list of the allowed child object classes to each parent class and, for each such combination, the naming attribute(s) to be used to provide a unique relative distinguished name (RDN) for such an object.
The relative distinguished name (RDN) provides a unique name for an object at that point in the directory hierarchy. Its format is thus somewhat unpredictable for any object, as it is formed by a combination of one or more of the object's attributes and as can be seen from the naming attributes for employees, many different attributes may be used for an object at any one point in the tree. LDAP objects also have a unique name in the directory—the distinguished name (DN). The DN is formed by the successive, sequential concatenation of the RDNs of the object itself and its parents, back up to the root of the directory tree.
For reasons of economy, scaleability, robustness and performance, it is now becoming accepted that existing relational database products (DB2, Oracle etc.) be used for the LDAP backing store. This requires that the hierarchical directory data model be mapped into the tabular model of relational databases. (The LDAP directory model is based on X.500 although, the precise nature of the X.500 to relational database mapping is not important to this disclosure; many possibilities exist and the details are complex.) Similarly, LDAP protocol operations need to be mapped into the relational operations supported by SQL. However it also desirable that the directory data be available for ad-hoc queries, expressed directly in SQL.
It can be seen that the directory of
FIG. 1
contains objects with varying type of attributes. If a single table or relation is used to store all the objects, then most objects will have many null attributes, making inefficient use of storage. Thus, a relational database typically comprises one or more base relation(s), each comprising a plurality of objects which in turn includes one or more attributes. A universal relation is essentially a union of all of the information in the base relations in the database. If the universal relation is substantiated for every query, when the query may only require substantiation of a sub-set of base relations, then memory and processing power will be wasted. On the other hand requiring that the base relations used for directory storage should be understood by users, makes query formulation unduly difficult.
DISCLOSURE OF THE INVENTION
Accordingly, the present invention provides a data retrieval system in which a plurality of objects having a multi-level hierarchical relationship are stored, each object having a respective parent and a set of children, said system including:
means adapted to store one or more base tables, the or each base table comprising a respective set of attributes associated with a sub-set of objects in the system,
means adapted to generate for the or each base table a respective complementary table, the or each complementary table comprising a set of attributes excluding the attributes of the associated base table, and
optimisation means adapted to interpret a query comprising an expression including one or more operations, each operation having a respective operator and one or more associated operands; to track a number of objects associated with the or each operation and any attributes associated with the operation; and to re-formulate the expression accordingly.
In a further aspect, the invention is implemented in a computer program product comprising computer readable program code stored on a computer readable recording medium, the program code including a data retrieval system in which a plurality of objects having a multi-level hierarchical relationship are stored, each object having a respective parent and a set of children, said system including: means adapted to store one or more base tables, the or each base table comprising a respective set of attributes associated with a sub-set of objects in the system, means adapted to generate for the or each base table a respective complementary table, the or each complementary table comprising a set of attributes excluding the attributes of the associated base table, and optimisation means adapted to interpret a query comprising an expression including one or more operations, each operation having a respective operator and one or more associated operands; to track a number of objects associated with the or each operation and any attributes associated with the operation; and to re-formulate the expression accordingly.
The present embodiment employs the universal relation as an access model for a hierarchical directory stored in a plurality of relations in a relational database.
REFERENCES:
patent: 5276870 (1994-01-01), Shan et al.
patent: 5675785 (1997-10-01), Hall et al.
patent: 5701453 (1997-12-01), Maloney et al.
Alam Hosain T.
Dougherty Anne Vachon
Fleurantin Jean Bolte
International Business Machines - Corporation
Shofi David M.
LandOfFree
Optimization of relational database queries does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimization of relational database queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization of relational database queries will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2438206