Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2002-01-09
2002-11-19
Shah, Sanjiv (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06484181
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to database environments, and more particularly to method and system for handling foreign key database updates in such environments.
BACKGROUND OF THE INVENTION
Today's object-oriented database environments are typically used as front-ends to more simplistic but efficient data models, such as flat files and relational databases. In such an environment, a client submits a semantic-rich query at the object-level and the system generates an execution plan specifying what queries to run against the relational databases, and how to combine those results to compute the final result.
In a relational database, data is perceived by its users as a collection of tables. The tables in a relational database include a row of column names specifying one or more attribute fields, and zero or more data rows containing one scalar value for each of the column fields. Objects referred to in the query received from the client are identified by a primary key. And the row in the underlying relational database table corresponding to this object is also uniquely identified by this primary key. A foreign key is an attribute(s) in a table that forms a relationship with another table by storing the primary key value of the related table.
Given a set of database tables, foreign key relationships are not necessarily present. If foreign key relationships are present in the set of tables, then the foreign key relationships are classified as either acyclic or cyclic.
FIG. 1
is a diagram illustrating acyclic foreign key relationships between example database tables. In the example, three tables are shown: Department, Project, and Employee. Each table includes one or more rows, although only one row is shown, and each row includes a primary key (designated with a * symbol) that uniquely identifies that row. In the Department table, the attribute “depno” is the primary key. In the Project table, the attribute “projno” is the primary key. And in the Employee table, the attribute “empno” is the primary key.
As shown by the arrows, a foreign key relationship exists between the Employee table and the Department table and between the Employee table and the Project table, because the Employee table includes the primary key “depno” from the Department table and the primary key “projno” from the Project table. The Department and Project tables are referred to as parent tables since they are the source of the primary keys in the Employee table. The Employee table is referred to as the child because it contains the foreign keys. The Employee table is dependent because its foreign key values are constrained to be values of the primary keys in the parent tables.
FIG. 2
is a diagram illustrating cyclic foreign key relationships between example tables. In the example, three tables are shown: Department, Employee, and Network. As before, the primary key of the Department table is “depno” and the primary key of the Employee table is “empno”. The Network table's primary, key is “netno”.
A cycle of foreign key relationships exists between the tables because there is a closed loop of child/parent relationships between the tables. As shown, the Department table is a child of the Network table since it includes the Network table's primary key “netno”, the Network table is a child of the Employee table since it includes the Employee table's primary key “empno”, and the Employee table is a child of the Department table since it includes the Department table's primary key “depno”. In contrast, the acyclic example in
FIG. 1
does not include a closed loop of child/parent relationships between the tables.
During operation of the database, an application may perform a number of object creation, removal and modification operations. The operations are typically implemented through commands such as Insert row, Delete row, and Update row, respectively. The application may pass one or more such row operations to the database and require that the changes be applied to the database at transaction commit time.
At commit time, the operations may alter one or more parent-child relationships between two objects by creating a new child for a parent, moving a child from one parent to another, removing a child's parent, or removing a child. When the parent-child relationship changes, the foreign key values need to be updated accordingly. However, the relational database imposes referential integrity (RI) constraints on foreign key updates. For example, a parent row's delete must be preceded by all children rows' deletes, and any child row can be inserted only after the parent has been inserted. Stated more formally, the RI constraints are:
a) a parent with a primary key must be inserted into the database or already exist before that foreign key may be assigned to a child row, and
b) a child row having a foreign key must be deleted before the parent with the primary key can be deleted.
When the list of row operations to be performed is received by the database, the insert, update and delete of the rows must be ordered to satisfy these RI constraints.
Conventional methods for ordering the row operations take all the rows to be modified and order them in a list to satisfy the constraints. This entails sequentially traversing the row operations and for each row finding rows that have corresponding children and/or parents. The child/parent rows are then examined to determine whether the child/parent needs to be modified before the current row. If it does, the child/parent row is placed in the list before the current row. If the child/parent row needs to be modified after the current row, then it is placed in the list after the current row. The result of this process is a linked list whose order defines the order of the updates in a way that satisfies all RI constraints. Although this method effectively accomplishes the task of ordering the row operations, the method is computationally expensive if there are many rows to be modified.
Another issue with database row operations is the case where foreign and primary keys overlap. A foreign or primary key can contain multiple attributes, and two keys overlap when they have one or more attributes in common. A foreign key may partially or completely overlap with other foreign or primary keys.
Consider, for example, a child table T
1
with a foreign key (A
1
, A
2
, A
3
), where A
1
, A
2
and A
3
are the attributes in the foreign key. When a user updates the foreign key for a given row in table T
1
, the value of some or all the attributes in the foreign key may change. Key overlap poses certain challenges when foreign keys are modified.
In case where a foreign key overlaps a primary key, the update of the foreign key may or may not be allowed. When an update is allowed, it invalidates any other foreign key the current key partially but not completely overlaps with. The task is to define which foreign key updates should be allowed and which ones should be forbidden.
To handle a row updates efficiently, the system must determine for each attribute in a row to be updated, the keys (foreign or primary) the attribute overlaps with, the keys the attribute completely contains, and the keys the attribute is completely contained by. This information determines whether to allow the foreign key update or not (it will not be allowed if it changes a primary key attribute value). It also determines what other foreign keys are invalidated by this update.
In conventional systems, this information is maintained in linked lists. Unfortunately, however, creating and scanning large linked lists is memory intensive and can be slow.
Accordingly, what is needed is a method and system for more efficiently ordering the database row operations to satisfy the RI constraints, and for detecting and handling other foreign and primary key updates when an overlapping foreign key is updated. The present invention addresses such needs.
SUMMARY OF THE INVENTION
The present invention is a method and system for handling foreign key database updates. The
Attaluri Gopi Krishna
Wisneski David Joseph
Sawyer Law Group LLP
Shah Sanjiv
LandOfFree
Method and system for handling foreign key update in an... 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 and system for handling foreign key update in an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for handling foreign key update in an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2959810