O I
`
`— LO 9‘
`0- CO ’3;
`5
`“3. CO -—-—_:;0
`-_-; g g:
`c v- Eco
`a: £0
`i ‘— “g
`
`REISSUE PATENT APPLICATION TRANSMITTAL
`
`‘ ddress to:
`
`9 "
`
`Assistant Commissioner for
`‘ Patents
`0 PD. Box 1450
`Arlington, VA 223134450
`
`Attorney Docket No.
`.
`Flrst Named Inventor
`.
`.
`Orlglnal Patent No.
`Original Patent Issue Date
`
`83145
`
`Doktor
`
`5 826 259
`October 20 1998
`
`Ex-ress Mail Label No.
`
`V70048737$i7
`
`,7
`
`llllllilliillililllllll
`
`APPLICATION FOR REISSUE OF:
`Check a olicable box
`APPLICATION ELEMENTS 37 CFR 1.173
`
`Plant Patent
`Design Patent
`L Utility Patent
`ACCOMPANYING APPLICATION PARTS
`
`1. A Fee Transmittal Form (PTO/SB/56)
`(Submit an original and a duplication for fee processing)
`
`2.
`
`X Applicant claims small entity status. See 37
`CFR 1.27.
`
`.
`
`.
`
`Statement of status and support for all
`changes to the claims. See 37 CFR 1.173(c).
`
`Original US. Patent for surrender
`Ribboned Original Patent Grant
`Statement of Loss (PTO/SB/55)
`
`12. _ Foreign Priority Claim (35 use 119)
`if applicable)
`ountry:
`Application No.:
`Filing Date:
`The certified copy has been filed in
`prior application Serial No.
`filed
`on
`
`_ Information Disclosure Statement
`(lDS)/PTO-1449 and Copies of IDS
`Citations
`
`14.
`
`15.
`
`English Translation of Reissue
`Oath/Declaration (if applicable)
`
`Preliminary Amendment
`
`16. X
`
`Return Receipt Postcard (MPEP 503)
`(Should be specifically itemized)
`
`Other: Please associate this application
`17. X
`with Customer No. 27975
`
`
`
`3. L Specification and Claims in double column
`copy of patent format (amended. if
`appropriate)
`
`4. X_ Drawing(s) (proposed amendments. if
`appropriate)
`
`5. L Reissue Oath/Declaration (original or copy)
`(37 CFR 1.175) (PTO/SB/51 or 52) (3 items)
`
`6. _ Power of Attorney
`
`7. X_ Original US. Patent currently assigned?
`X
`Yes
`No
`(If Yes, check applicable box(es))
`X
`Written Consent of all Assignees (PTO/$8153)
`X
`37 CFR 3.73(b) Statement (PTO/SB/96)
`
`8.
`
`9.
`
`CD-ROM or CD-R in duplicate, Computer Program
`(Appendix) or large table
`
`Nucleotide and/or Amino Acid Sequence
`submission (if applicable. all of the following
`are necessary)
`a.
`Computer Readable Form (CFR)
`b.
`Specification Sequence Listing on:
`I.
`CD ROM or CD—R (2 copies) or
`ii.
`paper
`
`_.. ||||I||l|I||llllllllllllll||l| 27975
`
`above copies
`
`PATENT TRADEMARK OFFICE
`
`Respectfully submitted,
`
`DAVID L. STEWART
`
`Reg. No. 37,578
`Allen, Dyer, Doppelt, Milbrath
`& Gilchrist, PA.
`255 S. Orange Ave., Suite 401
`Post Office Box 3791
`
`Orlando. Florida 32802
`Phone: 407-841-2330
`
`001
`
`IBM EX. 1015
`
`001
`
`

`

`REISSUE APPLICATION FEE
`TRANSMITTAL FORM
`
`PTO/SB/56
`
`Attorney Docket No.
`
`83145
`
`Claims
`in Patent
`
`(A)
`(C)
`
`Total
`
`Claims
`Indep.
`Claims
`
`Claims as Filed — Part 1
`
`Number Filed in
`Reissue
`Ao olication
`
`(3)
`Number
`Extra
`
`Large Entity
`
`_
`
`“3’ 18’20‘ — “8’
`_
`_
`(D)
`23—
`X84—
`BASIC FEE
`
`_
`
`$700.00
`
`
`
`TOTAL FEE
`
`$700.0.
`
`Claims as Amended — Part 2
`
`(1)
`Claims
`Remaining After
`Amendment
`
`(3)
`(2)
`V
`Highest Number Number Extra
`Previously Paid
`For
`
`Large Entity
`
`Total
`
`Indep.
`
`_m—nu
`-_-——m
`
`_
`
`TOTAL ADDITIONAL FEE
`
`* If the entry in (D) is less than the entry in (C), Write “0" in column 3.
`** if the “Highest Number of Total Claims Previously Paid For" is less than 20, Write “20" in this space.
`*** After any cancellation of claims.
`**** If “A” is greater than 20, use (B-A); if “A" is 20 or less, use (B-20).
`***** “Highest Number of Independent Claims Previously Paid For" or Number of Independent Claims
`in Patent (C).
`
`X
`
`X
`
`Please charge the attached credit card payment form in the amount of $700.00 .
`A duplicate copy of this sheet is enclosed.
`
`The Commissioner is hereby authorized to charge any additional fees under
`37 CFR 1.16 or 1.17 which may be required, or credit any overpayment to
`Deposit Account No. 01-0484.
`A duplicate copy of this sheet is enclosed.
`
`JUN 14 2005
`
`Date
`
`David L. Stewart
`
`Reg. No. 37,578
`
`002
`
`002
`
`

`

`I)
`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`
`In re Patent Application of:
`DOKTOR
`
`Serial No. NOT YET ASSIGNED
`
`Filing Date: HEREWITH
`
`Attny. Docket No.
`83145
`
`VVVVVVVV
`
`vv
`
`For: EASILY EXPANDABLE DATA
`PROCESSING SYSTEM AND METHOD
`
`TRANSMITTAL OF FORMAL DRAWINGS
`
`Commissioner of Patents
`P.O. Box 1450
`
`Alexandria, VA 22313-1450
`
`Sir:
`
`Enclosed are nineteen (19) sheets of formal drawings filed concurrently with
`
`the above identified patent application
`
`Respectfully submitted,
`
`@—
`
`DAVID 'L. STEWART
`
`Reg. No. 37,578
`
`
`
`|||||ll||
`
`
`
`|||
`
`
`
`||lll||||| ||||
`
`
`
`
`- PATENT TRADEMARK OFFICE
`
`27975
`
`Telephone: (321) 725-4760
`
`003
`
`003
`
`

`

`n
`
`Attorney Docket No. 83145
`
`US. PATENT APPLICATION FOR
`
`REISSUE OF US. PATENT 5,826,259 ENTITLED
`
`EASILY EXPANDABLE DATA PROCESSING SYSTEM AND METHOD
`
`********************************
`
`INVENTOR:
`
`Karol Doktor
`
`29 Belinda Cresent
`
`Wheelers Hill, Australia 3150
`
`Citizenship: Australian
`
`PREPARED BY:
`
`David L. Stewart
`
`.
`
`Allen, Dyer, Doppelt, Milbrath
`& Gilchrist, PA.
`255 South Orange Avenue
`Suite 1401
`
`Orlando, Florida 32801
`
`004
`
`004
`
`

`

`1 .
`EASILY EXPANDABIE DATA PROCESSING
`SYSTEM AND METHOD
`
`5,826,259 ,
`
`2
`
`This application is a continuation of application Ser. No.
`' 08/439,207, filed May 11, 1995. now US. Pat No.'5.675.
`
`779, which is a divisional of Ser. No. [08/083,361] 08/083 861,
`
`filed Jun. 28, 1993, now [issued;] US. Pat. No. 5 604 899 which:
`. issued on Feb. 18, 1997, which is a continuation of Ser. No.
`07/526,424, filed May 21, 1990, now abandoned
`BACKGROUND OF THE INVENTION
`
`5
`
`10
`
`Cross Reference to Microfiche Appendix
`
`This application includes a plurality of computer program
`listings (modules) in the form of a Microfiche Appendix
`which is being filed concurrently herewith as 1162 frames
`(not counting target and title fi'ames) distributed over 20
`sheets of microfiche in accordance with 37 C.F.R. § 1.96.
`The disclosed computer program listings are incorporated
`into this quecification by reference but it should be noted that
`the source code ‘and/or the resultant object code of the
`disclosed program modules are subject to copyright protec-
`tion. The copyright owner has fro-objection to the facsimile
`reproduction by anyone of the patent document (Or
`the
`‘ patent disclosure as it appears’in the files or records of the
`' US. Patent and Trademark Ofiice) for the sole purpose of
`studying the disclosure but otherwise reserves all other
`rights to the disclosed computer program modules including
`the right to reproduce said computer program modules in
`machine-executable form.
`
`Field of Invention
`
`The present invention relates generally to computer data—
`base management systems and more @ecifically to appara—
`tus and methods for modifying and searching through large
`scale databases at high speed.
`'
`'
`
`Description of Related Art ,
`
`15
`
`30
`
`35
`
`positioned such that each card is directly adjacent to no more
`than two others (for each typical examination there is a
`preceding card, the card under examination and a following
`card in the stack). On the fiont surface of each index card a
`librarian enters, in left to right sequence; the last name of an
`author, the first name of the author, the title of a single book
`which the author wrote and a shelf number indicating the
`physical location within the library where the one book may
`be found. Each of these four entries may be referred to as a
`“column” entry. Sufficient surface area must be available on
`each card- to contain the largest of conceivable entries.
`After the entries are made, the index cards are stacked one
`after the next in alphabetical order, according to the author’s
`last name and then according to the author’s first name and
`then by title. This defines a “key—sequenced” type of data-
`base Whose primary sort key is the author’s name. The
`examination position of each card is defined relative to the
`contents of preceding and following cards in the stack. That
`is, when cards are examined, each intermediate card is
`examined immediately after its alphabetically preceding
`card and immediately-before its alphabetically succeeding
`card. When a new book is acquired,
`the key-sequenced
`database is easily “updated” by inserting a new card between
`two previously created cards. Similarly, if a book is removed
`from the collection, its card is simply pulled from the card
`stack to reflect the change.
`If a hbrary user has an inquiry respecting the location of
`a particular book or the titles of several books written by a
`named author, the librarian may quickly search through the
`alphabetically ordered set of index cards and retrieve the
`requested information. However, if a library user has an
`inquiry which is not keyed to an author’s name, the search
`and retrieval process can require substantially more time; the
`worst case scenario being that for each inquiry the librarian
`has to physically sift through and examine each card in the,
`entire catalog. As an example of such a scenario, suppose
`that an inquiring reader asks for all books in the library
`where the author’s first name is John and the title 'of the book
`contains the word “neighbor” or a synonym thereof.
`Although it is conceptually possible to answer this inquiry
`using the information within the catalog, the time for such
`a search may be impractically long, and hence, while the
`information is theoretically available, it is not realisticall
`accessible,
`.-
`To handle the more common types of inquiries, libraries
`often keep redundant sets of index cards. One set of cards is
`sorted according to author names and another set is sorted
`according to the subject matter of each book. This form of -
`redundant storage is disadvantageous because the size of the
`card catalog is doubled and hence, the cost of information
`storage is doubled. Also, because two index cards must be
`generated for each new book added to the collection the cost
`of updating the catalog is also doubled.
`The size of a library collection tends to grow over time as
`more and more books are acquired. During the same time,
`more and more index cards are added to the catalog. The
`resulting stack of cards, which may be viewed as a kind of
`“database”, therefore grows both in size and in worth. The
`“worth” of the card-based system may be defined in part as
`the accumulated cost of all work that is expended in creating
`‘ each new index card and in inserting the card into an
`appropriate spot in the stack
`As time- goes by, not only does the worth and size of the
`database grow, but new technologies, new rules, new
`services, etc., begin to emerge and the information require—
`ments placed on the system change. Some of these changes
`
`Modern computer systems are capable of storing volumi—
`nous amounts of information in bulk storage means such as
`magnetic disk banks. The volume of stored information can
`be many times that of the textual information stored in a
`conventional encyc10pedia or in the telephone directory of a
`large city. Moreover, modern computer systems can- sift
`through the contents of their bulk storage means at
`extremely high speed, accessing as many as one million
`bytes of informan'on or more per second (a byte is a string
`of eight bits, equivalent to approximately one character of
`text in layman’s terms). Despite this capability, it may take
`an undesirably long time (i.e., hours or’ days) to retrieve
`desired pieces of information. In commercial settings such
`as financial data storage facilities, there will be literally
`billions of pieces of information that could be sifted through
`before the right one or more pieces of information are found.
`Thus, even at speeds of one million examinations per
`second, it can take thousands of seconds (many hours) to
`retrieve a desired piece of information. Efficient organiza-
`tion of the stored information is needed in order to minimize
`retrieval time.
`i
`
`60
`
`The methods by which pieces of information are orga—
`nized within a computer, searched through or reorganized,
`.often parallel techniques used by older types _of manual
`information processing systems. Awell known example of
`a manual system is the index card catalog found in public _
`libraries. Such a card catalog consists of a large number of 65
`uniformly dimensioned paper cards which are serially
`stacked in one or more trays. The cards are physically
`
`45'
`
`50
`
`$5
`
`-
`
`005
`
`005
`
`

`

`5,826,259
`
`3
`may call for a radical reorganization of the card catalog
`system. In such cases, a great deal of work previously
`expended to create the catalog system may have to be
`discarded and replaced with new work.
`For the sake of example, let it be supposed that the library
`acquires a new microfilm machine which stores copies of a
`large number of autobiographies. The autobiographies dis-
`cuss the life and literary works of many authors whose books
`are kept in the library. Let it further be supposed that the
`original, first card catalog system is now required to cross
`reference each book to the microfilm location (or plural
`locations) of its author’s (or plural authors’) autobiogra-
`phies. In such a case, the card catalog system needs to be
`modified by adding at least one additional column of infor-
`mation to each index card to indicate the microfilm storage
`locations of the relevant one or more autobiographies.
`We will assume here that there is not enough surface area
`available on the current index cards for adding the new
`information. Larger cards are therefore purchased, the infor-
`mation from the old cards is copied to the new cards, and
`finally, the new microfilm cross referencing information is
`added to the larger cards. This type of activity will be
`referred to here as “restructuring” the database.
`Now let us suppose,
`that as more time goes by, an
`additional but previously unanticipated, cross indexing cat-
`egory is required because of the introduction of a newer
`technology or a new government regulation. It might be that
`the just revised and enlarged second card system does not
`have the capacity to handle the demands of the newer
`technology or regilation. In such a situation, a third card
`system has to be constructed from scratch. The value of
`work put into the creation of the just-revised second system
`is lost. As more time passes and further changes emerge in
`technology, regulations, etc., it is possible that more major
`organizational changes will have to be made to the catalog
`system. Time after time, a system will be built up only to be
`later scrapped because it fails to anticipate a new type of
`information storage and retrieval operation. This is quite
`wasteful.
`
`Although computerized database systems are in many
`ways different
`from manual systems,
`the computerized
`information storage and retrieval systems of the prior art are
`analogous to manual systems in that
`the computerized
`databases require similar restructuring every time a new
`category of information relationships or a new type of
`inquiry is created.
`At a fundamental level, separate pieces of information are
`stored within a computerized database system as a large
`number of relatively short strings of binary bits where each
`string has finite length. The bit strings are distributed spa-
`cially within a tangible medium of data storage such as an
`array of magnetic disks, optical devices or other information
`representing means capable of providing mass storage. Each
`bit is represented by a magnetic flux reversal, an optical
`perturbation and/or some other variance in the physical
`attributes of a data storage medium. A transducer or ampli-
`fier means converts these variances into signals (e.g.,
`electrical, magnetic, or optical) which can be processed on
`a digital data processing machine. Each string of bits is often
`uniquely identified by its physical location or by a logical
`storage address. Some bit strings may function as address
`pointers, rather than as the final pieces of “real” information
`which a database user wishes to obtain. The address pointers
`are used to create so-called “threaded list” organizations of
`data wherein logical
`links between a first
`informational
`“object” (first piece of real data) and a second informational
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`“object” (second piece of real data) are established by a
`chain of direct or indirect address pointers. The user-desired
`objects of real information themselves can be represented by
`a collection of one or more physically or logically connected
`strings.
`Typically, “tables” of information are created within the
`mass storage means of the computerized system. A horizon-
`tal “row” of related objects, which is analogous to a single
`card in a card catalog system, may be defined by placing the
`corresponding bit strings of the objects in physical or
`address proximity with each other. Logical interconnections
`may be defined between dilferent rows by using ancillary
`pointers (which are not considered here as the “real” data
`sought by a database user). A serial sequence of “rows”
`(analogous to a stack of cards) is then defined by linking one
`row to another according to a predefined sorting algorithm
`using threaded list techniques.
`linking “threads” may be
`A vast number of different
`defined in this way through a database table having millions
`or billions of binary information bits. Unlike manual
`systems,
`the same collection of rows (which replaces the
`manual stack of cards) can be simultaneously ordered in
`many difierent ways by utilizing a multiplicity of threaded
`paths so that redundant data storage is not necessary.
`Searches and updates may be performed by following a
`prespecified thread from one row to the next until a sought
`piece of information (or its address) is found within a table.
`A threaded-list type of table can be “updated" in a manner
`similar to manual card systems by breaking open a logical
`thread within the list, at a desired point, and inserting a new
`row (card) or removing an obsolete row at the opened spot.
`Tables are often constructed according to a “key-
`sequenced” approach. One column of a threaded-list table is
`designated as the sort-key column and the entries in that
`column are designated as “sort keys”. Address pointers are
`used to link one row of the table to another row according
`to a predefined sequencing algorithm which orders the
`entries (sort-keys) of the sort column as desired (i.e.,
`alphabetically, numerically or otherwise). Once a table is so
`sorted according to the entries of its sort column, it becomes
`a simple task to search down the sort column looking for an
`alphabetically, numerically or otherwise ordered piece of
`data. Other pieces of data which are located within the row
`of each sort key can then be examined in the same sequence
`that each sort key is examined. Any column can serve as the
`sort column and its entries as the sort keys. Thus a table
`having a large plurality of columns can be sorted according
`to a large number of sorting algorithms.
`The key-sequencing method gives tremendous flexibility
`to a computerized database but not without a price. Each
`access to the memory location of a list-threading address
`pointer or to the memory location of a sort-key or to the
`memory area of “real” data which is located adjacent to a
`sort-key takes time. As more and more accesses are required
`to fetch pointers and keys leading to the memory location of
`a piece of sought-after information (“real data”),
`the
`response time to an inquiry increases and system perfor-
`mance sufiers.
`
`There is certain class of computerized databases which
`are referred to as “relational databases". Such database
`systems normally use threaded list techniques to define a
`plurality of key-sequenced “tables”. Each table contains at
`least two columns. One column serves as the sort column
`while a second or further columns of the table store either
`the real data that is being sought or additional sort—key data
`which will ultimately lead to a sought-after piece of real
`
`006
`
`006
`
`

`

`‘1
`
`5,826,259
`
`5
`data. The rows of the table are examined in an ordered
`fashion according to the contents of the sort column. Target
`data is located by first threading down the sort column and
`thus moving through the chain of rows within a table
`according to a prespecified sort algorithm until a specific
`sort-key is found. Then the corresponding row is examined
`horizontally and the target data (real data or the next key) is
`extracted from that row.
`
`An example of “real” data would be the full-legal names
`of unique persons such as in the character strings, “Mr.
`Harry W. Jones”, “Mrs. Barbara R. Smith”, etc. The sort-key
`can be a number which is stored adjacent to the full name
`and which sequences the names (real data) according to any
`of a wide variety of ordering patterns including by age, by
`height, by residential address, alphabetically, etc. Because
`the real data (e.g., full name of a person) is stored in a
`separate column, it is independent from the sort key data. A
`large variety of dilferent relations can therefore be estab-
`lished between a first piece of real data (e.g., a first person’s
`name) and a second piece of real data (e.g., a second
`person’s name) simply by changing the sort keys that are
`stored in the separate sort column (e.g., who is older than
`whom, who is taller, etc.). Plural orderings of the real data
`can be obtained at one time by providing many columns in
`one table, by storing alternate keys in the columns and by
`choosing one or more of these columns as the primary sort
`key column.
`Relational database systems often include tables that do
`not store real data in a column adjacent to their sort-key
`column, but rather store a secondary key number which
`directs a searcher to a row in another key-sequenced table
`where a matching key number is held together with either a
`piece of sought~after real data or yet another forward refer-
`encing key number (e.g., an entry which in effect says “find
`the row which holds key number x of yet another table for
`further details”). With this indirect key-sequenced approach,
`a large number of tables can be simultaneously updated by
`changing one entry in a “base” table.
`Relational database tables are normally organized to
`create implied set and subset “relations” between their
`respective items of pre-stored information. The elements of
`the lowest level subsets are stored in base tables and higher
`level sets are built by defining, in other tables, combinations
`of keys which point to the base tables. The implied relations
`between elements cannot be discerned by simply inspecting
`the raw data of each table. Instead, relations are flushed out
`only with the aid of an access control program which
`determines in its randomly-distributed object code, which
`table to examine first and what column to look at before
`beginning to search down the table’s column for a key
`number and, when that key number is found, what other
`column to look at for the real data or a next key number.
`Relations between various “entities” of a relational database
`are implied by the sequence in which the computer accesses
`them.
`
`By way of a concrete example, consider a first relational
`table (Names-Table) which lists the names of a large number
`of people in telephone directory style. Each name (each
`separate item of real data) is paired to a unique key number
`and the rows of this Names-Table are sorted sequentially
`according to the key number. Asecond relational table may
`be provided in the database (Cars-table) which lists auto-
`mobile (vehicle) identification numbers (VIN) each paired in
`its row with a second key number. If the second key number
`is matched by a corresponding key number in the first table,
`then a relationship might be implied between the entries of
`the two separate tables (Names-Table and Cars-Table). The
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`“implied" relationship might be one of an infinite set of
`possibilities. The relationship could be, for example, that the
`car listed in the second table is “owned” by the person whose
`name is found next to a matching key in the first table. On
`the other hand, it might be implied that the matched person
`in the first table “drives” the car, or “cleans” the car or has
`some other relation to the car. It is left to the access control
`program to define what the relationship is between entities
`in the first table and entities in the second table.
`
`It can be seen that relational database systems offer users
`a great deal of flexibility since an infinite number of relations
`may be defined (implied). Economy in maintaining
`(updating) the database is also provided-since a change to a
`base table propagates through all other tables which refer-
`ence the base table. The access control program of the
`database system can include information-updating modules
`which, for example, change the key number in the second
`table (Cars-Table) whenever ownership of a car changes. If
`the name of the new owner is already in the first table
`(Names-Table), it does not have to be typed a second time
`into a new storage area and thus, extra work and storage
`redundancy are avoided. The vehicle identification number
`(VIN) remains unchanged. Minimal work is thus expended
`on updating the database.
`Despite these advantages, relational database systems
`sufier from expandability and restructuring problems similar
`to those of the above—described manual system. Sometimes
`the rows within a particular table have to be altered to add
`additional columns. This is not easily done. Suppose for
`example, that a new government regulation came into being,
`mandating that vehicles are to always be identified not only
`by a vehicle identification number (VIN) but also by the
`name and location of the factory where the vehicle was
`assembled. If spare columns are not available in the Cars-
`Table, the entire database may have to be restructured to
`create extra room in the storage means (i.e. the disk bank)
`for adding the newly required columns. New key numbers
`will have to be entered into the new columns of each row
`(e.g., a new “factory of assembly” key number) and sorted
`in order to comply with the newly mandated regulation. New
`search and inquiry routines will have to be written for
`handling the newly structured tables.
`In the past, much of this restructuring work was done by
`reprogramming the computer at the object code or source
`code level. This process relied heavily on an expert pro-
`gramming staff. It was time consuming, costly and prone to
`programming errors. Worst of all, it had to be redone time
`and again as new informational requirements emerged just
`after a last restructuring project was completed. There is a
`need in the industry for a database management system
`which provides quick responses to inquiries and which can
`also be continuously updated or restructured without repro—
`gramming at the source or object code level.
`SUMMARY OF THE INVENTION
`
`It is an objective of the present invention to provide a
`database system which is capable of storing voluminous
`amounts of information, sifting through the information at
`high speed, and is at the same time easily expandable or
`restructurable to take on new forms of entities and relation-
`ships.
`In accordance with a first aspect of the invention, an entity
`definition table (ENTDEF) is defined within the memory
`means of a computer system to store the name of an allowed
`entity type (class) and the name of a single other table
`(Entity-instances Table or “EiT” for short) where instances
`
`007
`
`007
`
`

`

`ll
`
`5,826,259
`
`7
`of the allowed entity type may be stored. A separate rela-
`tionships definition table (RELDEF) is defined in the
`memory means to list in each row of the table: (a) the name
`of an allowed relations type, (b) the name of a single
`Relation-instances Table (RiT) where instances of the
`allowed relationship type may be stored, (c) the name of a
`primary (head) entity type to which the relation type may
`apply and (d) the names of one or more secondary (tail)
`entity types to which the named relationship may apply.
`Each row of the Relation-instances Table (RiT) is provided
`with at least one primary pointer which points to the storage
`location of a first instance of the primary entity type and at
`least one secondary pointer which points to the storage
`location of a corresponding first instance of the secondary
`entity type. Each row of the Relation—instances Table (RiT)
`further includes a pointer to a relationship-defining row in
`the RELDEF table. The pointer can be the name of an
`applicable relation type as recorded in the RELDEF table.
`Relationships between instances of a primary entity and a
`secondary entity are thus expressly defined by entries in the
`Relation-instances Table (RiT). Adding new rows to this
`Relation-instances Table (RiT) allows for the addition of
`new relations. Adding new rows to the RELDEF table
`allows for the creation of new classes (types) of relation-
`ships. Since relation-defining tables can be updated using a
`fixed set of update modules, reprogramming at the source or
`assembly level is not needed for restructuring the schema of
`the database.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`The invention will be described with reference to the
`following figures in which:
`FIG. 1A is a block diagram of a conventional database
`system.
`FIG. 1B is a timing diagram showing the delay between
`the addressing and the delivery of storage data.
`FIG. 2A is a block diagram of a conventional key-
`sequenced table organization.
`FIG. 2B is a block diagram of a conventional relative-
`record table organization.
`FIG. 3 diagrams a multiple table system whichis based on
`a conventional relational database approach and which has
`key-sequence organized tables.
`FIG. 4A is a conceptual diagram illustrating an entity-
`relation schema in accordance with the invention.
`
`FIG. 4B is a further conceptual diagram of an entity-
`relation schema according to the invention.
`FIG. 5 is a block diagram of an entity definition
`(ENT.DEF) table in accordance with the invention.
`...:
`.I. 2-::.._ In")! nnm ...L1.. _ ......._.I.._....
`FIGS. 6A and 6B are block diagrams of a relationship
`
`8
`carrying out the invention. It is to be understood that these
`modes are merely exemplary of the invention. The detailed
`description is not intended to be taken in a limiting sense.
`Referring to FIG. IA, the block diagram of a conventional
`database system 100 is shown. The database system 100
`comprises a central processing unit (CPU) 110 which is
`operatively coupled so as to be controlled by an access
`control program (object code) 120d stored in a first memory
`means 120 (i.e., read-only-memory, ROM, or random access
`memory, RAM). The CPU 110 in combination with the first
`memory means 120 can be viewed as one or more machine
`means for performing functions specified by the object code
`120d. The CPU 110 is further operatively coupled to access
`the data 130d of a “bulk storage” second memory means 130
`also included in the database system 100. Individual strings
`of digital information are represented by wiggled lines (e.g.,
`120d, 130d ) in FIG. 1A. The bulk storage means 130
`typically takes the form of a large array of magnetic disk
`drives,
`tape drives, or other mass storage devices (e.g.,
`arrays of Dynamic Random Access Memory [DRAM]
`chips). The first (control) memory means 120 usually takes
`the form of high speed RAM and/or ROM.
`To access a particular string of data 130d stored within the
`bulk storage means 130,
`the CPU 110 must provide a
`corresponding address signal 1315 (FIG. 1B) in the form of
`logic highs (H) and lows a.) to the bulk storage means 130
`over an address bus 131. As seen in the time versus
`logic-level graph of FIG. 1B,
`the address signal 131:
`(usually an electrical signal) comprises a set of logic high
`and logic low levels (H and L) transmitted in a first time
`period to—tl. There follows a second time period,
`t1—t2,
`which is often referred to as an‘‘access delay", during which
`. addressing circuits attempt to access the addressed memory
`location. Depending on whether a memory read or memory
`write operation is occurring, data signals 1325 are then
`transferred over a data bus 132 (FIG. 1A) from the addressed
`location within the bulk storage means 130 to the CPU 110
`or vice versa during a following third time period, tz—ta.
`Referring still to FIG. 1A, the object code 120d of the
`access control program determines when and how the CPU
`110 will access information 130d stored in the bulk storage
`means 130. The CPU 110 issues address signals 1215 (not
`shown) over an address bus 121 to the first memory means
`120, and in response, the first memory means 120 supplies
`instruction signals 1225 (not shown) over a data bus 122 to
`the CPU 110. Information signals 1223 can be exchanged
`bidirectionally over data bus 122 between the CPU 110 and
`the first memory means 120. FIG. 1B may represent the
`timing relation between address signals 1215 and first
`memory information signals 1225 by replacing reference
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`008
`
`008
`
`

`

`5,826,259
`
`9
`through a first translation machine which may