Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-01-22
2001-01-16
Amsbury, Wayne (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06175835
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to databases and database management systems.
BACKGROUND OF THE INVENTION
As is well known, a database system is a collection of interrelated data files, indexes and a set of programs that allow one or more users to add data retrieve and modify the data stored in these files. The fundamental concept of a database system is to provide users with a so called “abstract” and simplified view of the data (referred to also as data model or conceptual structure) which exempts a conventional user from dealing with details such as how the data is physically organized and accessed.
Some of the well known data models (i.e. the “Hierarchical model”, “Network model”, “Relational model” and “Object Relational Model” will now be briefly reviewed. A more detailed discussion can be found for example in: Henry F. Korth, Abraham Silberschatz, “Database System Concepts”, McGRAW-Hill International Editions, 1986 (or the 3
rd
edition (1997))., Chapters 3-5 pp. 45-172.
Generally speaking, all the models to be discussed below have a common property in that they represent each “entity” as a “record” having one or more “fields” each being indicative of a given attribute of the entity (e.g. a record of a given book may have the following fields “BOOK ID”, “BOOK NAME”, “TITLE”). Normally one or more attributes constitute a “key” i.e. it identifies the record. In the latter example “BOOK-ID” serves as a key. The various models are distinguished one from the other, inter alia, in the way that these records are organized into a more complex structure:
Relational Model—The relational model, introduced by Codd, is a landmark in the history of database development. In relational databases an abstract concept has been introduced, according to which the data is represented by tables (referred to as “relations”) in which the columns represent the fields and rows represent the records.
The association between tables is only conceptual. It is not a part of the database definition. Two tables can be implicitly associated by the fact that they have one or more columns whose values are taken from the same set of values (called “domain”).
Other concepts introduced by the relational model are high level operators that operate on tables (i.e., both their parameters and results are tables) and comprehensive data languages (now called 4th generation languages) in which one specifies what are the required results rather than how these results are to be produced. Such non-procedural languages (SQL—Structured Query Language) have become an industry standard. Furthermore, the relational model suggests a very high level of data independence. There should not be any effect on the programs written in these languages due to changes in the manner data are organized, stored, indexed and ordered. The relational model has become a de-facto standard for data analysts.
Network Model—In the relational model, data (and relationship between data) are regarded as a collection of tables. In distinction therefrom in the network model data are represented as a collection of records whereas relationship between the records (data) are represented as links.
A record in the network model is similar to an “entity” in the sense that it is a collection of fields each holding one type of data. The links may be effectively viewed preferably (but not necessarily) as pointers. A collection of records and the relation therebetween constitutes a collection of graphs.
Hierarchical Model—The Hierarchical Model resembles the network model in the manner that data and relations between data are treated, i.e. as records and links. However, in distinction from the network model, the records and the relations between them constitute a collection of trees rather than of arbitrary graphs. The structure of the Hierarchical Model is simple and straightforward particularly in the case that the data that needs to be organized in a database are of inherent hierarchical nature. The hierarchical model has some inherent shortcomings, e.g. in many real life scenarios data cannot be easily arranged in hierarchical manner. Moreover, even if data may be organized in hierarchical manner, it may require larger volumes as compared to other database models.
Consider for example a basic entity “Employee” with the following subordinated attributes “Employee_Salary” and “Employee_Attendance”. The latter may also have subordinated attributes e.g. “Employee_Entries” and “Employee_Exits”. In this scenario the data is of inherent hierarchical nature and therefore should preferably be organized in the hierarchical model. Consider, for example, a scenario where “Employee” is assigned to several “Projects” and the time he/she spends (“Time_Spent”) in each project is an attribute that is included in both the “Employee” and “Projects” entities. Such arrangement of data cannot be easily organized in the hierarchical model and one possible solution is to duplicate the item “Time_Spent” and hold it separately in the hierarchies of “Employee” and “Project”. This approach is cumbersome and error prone in the sense that it is now required to assure that the two instances of “Time_Spent” are kept identical at all times.
Object Oriented Model—A comprehensive explanation can be found in “Object Oriented Modeling and Design”, James Rumbaugh, Michael Blaha, William Premerlani, Fredrick Eddi and William Lorensen.
The object-oriented approach views all entities a objects. Each object belongs to a class, with each class there are associated methods and fields. To enable encapsulation some the fields are private, accessible only to methods of the class while others are public accessible to all. Thus “Joe Smith” belongs to the class of persons. For that class, the private fields age can be defined. Applying the class method update_age() to the object Joe will change his age. The methodology allows to define sub-classes which inherit all the methods and fields of the super-class. Thus, for example, the employee class can be defined as a subclass of the person class. In addition one may define additional fields and methods to the subclass. Thus, the employee class could support a salary field, and the get raise() method.
Object Relational Model allows an object view on relational-organized data. Thus, one is able to operate on the data as if it is organized as objects and at the same time, support the relational approach. As mentioned in the foregoing, data models deal with the conceptual or logical level of data representation and “hide” details such as how the data are physically arranged and accessed. The latter characteristics are normally dealt with by a so-called database file management system.
The database file management system maps the logical structure (in terms of database model) to a data structure, pertinent operations and possibly other data. The data structure includes index and data records. The index enables accessing or updating the data records by a key. In the context of search, the term search key is used. Database file management system should preferably operate on the data records so as to accomplish enhanced performance in terms of time (i.e. from the user's standpoint fast response time of the database), and space (i.e. to minimize the storage volume that is allocated for the database files). As is well known in the art, normally, there is a trade off between the time and space requirements. The performance of the database depends on the efficiency of the data structures that are used to represent the data and how efficiently the system can operate on these data. A detailed discussion on conventional file and management systems is given for example in Chapters 7 (file system structure) and 8 (indexing) in “Database System Concepts”, ibid.
Known database file management systems typically utilize the following indexing schemes, which fall into the following main categories that include: Multi-way trees indexes and others.
Multi-way trees indexes—These techniques can be used to create a one or more access paths (referred to also as searc
Amsbury Wayne
Oliff & Berridg,e PLC
Ori Software Development Ltd.
LandOfFree
Layered index with a basic unbalanced partitioned index that... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Layered index with a basic unbalanced partitioned index that..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Layered index with a basic unbalanced partitioned index that... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2543338