l‘l
`
`. r'
`(Sm. Bus. §l.60)i
`
`n
`
`Docket No.: M—1226-5C US
`
`llllllllllllllllllllllllllllllllll,‘70976U.S.PTO
`
`05/22/97
`
`
`
`
`
`......
`
`DIVISION—CONTINUATION PROGRAM APPLICATION TRANSMITTAL FORM
`
`Prior Application
`
`Serial No.:
`
`08/439,207
`
`Filing Date:
`
`05/11/95
`
`Inventor(s)
`
`Doktor, Karol
`
`Assignee:
`
`
`Financial Systems Technology Pty. Ltd.
`
`Examiner:
`
`R. Ho
`
`Group Art Unit:
`
`2307
`
`Title:
`
`A Data Processing System and Method for Maintaining Cardinality in a Relational Database
`
`To the Commissioner of Patents and Trademarks:
`
`This is a request to file a:
`
`continuation
`
`E] divisional
`
`application under 37 CFR 1.60 of the above-named prior application.
`
`Enclosed is a copy of the latest inventor-signed prior application, including the oath or declaration
`showing the signature or an indication it was signed, The enclosed papers are a true copy of the latest
`inventor-signed prior application, including the specification, claims, drawings and oath or declaration, and no
`amendments referred to in the oath or declaration filed to complete the prior application introduced new matter
`therein.
`
`CLAIMS AND FILING FEES
`
`A Preliminary Amendment is enclosed.
`
`El[:1El
`
`Cancel in this application claims __ of the latest inventor-signed prior application before calculating
`the filing fee. (At least one independent claim must be retained for filing purposes.)
`
`Cancel in this application all claims of the latest inventor-signed prior application and substitute the
`claims contained in the attached Preliminary Amendment prior to calculating the filing fee;
`
`Add the additional claims in the attached Preliminary Amendment prior to calculating the filing fee.
`
`355837 v1
`
`
`
`
`
`IBM EX. 1012
`
`001
`
`001
`
`

`

`D
`
`Since the power does not appear in the original papers, a copy of the power in the latest
`inventor-signed prior application is enclosed.
`
`K4
`
`Address all future communications (May only be completed by applicant, or attorney or agent of
`record) to:
`
`Edward C. Kwok
`
`SKJERVEN, MORRILL, MACPHERSON, FRANKLIN & FRIEL LLP
`25 Metro Drive, Suite 700
`San Jose, CA 95110
`
`Telephone No.: 408-453-9200
`
`Facsimile
`
`0.: 408-453-7979
`
`Date:
`
`(-1 LL! Q7
`
`Signature:
`
`
`
`Address of signator:
`
`Reg. No. 33,938
`
`DEED
`
`inventor(s)
`assignee of complete interest
`attorney or agent of record
`attorney for Applicant(s)
`under 37 CPR. § l.34(a)
`
`SKJERVEN, MORRILL, MACPHERSON, FRANKLIN & FRIEL LLP
`25 Metro Drive, Suite 700
`San Jose, CA 95110
`
`
`
`EXPRESS MAIL LABEL NO:
`
`EM425689701US
`
`
`
`355837 vl
`
`_ 3 _
`
`002
`
`002
`
`

`

`\x\
`
`The filing fee is calculated as follows:
`
`m
`
`Number
`
`Filed
`
`Number
`
`Extra
`
`Rate
`
`fig
`
`
`Total Claims
`18
`-20
`=
`0
`x
`$11
`=
`$
`0.00
`Independent
`
`Claims
`2
`-3
`=
`0
`X
`$40
`=
`$
`0.00
`
`
`Basic Filing Fee:
`$
`385.00
`Application contains one or more multiple
`El
`dependent claims ($130 total fee)
`$
`0.00
`
`
`
`
`385.00
`TOTAL FILING FEE:
`$
`
`Please make the following charges to Deposit Account 19—2386:
`
`K4
`
`E]
`
`[4
`
`[XI
`
`Fee for filing the patent application in the amount of
`
`$
`
`
`385 .00
`
`An Extension of Time in the above-named prior application has been requested and the fees therefor
`have been authorized in said application.
`
`The Commissioner is hereby authorized to charge any additional fees which may be required, or credit
`any overpayment to Deposit Account 19-23 86. A Return Receipt Postcard and triplicate copy of this
`sheet are enclosed.
`
`Amend the specification by inserting before the first line the sentence:
`
`This application is a |X| continuation 1:] division of application serial no. 08/439 207, filed May 11,
`1995, which is a divisional of 08/083,361, filed June 28, 1993, now issued, which is a continuation of
`serial no. 07/526,424, filed May 21, 1990, now abandoned.
`
`New drawings are enclosed.
`
`Other enclosures: DIED
`
`Priority of application serial no. __ filed on __ in _ (country) is claimed under 35 USC 119. [j
`The certified copy has been filed in the latest inventor-signed prior application.
`
`Small Entity Declaration/Independent Inventor's Declaration E] has been filed in the latest inventor—
`signed prior application and its benefit under 37 CFR 1.28(a) is hereby claimed; E] is enclosed.
`
`[4
`
`The power of attorney in the above-named prior application is to
`Alan H. MacPherson, (24,423); Thomas S. MacDonald, (17,774); Richard Franklin, (19,128);
`Kenneth E. Leeds, (30,566); Walter J. Madden, Jr., (16,661); Paul J. Winters, (25,246); Brian D.
`Ogonowsky, (31,988); Edel M. Young, (32,451); David W. Heid, (25,875); Gideon Gimlan (31,955);
`Guy W. Shoup, (26,805); Forrest E. Gunnison, (32,899); Norman R. Klivans, (33,003); David H.
`Carroll, (29,903); Ronald C. Fish, (28,843); Janis J. O Biksa (33,648); Edward C. Kwok (33,938);
`Elizabeth E. Leitereg (34,101); Patrick T. Bever (33,834); and B. Noel Kivlin (33,929).
`
`E]
`
`The power appears in the original papers in the latest inventor-signed prior application.
`
`355837 v1
`
`_ 2 _
`
`003
`
`
`
`
`
`
`
`003
`
`

`

`
`
`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`Applicant:
`Karol Doktor
`
`Assignee:
`
`Financial Systems Technology Pty. Ltd.
`
`g
`E
`
`
`
`Title:
`
`A DATA PROCESSING SYSTEM AND METHOD FOR
`MAINTAINING CARDINALITY IN A RELATIONAL DATABASE
`
`Serial No.:
`
`Unknown
`
`Filed: Herewith
`
`Examiner:
`
`Unknown
`
`Group Art Unit: Unknown
`
`Attorney Docket No.: M—1226—5C US
`
`San Jose, California
`May 22, 1997
`
`COMMISSIONER OF PATENTS AND TRADEMARKS
`Washington, D. C.
`20231
`
`PRELIMINARY AMENDMENT
`
`Sir:
`
`Please amend the above—identified application as indicated
`below:
`
`IN THE TITLE
`
`Please amend the title to ——EASILY EXPANDABLE DATA
`
`PROCESSING SYSTEM AND METHOD——.
`
`IN THE SPECIFICATION
`
`At page 2,
`
`line 10, replace "literally," with
`
`——literally——.
`
`At page 17,
`
`line 16, replace "proximity" with ——proximity
`link——.
`
`At page 17,
`.
`
`line 11, replace "proximity" with ——proximity
`link——.
`
`At page 17,
`
`line 13, replace "proximity" with ——proximity
`link——.
`
`At page 32,
`
`line 36, replace "owner" with ——owning——.
`
`At page 36,
`
`line 33, replace "RTD" with ——RTO——.
`
`At page 39,
`
`line 21, replace "REL—DEF" with —eREL.DEF——.
`
`At page 41,
`
`line 22, replace "enterthe" with ——enter
`
`the——.
`
`At page 43,
`
`line 14, replace "invetnion" with
`
`——invention——.
`
`LAW OFFICES OF
`SKJERVEN, MORRILL,
`Mnl‘l’flERSON, FRANKLW
`8L FRIEL
`25 METRO DRIVE
`SUITE 700
`SAN JOSE. CA 95110
`(408) 453-9200
`FAX (403) 453.7979
`
`‘ P:\DMS\5491\M—12265C\0215679 .WP
`
`004
`
`004
`
`

`

`PATENT
`
`At page 45,
`
`line 23, replace "AD.4)" with ——AD.4;——.
`
`At page 50,
`
`line 7, replace "FEL.DEF" with ——REL.DEF——.
`
`At page 50,
`
`line 10, replace "REF.DEF“ with ——REL.DEF——.
`
`At page 53,
`
`line 9, replace "entity.
`
`(i.e-" with ——entity
`
`(i.e.——.
`
`At page 55,
`
`line 1, replace "applicationprogram" with
`
`——application program——.
`
`-
`
`At page 57,
`
`line 9, replace "question,?.??" with
`
`
`
`——question,
`
`?.??——.
`
`EALIEE_QLALM§
`
`Please cancel Claims 1—14 without prejudice.
`
`Please add the following new claims:
`
`——15.
`
`A method for retrieving a desired entity of a
`
`desired entity type from a relational database, wherein said
`
`desired entity is related to a provided entity by a provided
`
`relation type associating an entity type of said provided
`
`entity with said desired entity type, said method comprising:
`
`retrieving a specific relation type record defining
`
`said provided relation type from a relation definition
`
`table;
`
`retrieving a specific relation instance record
`
`defining a relation of said provided relation type between
`
`said provided entity and said desired entity from a
`
`relation instance table corresponding to said specific
`
`relation type record;
`
`retrieving a desired entity type record containing
`
`said desired entity type from an entity definition table,
`
`wherein said desired entity type record specifies a
`
`desired entity instance table associated with said desired
`
`entity type; and
`
`retrieving said desired entity from said desired
`
`entity instance table.
`
`LAW OFFICES or
`stVEN, MORRILL,
`MscPHERSON, FRANKLIN
`& FRIEL
`25 METRO DRIVE
`SUITE 700
`SAN JOSE. CA 95110
`(408) 4539200
`FAX (408) 4534979
`
`P : \DMS\5491\M~12265C\O215679 . WP
`
`- 2 -
`
`005
`
`005
`
`

`

`
`
`PATENT
`
`16.
`
`The method of claim 15, wherein said relation
`
`instance record specifies said desired entity by said desired
`
`entity type and a desired record identifier.
`
`17.
`
`The method of claim 16, wherein said desired entity
`
`is identified by said desired record identifier in said desired
`
`entity instance table.
`
`18.
`
`The method of claim 15, wherein said retrieving a
`
`specific relation type record defining said provided relation
`
`type from a relation definition table comprises:
`
`retrieving a table identifier for said relation
`
`instance table from said specific relation type record;
`
`and
`
`retrieving said specific relation instance record
`
`from said relation instance table based on said specific
`
`relation type record and said provided entity.
`
`19.
`
`The method of claim 15, further comprising retrieving
`
`data specifying said provided relation type from an inquiry
`
`table.
`
`20.
`
`The method of Claim 15, further comprising retrieving
`
`data specifying said provided entity from an inquiry table.
`
`21.
`
`The method of claim 15, further comprising retrieving
`
`a second desired entity type record containing a second desired
`
`entity type from said entity definition table, wherein said
`
`second desired entity type record specifies a second desired
`
`entity instance table associated with said second desired
`
`entity type.
`
`22.
`
`The method of claim 21, further comprising retrieving
`
`a third desired entity type record containing a third desired
`
`LAW OFFICES OF
`SKJERVEN. MORRILL,
`MacPliERSON, FRANKLIN
`& FRIEL
`25 METRO DRIVE
`SUITE 700
`SAN JOSE. CA 95110
`(408) 453-9200
`FAX@0&4$JW9
`
`P:\DMS\5491\M—12265C\0215679.WP
`
`006
`
`006
`
`

`

`
`
`
`PATENT
`
`entity type from said entity definition table, wherein said
`
`third desired entity type record specifies a third desired
`
`entity instance table associated with said third desired entity
`
`type.
`
`23.
`
`The method of claim 15, further comprising retrieving
`
`a second specific relation instance record defining a second
`
`relation of said provided relation type between said provided
`
`entity and said desired entity from a second relation instance
`
`table corresponding to said second specific relation type
`
`record.
`
`24.
`
`A relational database processing system comprising:
`
`an entity definition table containing a first entity
`
`type record defining a first entity type;
`
`an first entity instance table associated with said
`
`first entity type;
`
`a plurality of entity instance records stored in said
`
`first entity instance table;
`
`a relation definition table containing a first
`
`relation type record defining a provided relation type;
`
`a first relation instance table associated with said
`
`provided relation type; and
`
`a first relation instance record of said provided
`
`relation type, said first relation instance record
`
`relating a desired entity in one of said entity instance
`
`records to a provided entity.
`
`25.
`
`The relational database processing system of claim
`
`24, wherein each of said entity instance records is identified
`
`by a record identifier.
`
`26.
`
`The relational database processing system of claim
`
`24, wherein said first relation contains a desired record
`
`LAW OFFICES OF
`SKJ'ERVEN, MORRILL.
`MBCPHERSON, FRANKLIN
`& FRIEL
`25 METRO DRIVE
`SUITE 700
`SAN JOSE. CA 95110
`(408) 453-9200
`FAX (408) 453-7979
`
`P:\DMS\5491\M—12265C\0215679 .WP
`
`007
`
`007
`
`

`

`
`
`
`PATENT
`
`identifier and a desired entity type corresponding to a desired
`
`entity instance record containing said desired entity.
`
`27.
`
`The relational database processing system of claim
`
`24, wherein said first relation type record comprises a table
`
`identifier identifying said first relation instance table.
`
`28.
`
`The relational database processing system of claim
`
`24, further comprising an inquiry table containing an inquiry
`
`record, wherein said inquiry record specifies said provided
`
`relation type and said provided entity.
`
`29.
`
`The relational database processing system of claim 24
`
`further comprising:
`
`a second entity instance table associated with a
`
`second entity type; and
`
`wherein said entity definition table contains a
`
`second entity type record containing said second entity
`
`type and associating said second entity instance table
`
`with said second entity type.
`
`30.
`
`The relational database processing system of claim 29
`
`further comprising:
`
`a third entity instance table associated with a third
`
`entity type; and
`
`wherein said entity definition table contains a third
`
`entity type record containing said third entity type and
`
`associating said third entity instance table with said
`
`third entity type.
`
`31.
`
`The relational database processing system of claim 24
`
`further comprising:
`
`a second relation instance table associated with a
`
`second entity type; and
`
`LAW OFFICES OF
`SKJERVEN, MORRILL.
`Mam-ERSON, FRANKLIN
`& FRIEL
`75 METRO DRIVE
`SUITE 700
`SAN JOSE. CA 95110
`(408) 453-9200
`FAX (408) 453-7979
`
`P:\DMS\5491\M—12265C\0215679.WP
`
`008
`
`008
`
`

`

`
`
`PATENT
`
`wherein said relation definition table contains a
`
`second relation type record containing said second
`
`relation type and associating said second relation
`
`instance table with said second relation type.
`
`32.
`
`The relational database processing system of claim 24
`
`further comprising:
`
`a third relation instance table associated with a
`
`third entity type; and
`
`wherein said relation definition table contains a
`
`third relation type record containing said third relation
`
`type and associating said third relation instance table
`
`with said third relation type.——
`
`REMARKS
`
`Claims 1—14 are deleted.
`
`New Claims 15—31 are added by
`
`this amendment.
`
`New claims 15—31 are supported by at least
`
`Figures 5, 6A, 6B, and 7, and the Specification at pages 35—45.
`
`Consideration and allowance of these claims is respectfully
`
`requested.
`
`If the Examiner believes a telephone interview
`
`would be helpful to facilitate early allowance of these claims,
`
`the Examiner is invited to call the undersigned Attorney for
`
`Applicant at
`
`(408) 453—9200.
`
`Respectfully sub
`
`
`
`
`Attorney for Applicant
`Reg. No. 33,938
`
`EXPRESS MAIL LABEL NO: EM425689701US
`
`LAW OFFICES OF
`SKJERVEN, MomL,
`MacPl-IERSON, FRANKLIN
`& FRIEL
`25 METRO DRIVE
`SUITE 700
`SAN JOSE. CA 95110
`(403) 453-9200
`FAX (408) 453-7979
`
`P ; \DMS\S491\Mv 12265C\0215679 .WP
`
`009
`
`009
`
`

`

`
`
`ABP/M-1226
`
`PATENT.APPLICATION
`
`DATA RELATIONSHIPS PROCESSOR
`
`WITH UNLIMITED EXPANSION CAPABILITY
`
`Karol Doktor
`
`BACKGROUNDKOF THE INVENTION
`
`1.
`
`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 frames) distributed
`
`over 20 sheets of microfiche in accordance with 37 C.F.R. §
`
`1.96.
`
`The disclosed computer program listings are
`
`incorporated into this specification 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 protection.
`
`The COpyright owner has no 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 0.8. Patent and Trademark Office)
`
`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.
`
`2.
`
`Field of Invention
`
`The present invention relates generally to computer
`
`database management systems and more specifically to
`
`apparatus and methods for modifying and searching through
`
`large scale databases at high speed.
`
`3.
`
`Description of Related Art
`
`Modern computer systems are capable of storing
`
`voluminous 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 encyclopedia or in the telephone directory of
`
`{DNQQMuthH
`
`:»wwuzcnwch»uN«arcNkgNNmareNH+4HHPaidHH+4Hm~4mananoN+4C3‘Om~JmLn9u;m+4ou:m~4mansu:m+4o
`
`010
`
`010
`
`

`

`
`
`ABP/M-1226
`
`PATENT APPLICATION
`
`\DQQC‘U‘leNH
`
`wwwwwwwwwNNNNNNNNNNHHHI—‘Hl—‘HHHH
`“flawhWNI—‘O‘DQQQ‘U’IrhUJNF-‘O‘Dmdmb‘lbwwldc
`
`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 information 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 informa-
`
`tion. Efficient organization of the stored information is
`needed in order to minimize retrieval time.
`
`The methods by which pieces of information are
`
`organized within a computer, searched through or
`
`reorganized, often parallel techniques uSed by older types
`
`of manual
`
`information processing systems.
`
`A well 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 uniformly dimensioned paper cards which are
`
`serially stacked in one or more trays.
`
`The cards are
`
`physically 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
`
`front 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
`
`011
`
`011
`
`

`

`
`
`ABP/M-1226
`
`PATENT.APPLICATION
`
`\DmdmthNH
`
`t»wtowu:wLunit»wh:Nn:Mn:wk:Na:H+4HP‘!4Hr4H+4Hm~JmLn9L»Nrdou:m~JmLnbLuN+4otom~amrnaL»N+4o
`
`author's last name and then according to the author's first
`
`name and then by title. This defines a "key-sequenced" type
`
`of database 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 library 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 realistically 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
`
`012
`
`012
`
`

`

`ABP/M-1226
`
`PATENT.APPLICATION
`
`\DOGQO’IUIIhWNI-I'
`
`wtowtowL»wLuwa:Mn:NisNa:NhaNP4HF4H+4Hm~JmU19o;uk4cxom~4mU1aDJM+4o«am~4mLn9t:St:S
`
`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
`
`requirements placed on the system change.
`
`Some of these
`
`changes 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
`
`discuss 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')
`
`autobiographies.
`
`In such a case,
`
`the card catalog system
`
`needs to be modified by adding at least one additional
`
`column of information 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
`
`information 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
`
`1313
`
`013
`
`

`

`
`
`
`
`ABP/M-1226
`
`PATENT.APPLICATION
`
`{OMQOiUI-hWNH
`
`wsac»wwuzcuwwMnineMNnineMNNF‘}4HHHF‘I‘HHHm~4m01:5ubeHc>\om~JmU1»hwnabsou:m~JmLnaLaN+2a
`
`referred to here as "restructuring" the database.
`
`Now let us suppose, that as more time goes by, an
`
`additional but previously unanticipated, cross indexing
`
`category 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 net
`
`have the capacity to handle the demands of the newer
`
`technology or regulation.
`
`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
`
`spacially 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 amplifier 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
`
`014
`
`014
`
`

`

`
`
`ABP/M-1226
`
`PATENT.APPLICATION
`
`\OODKJU‘UIbMMH
`
`wwwnit»wuwtaromNNh>roNNwhardH’HHem~JmLn9toN+4o\om~JmLnaLaN+4onom~qmtn2t:St:S
`
`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 “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
`
`horizontal "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 different 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.
`
`A vast number of different linking "threads" may be
`
`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
`
`different 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.
`
`015
`
`015
`
`

`

`
`
`ABP/M—1226
`
`PATENT-APPLICATION
`
`\DWQO‘MfiWNI—J
`
`wL0wLuwLuwtowA)Nn:mh)mn:Nh)Nr4HP4Hmumma-cuNHowm~J<hmpwhardoomwcut;I5StS
`
`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 performance
`
`_
`suffers.
`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 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
`
`016
`
`016
`
`

`

`
`
`ABP/M-1226
`
`PATENT.APPLICATION
`
`mmuc\tn.>wukt
`
`NNO‘U‘Ithi—‘O‘OmfimmthHOKDmQO‘bfifiwFM-IES
`WNNWWWUWU’NMNNMNNNNNHl—‘Hl—‘P—‘l—‘H
`
`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
`
`A large variety of
`independent from the sort key data.
`different relations can therefore be established 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 referencing 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
`
`017
`
`017
`
`

`

`
`
`ABP/M-1226
`
`PATENT APPLICATION
`
`‘OODQOIUIIDDJNH
`
`mqmmprr-iouoaoxlmmbwwwowgsggzastg
`wwwwwwwwwmwnwmwwmmmr—a
`
`The elements of
`respective items of pre—stored information.
`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.a 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 it