`
`H,
`
`.
`
`O 03/439013 A 4
`
`37
`
`-
`DIVISION-CONTINUATION PROGRAM APPLICATION TRANSMITTAL FORM
`
`film (Sm. Bus, §1.60)
`fl
`
`
`
`
`Atty Docket No.: M-1226-4D US
`
`f‘J—?f‘
`
`
`
` Serial Not: 08 083 361
`
`Filing Date:
`
`06(28193
`
`Inventor(s): Karol Doktor
`
`
`
`Assignee: Financial S stems Technolo . Ltd. Pt
`
`
`
`Examiner:
`
`L. Toplu
`
`Group Art Unit:
`
`2316
`
`Title:
`
`DATA RELATIONSHIPS PROCESSOR WITH UNLIMITED EXPANSION
`
`CAPABILITY
`
`To the Commissioner of Patents and Trademarks:
`
`This is a request to file a:
`
`[
`
`I continuation
`
`[X] 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
`
`including the specification, claims, drawings and oath or
`prior application,
`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
`
`[X]
`
`[
`
`]
`
`[X]
`
`[
`
`]
`
`A Preliminary Amendment is enclosed.
`
`of the latest inventor-
`Cancel in this application claims
`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.
`
`
`
`L:\DMS\$491\M-l226—4\0129291.WP
`
`IBM EX. 1017
`
`001
`
`

`

`‘
`
`a
`
`.
`
`‘
`
`.
`
`J
`
`.
`
`.
`
`The filing fee is calculated as follows:
`
`For
`
`Number
`
`Filed
`
`Number
`Extra
`
`Total Claims
`
`16
`
`-20 =
`
`Independent
`Claims
`
`8
`
`~
`- 3 =
`
`0
`
`5
`
`
`Rate
`
`x
`
`11
`
`x
`
`38
`
`=
`
`=
`
`Fee
`
`0
`
`190.00
`
`Basic Filin Fee:
`365.00
`
`_
`Application contains one or more multiple
`de endent claims
`120 total fee
`
`0
`
`TOTAL FILING FEE:
`555.00
`
`
`Please make the following charges to Deposit Account 19-2386:
`
`[X]
`[
`]
`
`Fee for filing the patent application in the amount of
`$
`555.00
`An Extension of Time in the above—named prior application has been
`requested and the fees therefor have been authorized in said
`application.
`
`
`
`I
`‘
`g
`J
`I
`
`[X]
`
`losed.
`
`j
`
`,
`
`/
`4
`
`The Commissioner is hereby authorized to charge any additional fees
`which may be required, or credit any overpayment to Deposit Account
`19-2386.
`A Return Receipt Postcard and triplicate copy of this sheet
`(/45?
`are
`46
`r/finc
`k"/
`&_._.=s[x]
`Amend the specification by inserting before the first line the sentence:
`
`
`is app 1cation 1S a
`continuation X
`1vision of appligagigg,vl.fl-
`62,,
`serial no. 08(083,361, filed June 28I 1993, which is a continuation of
`
`
`serial no. 07(526,424, filed May 21l 1990, now abandoned..
`J
`
`
`\ ngg
`
`‘
`
`[]
`
`[
`
`]
`
`New drawings are enclosed ([] formal
`
`Other enclosures:
`
`[] informal).
`
`Q&;V
`
`[
`
`]
`
`[X]
`
`filed on
`Priority of application serial no.
`[
`in
`(country)
`is claimed under 35 USC 119.
`certified copy has been filed in the latest inventor—signed prior
`application.
`
`] The
`
`Small Entity Declaration/Independent Inventor's Declaration [X] has been
`filed in the latest inventor-signed prior application and its benefit
`under 37 CFR 1.28(a)
`is hereby claimed;
`[
`]
`is enclosed.
`
`[X]
`
`The power of attorney in the above-named prior application is to
`
`17 774 - Richard
`24 423 - Thomas S. MacDonald
`Alan H. MacPherson
`Franklin
`19 128 - Kenneth E. Leeds
`30 566 - Walter J. Madden
`Jr.
`16 661 - Paul J. Winters
`25 246 - Brian D. O onowsk
`31 988 - Edel
`M. Youn
`32 451 - David W. Heid
`25 875 - Gideon Gimlan
`31 955 - Gu
`W. Shoup, £26,805}; Forrest E. GunnisonI $32,899}; Norman R. KlivansI
`33 003 ~ David H. Carroll
`29 903 - and Ronald C. Fish
`28 843 .
`
`[X]
`
`[
`
`]
`
`The power appears in the original papers in the latest inventor-
`signed prior application.
`
`Since the power does not appear in the original papers, a copy of
`the power in the latest inventor—signed prior application is
`enclosed.
`
`‘
`
`L:\DMS\549I\M-1226-4\0129291.WP
`
`@ l
`
`_2_
`
`002
`
`.
`u
`I.u1‘
`
`\
`
`002
`
`

`

`-
`
`O
`
`D
`
`[x]
`
`Address all future communications (May only be completed by applicant,
`or attorney or agent of record)
`to:
`
`Paul J. WintersM
`
`Sk'erv Morrill MacPherson Franklin & Friel
`
`25 Metro Drive Suite 70
`
`San Jose
`CA 95110
`
`
`Date:
`
`(2! g g H : [Eli )‘ Signature:
`
`
`
`Address of signator:
`
`Reg. No.
`
`( f applicable) 25‘246
`
`inventor(s)
`]
`[
`] assignee of complete interest
`[
`[X] attorney or agent of record
`[
`] attorney for Applicant(s)
`under 37 C.F.R.
`§ 1.34(a)
`
`
`Paul J: Winters
`
`.SkjervenlrMorrill, MacPhersonI Franklin & Friel
`
`25 Metro Drivel Suite 700
`
`San Jose‘ CA 95110
`
`I hereby certify that this correspondence is being deposited with the United
`States Postal Service as express mail in an en
`lope addressed to:
`Commissioner of Patents and Trad ma
`s, Washin
`on, D. C., 20231, May 11,
`1995. Express Mail Receipt No. T 807
`3254US.
`‘
`
`
`,:/_ Vm/E'
`
`Date of Signature
`
`L:\DMS\5491\M-1226-4\012929l .WP
`
`003
`
`003
`
`

`

`4
`
`.
`
`93/439013.
`
`-M-1226
`K. Doktor
`m
`
`-
`
`FIGIIRE 1A
`
`Va: Slimlhn
`W» Sheet 1 of
`comm
`
`
`Accegs Qontrol
`Program
`
`(Source Code)
`
`
`
`
`
`
` Bmx gigging}:
`
`-.
`(Binary Code ‘Sm'ngs)
` Access control ‘
`
`flegmn
`
`(Object Code)
`
`UERY INPUT"
`(SQL)
`
`
`
`"Please find
`all books
`havin ; x
`
`
` ”gnaw
`
`P
`
`004
`
`004
`
`

`

`aw:
`
`w/439013
`
`7’...
`
`M-] 226
`K. Doktor
`PST
`
`-
`
`Vat: gin/no 9 m
`00 mum-Lb)
`mam
`comm 20
`
`Sheet
`2
`
`W(
`
`Prior Art)
`
`
`
`\
`
`'
`
`005
`
`005
`
`

`

`Book's
`
`Location
`
`006
`
`

`

`M-1226
`K. Doktor
`m
`
`.
`
`'.
`. 1:191ng 2B
`(Prior Art)
`
`.
`
`m Sheet4of
`W“)
`W
`(IO-t 9004 20
`
`132 }
`
`RELATIVE-TABLE ORGANIZATION:
`1
`
`(RTO) Book's
`
`Location .
`
`. 3 Iia
`
`___._
`
`007
`
`007
`
`

`

`08/439013 Pr.
`
`5Woo-mmzo
`
`v; man ‘9'“
`col mum's;
`(m0!)
`
`Shea
`
`
`,nunuuuuunmux.
`744444:444444444444444444444444444n
`
`
`
`42 \\\\\\\\
` Person
`\\\\\\\\\\\\\\\\\\\\\\\\
` \\\\\\\\
`
`
`4444444444I444444444444444444444444444
`46
`\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
`‘\\\\\\\\\\s\\\\\\\\\\\\\x\\\
`¢\\\\\\\~\x\\v\
`
`120d*
`
`
`
`\
`
`444444444444444
`
`'9
`
`44444444:
`
`IDN=II4II
`
`Car
`IDN="2"
`
`\\\\\\\\\\44,4444444
`
`\
`
` Random
`Object Code
`
`008
`
`008
`
`

`

`u. "h‘
`'- cf:
`
`.
`
`'f
`
`.
`
`( t
`
`.t
`_
`08/439013 '
`
`_
`
`M-1226
`FST
`
`.
`
`._
`
`,
`
`I URE 4
`
`v; mm eta
`m
`
`M
`
`RELATION R-l
`
`Meaning: Head Attribute + Tail Attribute
`{ Caldinality = one to many }
`~Mandatory Coupling = Yes/No
`
`
`
`
`
`\‘B,
`
`
`
`
` I 1/8]
`= "Customer-B"
`
`
`
`
`/
`/
`
`1/53
`
`009
`
`009
`
`

`

`p
`
`I
`
`08/439013 ,:
`
`‘
`M-1226
`K. Doktor
`PST
`
`'
`
`.
`
`FIGURE 4B
`K.
`
`4—5-
`
`" V
`"
`;'u: film ”In.
`‘ W» Sheet
`(”on
`_
`7
`8%“
`
`-
`
`I Customer ®
`/
`/
`
`
`
`/
`
`
`
`Telephone
`/
`
`'010
`
`010
`
`

`

`M/439013
`N
`
`M- 1 226
`K. Doktor
`FST
`
`Van mm Hm:
`Wm;
`co museum
`(ms-OI)
`604900120
`
`Sheet
`. 8
`
`Class Name
`Abbneviation
`
`Name of
`Single Table
`when: instances
`are stored
`
`
`
`011
`
`011
`
`

`

`08/439013
`
`'
`
`M-1226
`K. Doktor
`FST
`
`l 30-RP
`
`‘
`
`.
`
`Eng! IRE 6A
`
`v": am .“ m
`W.)
`am": a“ m.
`tic-mum
`
`Sh9eet
`
`Relation
`Class Name
`Abbreviation
`(Full Name)
`
`Name of
`Single Table
`where instances
`of Relation
`are stored
`
`'
`
`Head Entity
`Type Number
`(Full Name)
`
`First
`Tail Entity
`Type Number
`(Full Name)
`
`6006
`
`Mandatory
`Head
`Coupling
`
`6003
`
`Optional
`Second thru Fifth
`Tail Entity
`Names
`(type)
`
`012
`
`012
`
`

`

`\J.
`
`'
`
`‘
`
`08/439013
`
`r:—
`
`¥~113226
`.
`oktor
`FST
`
`‘
`
`I
`
`RE B
`
`'
`
`Va: Sig/w 2m
`W»
`,.
`.
`Museum
`
`salsa
`
`_
`
`Optional
`Second thru Fifih
`Tail Entity
`Names
`Region
`
`.4
`
`(Supplier)
`
`‘
`
`.5
`
`(Area) -
`
`Tail-Activation
`
`.6
`
`.3
`
`'(PhoneNo). (Account) . O O O O
`
`013
`
`013
`
`

`

`08,-’439013
`2:.—
`
`M-1226
`K. Doktor
`FST
`
`1 3O-RP m
`
`E lGflRE 7
`‘
`
`
`
`
`Va: snub—1 pa
`6% Sheet
`Ehm'°a".m.
`11
`0cm90u 20
`
` REQUEST
`
`
`
`for:
`
`_O\uunuu‘
`
`
`
`600
`
`_
`
`
`
`
`(a) Search
`~Re1au‘on- Level
`
`b
`d
`(b) InqquirY
`
`\l00
`
`
`
`(0) Update
`(d) Restructure
`-Schema
`
`
`
`
`mmmp.
`-BU—
`
` -Entity-
`um-I
`
`’43e"
`
`s 3:: ==lI
`
`. g
`.
`
`Rel. Tail(l)
`
`
`ABM—EL
`
`
`
`a
`
`5 y
`
`3\
`
`_____
`
`
`9
`‘
`y
`L731
`.,,,,,-.2,- .SI
`.3 ;::::::.,, .
`w
`”nu/a,”Man‘wuuun.
`5001 (Kso‘u.
`
`+-~
`
`730
`
`.
`
`.
`
`,
`
`_
`
`_
`
`" 733
`
`I
`
`’6
`
`o‘
`
`\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
`
`2II
`III
`IIIIII
`IIIII
`
`55III5I5II5II5II5 gI55III 55IIIIII5I
`
`’1II.
`’II
`
`1,114,;4z11’1;111
`
`
`
`
`
`\ \
`
`\\\\\\\\\\\\\
`
`III/III/III/[I’ll/IllI’ll/I’ll/IIIIIIIII/II/IIIIIII/Ill(I’ll/IIIIIII
`
`014 ,
`
`
`
`
`A-S:_751\m \\\\s\\\\\\\\\\\\\\\\\\\\\\ \\\\\\\\\\\\\\\\\\\\\\\\\\\\\
`
`
`~
`
`\\\\\\\\\\\\\
`
`In
`
`
`014
`
`

`

`08/439013
`7.;
`
`
`
`"Please find
`
`all books
`havin x x"
`
`
`
`(SQL)
`
`
`
`
`
`
`Selmna;
`
`"Please add
`(SQL)
`
`
`
`new books
`
`
`"Please add
`
`WY'ZZZ"
`
`new REL
`Rnn-Rmm"
`
`
`
`870
`
`015
`
`015
`
`

`

`g“.
`
`‘L-
`
`”/439013
`7.2;
`
`M-1226
`K. Doktor
`FST
`
`,
`
`Va: mum pm
`FI URE 9 W SHEET 13
`a (”a“) .
`(Io-mono
`
`901
`
`910
`
`'
`Starting QUERY
`
`M
`
`INQUIRY INPUT FORM
`902
`INQUIRY GUIDE MEANS
` Lvl-l ETN1.EiN1- R'I'N1-7
`.,
`
`Lvl-2
`?
`.
`97
`- RTN2-?
`
`
`
`Lvl-3
`
`?
`
`.
`
`??
`
`- RTN3-?
`
`LvI-l
`
`ETN4. 7?
`
`- RTN4-7
`
`
` lEi-32a.1
`Ei-32a.2
`
`
` Intermediate Answers
`
`
`
`D i1
`
`1 Di
`
`1
`
`Allcns' Autos---------- 106 Car Corner
`Expert‘s Electronics---555 Transistor Lane
`5%
`
`W Bob‘s Books Inc.-------220 Literature SLreet
`
`
`016
`
`
`
`
`
`
`
`
`List Means
`
`Ei-ol
`Ei-Oz
`Ei-O3
`
`990
`
`016
`
`

`

`
`
`08/439013.
`
`
`
`ZIHNNQ<flum§§~=fl
`
`
`HA.U059.Emain.Marga—“1.8mama
`
`57—69—93
`
`
`...Qm_&=3;wkEmmA..m2052Ia
`mafia—am59.83585825858macaw
`
`
`
`35:00I33383vEms—.83'FmfiaoomH.m3052
`.r96—;.‘raga
`,2H.H.
`
`(\
`
`
`
`
`.9E95aa?d.S.d.w~353.3;.gm?“Siam
`5358cm88:5
`
`
`
`Wrugs
`
`.m2052.
`
`.m$052.
`
`.mmanna@Q
`
`Hiram.
`
`017
`
`
`
`
`

`

`
`
`'T' “40010".
`PATENT APPLICATION
`
`Karol Doktor
`
`3 4 5 6 7 8 9
`
`BACKGROUND OF THE INVENTION
`endix
`1.
`Cross Reference to Microfiche A
`
`This application includes a plurality of computer
`10 program listings (modules)
`in the form of a Microfiche
`11 Appendix which is being filed concurrently herewith as 1162
`12
`frames (not counting target and title frames) distributed
`13 over 20 sheets of microfiche in accordance with 37 C F. R.
`
`§
`
`The disclosed computer program listings are
`14 1.96.
`15
`incorporated into this specification by reference but it
`16
`should be noted that the source code and/or the resultant
`17 object code of the disclosed program modules are subject to
`18
`copyright protection. The copyright owner has no objection
`19
`to the facsimile reproduction by anyone of the patent
`20
`document (or the patent disclosure as it appears in the
`21
`files or records of the U.S. Patent and Trademark Office)
`
`22
`
`for the sole purpose of studying the disclosure but
`
`23 otherwise reserves all other rights to the disclosed
`24
`computer program modules including the right to reproduce
`25
`said computer program modules in machine-executable form.
`26
`
`‘ 27
`28
`29
`30
`31
`32
`
`33
`34
`35
`36
`37
`38
`
`2.
`
`Field of Invention
`The present
`invention relates generally to computer
`database management systems and more specifically to
`apparatus and methods for modifying and searohing 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
`
`01!!
`
`|i !l
`
`i ‘
`
`018
`
`

`

`ABP/M-l 2 2 6
`
`PATENT . APPLICATION
`
`maqmmc-wNH
`
`wtowtou:wu:wu)N‘h)Nh)Nh)Nh)Nh)HrdHHmNa\\nbwMP4<3wmuawtnh'wh))‘owmuSight:5SSE
`
`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
`
`to
`take an undesirably long time (i.e., hours or days)
`retrieve desired pieces of information} ’In commercial
`settings
`‘ch as financial data storage facilities,
`there
`will beMbillions 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).
`
`0n the
`
`in left
`front surface of each index card a librarian enters,
`tO'right sequence;
`the last name of an author,
`the first
`name of the-author,
`the title of a single book which the
`
`1 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
`
`
`
`
`
`01S)
`
`019
`
`

`

`ABP/M—1226
`
`.
`
`PATENT. APPLICATION
`
`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
`
`the librarian may quickly search
`written by a named author,
`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, suppdse 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
`Acatalog,
`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 cf inquiries,
`libraries
`often keep redundant sets of index cards. One set of cards
`is sorted according to author names and another set is
`t
`sorted according to the subject matter of each book. This
`form of redundant storage is disadvantageous because the
`
`mmqmmwab-I
`
`wwwwwwwwNNNNMNNNNMHHI—‘l—‘I—‘t—‘HH
`
`size of the card catalog is doubled and hence,
`the cost of
`information storage is doubled. Also, because two index
`
`38
`
`mm
`
`
`020
`
`020
`
`

`

`r
`
`ABP/M-1226
`\
`
`‘
`
`'PATENT.APPLICATION
`
`cards must be generated for each new bobk added to the .
`cdllection 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 vauired. 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 sire and in worth.
`The "worth" of the carddbased system may be defined in part
`
`I
`
`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
`
`Some of these
`requirements placed on the system change.
`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‘bf 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,
`
`the new microfilm cross referencing information
`and finally,
`is added to the larger cards. This type of activity will be
`
`wooxzmmthI-I
`
`wu:(»w0:1»whit»NhlluNsiloNa;NhardHFlidHP‘Hm~JmLH‘boarsHcawoas4murnswnoH-c>\am~Jm01.55«3::S
`
`
`
`
`\
`
`021
`
`021
`
`

`

`
`
`ABP/M-1226
`
`'
`
`PATENT. APPLICATION ‘
`
`\Dm~4mLnataleH
`
`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 not
`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
`
`Each bit is represented by a magnetic flux
`storage.
`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
`
`wwwwwwwwwNNNNNNNNNNHH
`
`022
`
`022
`
`

`

`ABP/M—lz 26
`
`'
`
`PATENT. APPLICATION.
`
`Some bit strings
`location or by a logical storage address.
`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
`
`The user-desired objects of real
`address pointers.
`~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
`
`is then
`sequence of "rows“ (analogous to a stack of cards)
`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
`
`(which replaces the
`the same collection of rows
`systems,
`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
`A
`information (or its address) is found within a table.
`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
`
`\DQQO‘WhWNH
`
`wu)!»wtownit»wa»Nh:wh3luQniceNPaidHm~4mLnbcaNr4o\om~4mtn9toNr4c\om~4;t:Et:St:S
`
`spot.
`
`023
`
`023
`
`

`

`ABP/M-1226
`
`PATENT.APPLICATION
`
`wmflmm-thH
`
`mummpwwHosaooqmmwaHomooutc-‘sSZSSEg
`wwWWWUUWWNMNNNNNNNNPI-‘H‘
`
`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 scrt
`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 isnlocated 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
`
`is being sought or additional Sort-key
`the real data that
`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
`
`
`
`
`
`024
`
`024
`
`

`

`
`
`ABP/M-1226
`
`PATENT.APPLICATION
`
`\DQ'QU‘U‘IIFDJNH
`
`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,
`The
`"Mr. Harry W. Jones", "Mrs. Barbara R. Smith", etc.
`sort-key can be a number which is stored adjaéent
`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
`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 personfs 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’
`
`wwwwwwwwwNNNNNNNNNND-‘HH.
`
`025
`
`025
`
`

`

`ABP/M-1226
`
`’
`
`PATENT APPLICATION
`
`toooqmmwaH
`
`u1»u:«»wL»wnit»Nh:Nn:Nn:wn:N'h)H.P4H+4H+4HmummbwNHowooxlmm-waHoooou’mmpwstg
`
`‘respective items of pre-stored information., The elements of
`the loweSt level subsets are stored in base tables and
`
`in other tables,
`higher level sets are built by defining,
`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.
`
`A second
`
`relational table may be provided inythe database
`(Cars-Table) which lists automobile'ivehicle) identification
`numbers (VIN) each paired in its row with a second key
`
`number.’ If the second key number is matched by a
`Icorresponding 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 "implied"
`relationship might be one of an infinite set of
`
`ipossibilities.
`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.
`
`
`
`Ir’\
`
`026
`
`026
`
`

`

`
`
`
`ABP/M-1226
`
`'
`
`PATENT. APPLICATION
`
`\Dmflmm-bMNH
`
`
`
`wwwwwwwwwMNNN‘NNNNNNF‘D-‘HH'-m~4mLn9c»wr4o\om~4mtn9toNrd0\om~4mt;Et:St:Z
`
`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 reference 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
`
`The vehicle identification
`storage redundancy are avoided.
`number
`(VIN)
`remains unchanged. Minimal work is thus
`
`expended on updating the database.
`Despite these advantages, relational database systems
`'suffer 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
`
`V
`
`assembled.
`
`If spare columns are not.availab1e in the
`
`the entire database may have to be restructured
`Cars-Table,
`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 regula—
`tion., 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
`programming staff.
`It was time consuming, costly and prone
`to programming errors. Worst of all, it had to be redone
`
`-/ I
`
`.410-
`
`027
`
`027
`
`

`

`OQQO‘UI-waH
`
`wwwwwwwwwNNNNNNNMNNl-‘H
`
`.)
`
`ABP/M-1226
`
`PATENT-APPLICATION
`
`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
`reprogramming at the source or object code level.
`
`SUMMARY OF THE INVENTION
`It is an objective of the present
`
`invention to provide
`
`high speed, and is at the same time easily expandable or
`restructurable to take on new forms of entities and
`relationships.
`In accordance with a first aspect of the invention, an
`entity definition table (ENT.DEF) 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 of the allowed entity type may be stored.
`A
`separate relationships definition table (REL. DEF)
`is defined
`in the memory means to list in eachrow of the table:
`(a) the name of an allowed relations type,
`(b)
`the name of a
`single Relatibn- instances Table (RiT)