Case: 1:20-cv-02032-DCN Doc #: 1-1 Filed: 09/10/20 1 of 15. PageID #: 16
`
`
`
`
`
`
`
`EXHIBIT A
`
`

`

`USOO7502791 B2
`
`(12) United States Patent
`Sjogren et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,502,791 B2
`Mar. 10, 2009
`
`(54) DATABASE CONSTRAINT ENFORCER
`(75) Inventors: Bjorn-Harald Sjogren, Ski (NO);
`Jan-Thore Bjornemyr, Hamar (NO)
`(73) Assignee: Norsync Technology A/S, Oslo (NO)
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 204 days.
`
`(21) Appl. No.: 10/720,262
`1-1.
`(22) Filed:
`(65)
`
`Nov. 25, 2003
`Prior Publication Data
`US 2004/O1 O72OO A1
`Jun. 3, 2004
`
`Related U.S. Application Data
`(60) Provisional application No. 60/428,937, filed on Nov.
`26, 2002.
`(51) Int. Cl.
`(2006.01)
`G06F 7/30
`(52) U.S. Cl. ........................ 707/8: 707/2; 707/3; 707/9
`(58) Field of Classification Search ..................... 707/8,
`707/9, 2, 3
`See application file for complete search history.
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`4,933,848 A * 6/1990 Haderle et al. .............. 707/2O1
`4,947,320 A * 8/1990 Crus et al. .................. 707/2O1
`5,386,557 A *
`1/1995 Boykinet al. .................. 707/1
`5,408,657 A * 4/1995 Bigelow et al. .....
`... 707/100
`5,706,494. A *
`1/1998 Cochrane et al. ............... 707/2
`5,899,993 A * 5/1999 Jenkins, Jr. .................... 707/9
`6,047.285 A * 4/2000 Jacobs et al. ................... 707/4
`6,105,025 A
`8/2000 Jacobs et al. ................... 707/8
`
`EP
`
`9/2002 Chan et al. ..................... 707/3
`6,453,314 B1
`7,272.589 B1* 9/2007 Guay et al. .................... 707/2
`2003/0140028 A1
`7/2003 Sjogren
`FOREIGN PATENT DOCUMENTS
`O351210
`1, 1990
`OTHER PUBLICATIONS
`“Referential Integrity Impementation Details and advantages' IBM,
`Technical Disclosure Bulletin, IBM Corp New York, Mar. 1, 1995,
`pp. 477-487.
`Date C.J. “referential Integrity” Conference on Very Large Data
`bases, Cannes, Sep. 9-11, 1981 IEEE US vol CONF 7 pp. 2-12
`XPOO745O22.
`EP search report, listing above, dated Sep. 6, 2004.
`* cited by examiner
`Primary Examiner Tim T Vo
`Assistant Examiner Mahesh H Dwivedi
`(74) Attorney, Agent, or Firm—Birch, Stewart, Kolasch &
`Birch, LLP
`(57)
`ABSTRACT
`A transaction based constraint enforcer for a database system
`is arranged to delay constraint checks until the end of a
`transaction by creating a check Stack during the course of the
`transaction and executing entries on the check stack at the end
`of the transaction. A stack maker module is arranged for
`creating and updating said check stack. The stack maker
`module is operatively connected to a runtime module in the
`database system and arranged to receive data from said runt
`ime module. An enforcer module is arranged to receive check
`data from the check stack, to process the check data received
`from the check stack, and to provide resulting data to the
`runtime module. The invention also relates to a method for
`enforcing a set of constraints that governs the integrity of
`information stored in a database system, and a database sys
`tem which includes the constraint enforcer.
`
`12 Claims, 4 Drawing Sheets
`
`Case: 1:20-cv-02032-DCN Doc #: 1-1 Filed: 09/10/20 2 of 15. PageID #: 17
`
`
`
`460 User
`
`45
`Application
`program
`
`
`
`400 Database systern
`
`470 Costraint enforcer
`
`472
`Conceptual
`Rules
`
`410 Runtime H
`
`474
`Stack-maker
`
`412 Storage
`engine
`
`
`
`
`
`
`
`420 database
`
`478
`Enforcer
`Thodule
`
`

`

`U.S. Patent
`
`Mar. 10, 2009
`
`Sheet 1 of 4
`
`US 7,502,791 B2
`
`
`
`
`
`
`
`150 Application
`
`130 Data
`Dictionary
`
`
`
`
`
`10 Runtime 8
`Storage engine
`
`
`
`120 Database
`
`
`
`Case: 1:20-cv-02032-DCN Doc #: 1-1 Filed: 09/10/20 3 of 15. PageID #: 18
`
`Fig. 1
`
`

`

`U.S. Patent
`
`Mar. 10, 2009
`
`Sheet 2 of 4
`
`US 7,502,791 B2
`
`200
`
`250 Application
`
`230 Runtime
`module
`
`
`
`
`
`Case: 1:20-cv-02032-DCN Doc #: 1-1 Filed: 09/10/20 4 of 15. PageID #: 19
`
`215 RSK kerne
`
`220 Database
`
`
`
`Fig. 2
`
`

`

`U.S. Patent
`
`Mar. 10, 2009
`
`Sheet 3 of 4
`
`US 7,502,791 B2
`
`• * * * * * * * * * * * * *** * * * * * * * * * * * * : * I
`
`.
`
`.
`
`.
`
`.
`
`. . .
`
`.
`
`300 Database syst m
`
`.
`
`.
`
`. . .
`
`.
`
`.
`
`.
`
`. . . . . . . . . . . . . . . . . . . .
`
`. . . . . . . . . . . . . . . . . . . . . . .
`
`360 User
`
`
`
`
`
`
`
`350
`Application
`program
`
`
`
`
`
`
`
`
`
`380 Conceptual
`rules
`
`370 Constraint
`enforcer
`
`310 Storage
`engine
`8 runtime
`module
`
`
`
`
`
`
`
`320 Database
`
`Case: 1:20-cv-02032-DCN Doc #: 1-1 Filed: 09/10/20 5 of 15. PageID #: 20
`
`" * : * : *** | * * * * * * * * : * * * . . . . . . . .
`
`. . . . .
`
`. . .
`
`.
`
`.
`
`.
`
`. . .
`
`. . . . .
`
`.
`
`. .
`
`.
`
`. . . .
`
`. . . . . . . . . . . . . . . . . . . . . . . . . .
`
`. .
`
`. . . . . . . . .
`
`. . . . . . . . . . . . .
`
`

`

`U.S. Patent
`
`Mar. 10, 2009
`
`Sheet 4 of 4
`
`US 7,502,791 B2
`
`
`
`400 Database system
`
`
`
`460 User
`
`
`
`450
`Application
`program
`
`470 Constraint enforcer
`
`472
`Conceptual
`Rules
`
`
`
`410 Runtime
`
`412 Storage
`engine
`
`
`
`420 Database
`
`
`
`478
`Enforcer
`module
`
`Case: 1:20-cv-02032-DCN Doc #: 1-1 Filed: 09/10/20 6 of 15. PageID #: 21
`
`Fig. 4
`
`

`

`1.
`DATABASE CONSTRAINT ENFORCER
`
`US 7,502,791 B2
`
`RELATED APPLICATION DATA
`
`This application claims priority to U.S. Provisional Appli
`cation No. 60/428,937, filed Nov. 26, 2002, entitled “Con
`straint Enforcer', which is expressly incorporated herein by
`reference in its entirety.
`
`5
`
`FIELD OF THE INVENTION
`
`This invention relates generally to database technology.
`More specifically, the invention relates to a transaction
`based constraint enforcer for a database system, a method for
`enforcing constraints that governs the integrity of information
`stored in a database system, and a database system which
`includes a transaction based constraint enforcer.
`
`BACKGROUND OF THE INVENTION
`
`10
`
`15
`
`Consistency is one of the primary design goals of database
`systems. Consistency means that the information stored in the
`database obeys certain constraints defined for the database.
`A DML statement is a modification, Such as a deletion, an
`insertion or an update (or modification), of a single piece of
`information in a database.
`A transaction is a sequence of DML statements that per
`forms a single logical action in a database application.
`The 100% principle states: There is one grammar which
`completely and exclusively prescribes all the permitted infor
`mation base states and all the permitted information base
`transitions. This grammar is called the Conceptual Schema.
`One requirement that is deducted from the 100% principle
`is that all updates storing, deleting or modifying information
`has to be interrupted and checked by a constraint enforcer.
`Constraints are a special case of the term “conceptual
`rules”. Conceptual rules are the rules that prescribe all per
`mitted States and transitions a database can undertake. Con
`ceptual Rules are not limited to testing the legality of data, but
`also includes computational capabilities. Conceptual Rules
`should always be obeyed, and they should be “fired as a
`result of any database change.
`There are two types of Conceptual Rules, rules of static
`nature and of dynamic nature. Static rules can be checked at
`any time, while dynamic rules must be checked for each
`update. E.g. a unique Social Security Number (SSN) for a
`person can be checked at any time, but a status change from
`Married to Divorced can only be checked when the status is
`changed. The present invention mainly relates to constraint
`enforcers for static rules.
`To keep a database consistent at all times, sometimes needs
`Very complex programming.
`Some constraints are impossible to implement if they have
`to be checked per DML statement. One example is the equal
`constraint. An equal constraint is a rule that says that for a
`given value in Table T1, the same value must existin TableT2,
`and vise versa. If you insert T1 first, the value does not exist
`in T2 and the insert is rejected. If you insert T2 first, the value
`does not exist in T1 and the insert is rejected. It is a deadlock
`situation.
`For these kinds of problems, the term Conceptual Trans
`action has been introduced. It states that at the beginning and
`end of the transaction, the database must be in a consistent
`state. During the transaction the database is allowed to be in
`an inconsistent state. By using a Conceptual Transaction, the
`above examples become quite trivial.
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Case: 1:20-cv-02032-DCN Doc #: 1-1 Filed: 09/10/20 7 of 15. PageID #: 22
`
`2
`A Database Transaction is a sequence of DML statements
`needed for a program to do a certain task. It may be thought of
`as an envelope with DML statements.
`If during the course of a transaction, the Conceptual Rules
`may be broken, the transaction is referred to as a Conceptual
`Transaction.
`It has been previously observed that it would be sufficient
`to check all involved Constraints in a Conceptual Transaction
`for the total database at the end of the transaction. But it was
`also understood that such an approach would be too time
`consuming for a practical implementation.
`An objective of the present invention is to provide a trans
`action based constraint enforcer for a database system, a
`method for enforcing a set of constraints that governs the
`integrity of information stored in a database, and a database
`system, which provides a full constraint check facility, satis
`fying the 100% principle for databases.
`Another object of the invention is to provide such a con
`straint enforcer, a method, and a database system which may
`be implemented in a simple and efficient way.
`A particular object of the invention is to provide such a
`transaction based constraint enforcer, a method, and a data
`base system, wherein the number of tests that need to be
`performed at the end of a series of DML statements included
`in a conceptual transaction does not exceed the number of
`tests that would have to be performed if the DML statements
`were not bracketed in a conceptual transaction.
`Another particular object of the invention is to provide such
`a constraint enforcer, a method, and a database system, which
`includes a transaction based constraint enforcer, wherein con
`ceptual transaction may be implemented in a fashion that
`allows single DML statements s as well as a transaction
`comprising a sequence of DML statements.
`
`SUMMARY OF THE INVENTION
`
`In accordance with a first aspect of the present invention, a
`transaction based constraint enforcer for enforcing a set of
`constraints that governs the integrity of information stored in
`a database system is provided. The enforcer is arranged to
`delay constraint checks until the end of a transaction by
`creating a check stack during the course of the transaction and
`executing entries on the check stack at the end of the trans
`action.
`Advantageously, the constraint enforcer comprises a stack
`maker module, arranged for creating and updating the check
`stack. The stack maker module is also operatively connected
`to a runtime module in the database system and arranged to
`receive data from the runtime module.
`The constraint enforcer advantageously further comprises
`an enforcer module, arranged to receive check data from the
`check stack, to process the check data received from the check
`stack, and to provide resulting data to the runtime module.
`Advantageously, the constraints are stored in a conceptual
`rules module included in the constraint enforcer, comprising
`rules for prescribing permitted States and transitions that the
`database can undertake. The stack maker module is opera
`tively connected to the conceptual rules module and arranged
`to retrieve constraints from the conceptual rules module.
`The check stack may be stored on persistent or volatile
`memory.
`The constraint enforcer is advantageously further arranged
`to handle a modify operator as a delete operator followed by
`an insert operator.
`In accordance with a second aspect of the present inven
`tion, a method for enforcing a set of constraints that governs
`the integrity of information stored in a database system is
`
`

`

`US 7,502,791 B2
`
`3
`provided. The method comprises the steps of enforcing a set
`of constraints that governs the integrity of information stored
`in the database, and delaying constraint checks until the end
`of a transaction by creating a check stack during the course of
`the transaction and executing entries on the check Stack at the
`end of the transaction.
`Advantageously, the method further comprises the follow
`ing steps, performed by a stack maker module operatively
`connected to a runtime module in the database system: receiv
`ing data from the runtime module, retrieving constraints from
`the conceptual rules module, and creating and updating the
`check stack.
`Advantageously, the method further comprises the follow
`ing steps, performed by an enforcer module: receiving check
`data from the check stack, processing the check data received
`from the check stack, and providing resulting data to the
`runtime module.
`Advantageously, the constraints are stored in a conceptual
`rules module, comprising rules for prescribing permitted
`states and transitions that the database can undertake. The
`stack maker module is operatively connected to the concep
`tual rules module and arranged to retrieve constraints from
`the conceptual rules module.
`The check stack used in the method may be stored on
`persistent or volatile memory.
`The method advantageously further comprises the step of
`handling, by the Stack maker module, a modify operator as a
`delete operator followed by an insert operator.
`According to a third aspect of the present invention, a
`30
`database system is provided. The database system comprises
`an application program interface, providing a two-way mes
`sage interface to a user application program, a runtime mod
`ule, operatively connected to the application program inter
`face, a storage engine module, operatively connected to the
`runtime module, a data storage, operatively connected to the
`storage engine module, and a transaction based constraint
`enforcer as described above. The constraint enforcer is thus
`arranged for enforcing a set of constraints that governs the
`integrity of information stored in the database, said enforcer
`being arranged to delay constraint checks until the end of a
`transaction by creating a check Stack during the course of the
`transaction and executing entries on the check stack at the end
`of the transaction.
`Additional features and principles of the present invention
`will be set forth in part in the description which follows, and
`in part will be obvious from the description, or may be learned
`by practice of the invention. The features and principles of the
`present invention will be realized and attained by means of the
`elements and combinations particularly pointed out in the
`appended claims.
`It is to be understood that both the foregoing general
`description and the following detailed description are exem
`plary and explanatory only and are not restrictive of the inven
`tion, as claimed.
`
`5
`
`10
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`4
`FIG. 2 is an exemplary block diagram illustrating a data
`base system environment with a dynamically changeable
`runtime module, applicable for use with the principles of the
`present invention;
`FIG. 3 is an exemplary block diagram illustrating a data
`base system which includes a constraint enforcer, and
`FIG. 4 is an exemplary block diagram illustrating a data
`base system which includes a constraint enforcer, consistent
`with the principles of the present invention.
`
`DETAILED DESCRIPTION OF THE
`EMBODIMENTS
`
`Reference will now be made in detail to the present inven
`tion, examples of which are illustrated in the accompanying
`drawings.
`FIG. 1 is an exemplary block diagram of a conventional
`database system environment, applicable for use with the
`principles of the present invention.
`The database system 100 as shown in operates in an inter
`preter like execution mode. The system 100 includes an inter
`preting database runtime module and storage engine 110, a
`data storage 120, an online data dictionary 130, an application
`program interface 145 and an application program 150.
`The interpreting database runtime module and storage
`engine 110 functions as the actual data interpreter. The data
`storage 120 physically stores the data, i.e., data files.
`The online data dictionary 130 stores meta-data, typically
`including information describing tables, columns, fields, data
`types for columns, and domain restrictions for these columns.
`The meta-data kept in the data dictionary 130 also includes
`information about different constraints, such as primary keys,
`foreign keys, Subset constraints, exclude constraints, etc. The
`meta-data are typically provided by a data model or schema
`(not shown), compiled by a schema compiler (not shown).
`FIG. 2 is an exemplary block diagram illustrating a data
`base system environment with a dynamically changeable
`runtime module, also applicable for use with the principles of
`the present invention.
`The system illustrated in FIG. 2 includes a database runt
`ime module 230. The database runtime module 230 is an
`executable program, which is generated from a code genera
`tor (not shown), which in turn operates according to a data
`model or schema represented in an offline data dictionary (not
`shown). The offline data dictionary essentially keeps the same
`information as would be kept in the online data dictionary 130
`shown in FIG. 1. The offline data dictionary thus includes
`metadata including information about constraints.
`The database runtime module 230 is operatively connected
`to a storage engine denoted a RISK module (Reduced Instruc
`tion Set Kernel) 215. The RISK module 215 is operatively
`connected to the data storage 220, which physically stores the
`data, i.e., data files.
`The database runtime module 230 also includes an appli
`cation program interface (API), which is operatively con
`nected to an application program 250.
`The generated runtime module 230 includes constraint
`checking functionality. Thus, the runtime module is tailor
`made for the constraints kept in the offline dictionary and
`used by the code generator.
`In the following description, the term "eDB is used for a
`database system in accordance with the dynamically change
`able runtime module approach illustrated in FIG. 2.
`FIG. 3 is an exemplary block diagram illustrating a data
`base system which includes a constraint enforcer.
`An application program 350, operated by a user 360, is
`operatively connected to the database system 300 via an
`
`Case: 1:20-cv-02032-DCN Doc #: 1-1 Filed: 09/10/20 8 of 15. PageID #: 23
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The accompanying drawings, which are incorporated in
`and constitute a part of this specification, illustrate several
`embodiments of the invention and together with the descrip
`tion, serve to explain the principles of the invention, and,
`together with the description, explain the features and aspects
`of the invention. In the drawings,
`FIG. 1 is an exemplary block diagram of a conventional
`database system environment, applicable for use with the
`principles of the present invention
`
`60
`
`65
`
`

`

`5
`application program interface (API) 345. The API 345 is
`operatively connected to a runtime and storage engine mod
`ule 310. This is, in turn, further operatively connected to the
`database320, which is the data storage for physical storage of
`the data, i.e., data files.
`The user 360 is thus allowed to communicate messages to
`the database system 300. DML statements derived from such
`messages from the environment, in particular from the user
`360, are checked by the constraint enforcer 370 before they
`are accepted in the database system 300. The constraint
`enforcer 370 is operatively connected to a conceptual rule
`unit 380 on the one side, and to the runtime and storage engine
`319 on the other side. The purpose of the constraint enforcer
`is to assure the 100% principle is satisfied for the database
`system 300 as a whole.
`FIG. 4 is an exemplary block diagram illustrating a data
`base system which includes a constraint enforcer, consistent
`with the principles of the present invention.
`An application program 450, operated by a user 460, is
`operatively connected to the database system 400 via an
`application program interface (API) 445. The API 445 is
`operatively connected to a runtime module 410 in close
`operative connection with a storage engine module 412. The
`storage engine module 412 is further operatively connected to
`the database 420, which is the data storage for physical stor
`age of the data, i.e., data files.
`The user 460 is thus allowed to communicate messages to
`the database system 400. SML statements derived from such
`messages from the environment, in particular from the user
`460, are checked by the constraint enforcer 470 before they
`are accepted in the database system 400. The constraint
`enforcer 470 is operatively connected to the runtime module
`410. The purpose of the constraint enforcer 470 is to assure
`the 100% principle is satisfied for the database system 400 as
`a whole.
`35
`The constraint enforcer 470 comprises a stack maker mod
`ule 474, a conceptual rules module 472, an enforcer module
`478 and a check stack 476.
`If the constraint enforcer, the method or the system accord
`ing to the invention is operating in an environment of the
`traditional type as illustrated in FIG. 1, the conceptual rules
`module 472 should be understood to be a subset of the rule set
`incorporated in the data dictionary 130. On the other hand, if
`the constraint enforcer, the method or the system according to
`the invention is operating in a dictionary-free environment
`which includes a dynamically changeable runtime module, as
`illustrated in FIG. 2, the conceptual rules module 472 should
`be understood to be an executable program module, corre
`sponding to a set of rules, as described in the offline dictio
`nary.
`The stack maker module 474 is operatively connected to
`the runtime module 410 and arranged to receive data form the
`runtime module 410. The stack maker module 474 is further
`arranged to populate and maintain the check stack 476. The
`stack maker module 474 is further operatively connected to
`the conceptual rules module 472, which in this case is an
`integrated part of the constraint enforcer 470. The check stack
`is operatively connected to the enforcer module 478, which in
`turn is operatively connected to the runtime module 410. The
`enforcer module 478 is arranged to process the check stack
`and thus perform the checks.
`In the following, the invention will be described in further
`detail, primarily in conjunction with the "eDB' environment
`as described with reference to FIG. 2. The skilled person will
`however realize that the principles of the invention are also
`applicable for the conventional environment as described
`with reference to FIG. 1.
`
`25
`
`30
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Case: 1:20-cv-02032-DCN Doc #: 1-1 Filed: 09/10/20 9 of 15. PageID #: 24
`
`US 7,502,791 B2
`
`5
`
`10
`
`15
`
`6
`As an approach in order to arrive at the present invention,
`one would think that it should be possible to stack information
`gathered during the course of the transaction. That stacked
`information could then be used at the end of the transaction to
`verify the consistency from the stacked information and the
`database.
`A first approach is to stack Constraints and Table refer
`ences in order to check all referential and uniqueness Con
`straints at the end of the transaction. This proves insufficient.
`It is trivial to find examples where the proposal is insufficient.
`Three cases that demonstrate the problem are given below.
`
`TABLE A
`
`Stack of Constraints and record occurrences
`that have to be checked.
`
`Constraint
`
`Equal-1
`Equal-1
`Subset-1
`
`Table
`
`T1
`T2
`T3
`
`Table
`address
`
`alt1
`alt2
`alt
`
`Observe that the kind of DML statement (Insert, Update or
`Delete) is missing but may be added. As appears, there are
`still problems.
`Delete is a special problem since you have no Table address
`to use, and therefore no previous value to check against.
`Observe that if T3 is the Subset “owner, then all Subset-1
`members pointing to T3 (alt3) must be checked at the end of
`the transaction. The check has sometimes to be done against
`previous value(s) that does not exist at the end of the trans
`action.
`A variant where references to the class occurrences
`involved in the rule, is put on a list, should be sufficient for
`inserts. However Delete and Update may “hide' what should
`be checked (previous values).
`Such a modified approach is therefore also insufficient.
`The Check Stack
`Although the check Stack is not a real stack, it is called so
`as its originator as an idea was the constraint stack.
`The new stack is a list of all checks that has to be performed
`at the end of the transaction.
`The Check Stack contains a list of simple functions that
`have to be performed at the end of a Conceptual Transaction
`to check the consistency.
`
`TABLE B
`
`Stack of Check-functions, check-arguments and proper messages.
`
`Message
`
`Duplicate of T1
`Equal value
`missing in T2
`Duplicate of T2
`Equal value
`missing in T1
`T3 value is
`used in Tmember
`
`Table
`to check
`
`T1
`T2
`
`T2
`T1
`
`Value to
`check
`
`t1 Value
`t1 Value
`
`t2 Value
`t2 Value
`
`The check
`
`LessThan2
`OneCDr.More
`
`LessThan2
`OneCDr.More
`
`Tmember
`
`Originalt3Value
`
`OneCDrMOwn
`
`The first four entries are from two Inserts and the last one
`is from a Delete.
`The Nature of Constraints and Transactions
`A constraint check is performed via certain operations (the
`check) and operands (columns). According to the invention,
`we have proposed to stack the operations and operands to be
`
`

`

`US 7,502,791 B2
`
`8
`
`TABLED
`
`Transaction Table 2.
`
`7
`performed (together with necessary diagnostic information
`for proper diagnostic to the application).
`A Transaction may contain more than a single DML state
`ment. There is no guarantee that any given database occur
`rence is used with only one DML statement. That means that 5
`a modified occurrence may then be modified or deleted later
`in the transaction. A deleted occurrence may be inserted again
`later end even modified after that.
`In modification, supporting keys may change, so an earlier 10
`established operand in the stack has to be changed. The fol
`lowing examples should demonstrate the above statement:
`
`TABLE C
`
`Transaction Table 1.
`
`Transaction
`
`The check and operands.
`
`Insert (r)
`
`Insert (r), Delete (r)
`
`Insert (r), Modify (r
`to r1)
`Insert (r), Modify (r
`to r1), Delete (r1)
`Delete (r)
`
`Modify (r to r1)
`
`Modify (r to r1),
`Modify (r1 to r2)
`Modify (r to r1),
`Delete (r1)
`
`There should be Insert entries with
`“r values in the stack.
`There should be no entries for “r
`in the stack.
`There should be Insert entries with
`r1 walues
`There should be no entries for “r
`or “r1 in the stack.
`There should be Delete entries with
`“r values
`There should be Modify entries with
`“r to r1 values in the stack.
`There should be Modify entries with
`“r to r2 values in the stack.
`There should be Delete entries with
`“r values
`
`15
`
`2O
`
`25
`
`30
`
`35
`
`40
`
`If one observe that a Modify (r to r1) is equivalent with
`Delete (r). Insert (r1), the table will look like (cf. Table D):
`
`Transaction
`
`insert (r)
`
`insert (r), Delete (r)
`
`insert (r), Delete (r),
`insert (r1)
`insert (r), Delete (r),
`insert (r1), Delete r1)
`Delete (r)
`
`Delete (r), Insert (r1),
`
`Delete (r), Insert (r1),
`Delete (r1), Insert (r2)
`Delete (r), Insert (r2),
`Delete (r2)
`
`The check and operands.
`
`There should be Insert entries with
`“r values in the stack.
`There should be no entries for “r
`in the stack.
`There should be Insert entries with
`r1 walues
`There should be no entries for “r
`or “r1 in the stack.
`There should be Delete entries with
`“r values
`There should be Modify entries with
`“r to r1 values in the stack.
`There should be Modify entries with
`“r to r2 values in the stack.
`There should be Delete entries with
`“r values
`
`The pair Insert (n), Delete (n) demonstrates that we need
`not to put entries in the Check Stack for Such pairs according
`to Table 1. Therefore we can ignore Stack entries from the
`DMLS marked gray in Table 2.
`The inventive method must therefore advantageously
`delete stack entries from an Insert(n) when a DML Delete(n)
`occurs as the next DML.
`In order to detect an Insert Delete sequence on a stack
`with entries related to many different Table types, and differ
`ent Table occurrences, we have to identify both.
`Therefore the stack need a Table--Rowid entry and the
`DML originator.
`In order to distinguish stack entries belonging to different
`parallel transactions we also have to add a transaction iden
`tifier. Since nested transactions upon one database, from the
`same process, are forbidden, the transaction identifier may be
`the ID of the process issuing the transaction. We will call it
`PID.
`The modified stack will formally look like (cf. Table E):
`
`TABLE E
`
`Modified stack
`
`PID Table
`
`Rowid Origin
`
`Column(s) Value
`to check
`to check The check
`
`Message
`
`Case: 1:20-cv-02032-DCN Doc #: 1-1 Filed: 09/10/20 10 of 15. PageID #: 25
`
`T1
`
`1
`
`1
`
`2
`
`2
`
`1
`
`INSERT T1, C1,
`C2, ...
`INSERT T2, C1,
`C2, ...
`
`INSERT T2, C1,
`C2, ...
`INSERT T1, C1,
`C2, ...
`
`t1Value LessThan2
`
`t1Value OneOrMore
`
`t2Value LessThan2
`
`t2Value OneOrMore
`
`Duplicate
`of T1
`Equal value
`missing in
`T2
`Duplicate
`of T2
`Equal value
`missing in
`T1
`DELETE Tmember, Original OneOrMOwn T3 value is
`C1, C2,
`t3Value
`used in
`Tmember
`
`

`

`US 7,502,791 B2
`
`TABLE F
`
`code for finding all entries belonging to a single DML
`
`DML key. PID = value;
`DML key. Table = value;
`DML key. Rowid = value;
`DML key. Origin="DML":
`status = eDB OBT(“Constraint Stack”, “DML key);
`
`10
`if an Supporting index for (c1 c2, ...) are established in the
`In order to find previous entries that should be removed
`(Insert Delete), it is practically to be able to find the entries
`eDB database. Therefore all Subset Constraints will be sup
`ported by an index Structure for the Subset “owner.
`to be removed, by using Column values that should match as
`a key in the Stack.
`OneOrMOwn:
`If a Delete (T1) was issued after the stack has been estab
`For the previous value set (v1, v2. . . . ) for the Column
`lished as shown above, all Insert (T1) entries should be
`combination (c1 c2, ...) in the "owner, find any “member
`removed.
`with current value set (V1,V2,...) for the Column combina
`This is equivalent to all entries with PID=1, Table-T1,
`tion (c1 c2, ...). If any—are there still at least one “owner
`Rowid=1 and Origin="INSERT.
`that satisfy the value set. Therefore all Subset Constraints will
`& G
`99
`Therefore PID, Table, Rowid and Origin is selected as key, 10
`be supported by an index Structure for the Subset “member.
`from now on called the DML-key.
`In general, all set oriented Constraints will be supported by
`indices or constructs called projections.
`Implementation of the Check Stack
`Column in the Check Stack, and the OneOrMOwn dem
`Stack handling considerations.
`Note that in order to delete an Insert entry in the Check 15 onstrates the need for both the “owner and the “member
`Stack Delete from the stack they will from the el B point of
`index. Projections can replace owner indices in the described
`view use the DML-key.
`algorithm. Projections are a key-tuple with a counter added.
`In eIDB the Check Stack will be implemented as entries in
`The Stack Col
`“Columns to Check” can be one ore
`an Index Structure.
`All
`ies belongi
`ingle DML is foundbv (cf. Tabl
`more columns from one single Table.
`F)
`entries belonging to a S1ngle
`is foundby (cf. Table 20
`However, the supporting index implicitly “declares the
`columns.
`Shown later, some tests have to be executed by more than
`one function. And the next function may be dependent upon
`25 the previous function. By including a serial number called
`Testno, functions that constitute a test can be identified by
`havi
`1 Test
`aV1ng equal lesuno.
`Furthermore, since functions in a multifunction test may be
`dependent they have to be ordered by a Seqno, which is
`included
`11
`so included as well.
`The expanded DML-key is: PID, Table(this), Rowid, Ori
`gin, Testino and Seqno.
`All entries belonging to a single DML is then found by a
`sub key of the DML-key (Major k