(19) United States
`(12) Reissued Patent
`Doktor
`
`111111111111111111111111111111111111111111111111111111111111111111111111111
`USOORE40520E
`
`(10) Patent Number:
`(45) Date of Reissued Patent:
`
`US RE40,520 E
`Sep. 23, 2008
`
`(54) EASILY EXPANDABLE DATA PROCESSING
`SYSTEM AND METHOD
`
`(75)
`
`Inventor: Karol Doktor, Wheelers Hill (AU)
`
`FOREIGN PATENT DOCUMENTS
`
`wo
`WO
`
`WO 00/07354
`WO 01/15811
`
`2/2000
`8/2001
`
`(73) Assignee: Financial Systems Technology
`(Intellectual Property) Pty Ltd,
`Malvern, Victoria (AU)
`
`(21) Appl. No.: 11/152,835
`
`(22) Filed:
`
`Jun. 14, 2005
`
`Related U.S. Patent Documents
`
`5,826,259
`Oct. 20, 1998
`08/862,176
`May 22, 1997
`
`Reissue of:
`(64) Patent No.:
`Issued:
`Appl. No.:
`Filed:
`u.s. Applications:
`(63) Continuation of application No. 08/439,207, filed on May
`11, 1995, now Pat. No. 5,675,779, which is a division of
`application No. 08/083,861, filed on Jun. 28, 1993, now Pat.
`No. 5,604,899, which is a continuation of application No.
`07/526,424, filed on May 21,1990, now abandoned.
`
`(51)
`
`Int. Cl.
`G06F 17/30
`
`(2006.01)
`
`(52) U.S. Cl.
`(58) Field of Classification Search .
`
`707/4; 707/2
`... .... 707/2,
`707/3, 101, 103 Y
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`3,618,027 A
`3,670,310 A
`4,068,300 A
`4,128,891 A
`
`11/1971 Feng
`6/1972 Bharwani et aI.
`1/1978 Bachman
`12/1978 Lin et al.
`
`.
`
`364/900
`395/603
`364/200
`364/900
`
`OTHER PUBLICATIONS
`
`Rudolf MullZ, "Design of The Well System", 1980, Noth(cid:173)
`Holland Publishing Company, pp. 505-522.*
`Tsichritzis, D. "LSL: A Link and Selector Language", Pro(cid:173)
`ceedings of the ACM-SIGMOD International Conference
`on Management of Data, Jun. 2-4,1976, pp. 123-133.*
`MullZ, R. "The Well System: A Multi-User Database Sys(cid:173)
`tem Based on Binary Relationships and Graph-Pattern(cid:173)
`Matching", Information Systems, vol. 3,1978, pp. 99-115.*
`
`(Continued)
`
`Primary Examiner-Luke S Wassum
`(74) Attorney, Agent, or Firm-Allen, Dyer, Doppelt,
`Milbrath & Gilchrist, P.A.
`
`(57)
`
`ABSTRACT
`
`Machine automated techniques are described for a method
`of data processing called Relationships Processing. A com(cid:173)
`puting system is disclosed which provides for the high speed
`recording and extraction of data objects (entities) and for the
`development data representing a queried relationship
`between the entities. The system is expandable to handle the
`relatively voluminous data bases of large, commercial data
`repositories. A user defines set of entities and allowed rela(cid:173)
`tionships between the entities. The user can expand this set
`of allowed entities and relationships at any time during the
`life of the system without reprogrannning or compiling of
`computer program code or disrupting concurrent operational
`use of the system. Large systems can now be built that are no
`longer limited to a scope of design requirements known dur(cid:173)
`ing initial systems development. For a given set of defined
`relationships the system allows the user to perfonn complex
`inquiries (again without programming at the code level) that
`would normally require multiple nested inquiries to be
`coded progrannnatically and would not achieve the perfor(cid:173)
`mance levels of the Relationships Processor.
`
`(Continued)
`
`18 Claims, 19 Drawing Sheets
`
`001
`
`

`

`US RE40,520 E
`Page 2
`
`u.s. PATENT DOCUMENTS
`4,497,039 A
`1/1985 Kitakami et 31
`4,498,145 A
`2/1985 Baker et al.
`4,506,326 A
`3/1985 Shaw et al.
`4,575,798 A
`3/1986 Lindstrom et al.
`4,631,664 A
`12/1986 Bachman
`4,670,848 A
`6/1987 Schramm
`4,774,661 A
`9/1988 Kumpati
`4,791,561 A
`12/1988 Huber
`4,807,122 A
`2/1989 Baba
`4,829,427 A
`5/1989 Green
`4,855,908 A
`8/1989 Shimada et al.
`4,893,232 A
`1/1990 Sairnaoka et al.
`4,901,229 A
`2/1990 Tashiro et 31
`4,918,593 A
`4/1990 Huber
`4,930,071 A
`5/1990 Tau et 31
`4,930,072 A
`5/1990 Agrawal et al.
`4,933,848 A * 6/1990 Haderle et al.
`4,947,320 A *
`8/1990 Crus et 31
`4,967,341 A
`10/1990 Yamamoto et al.
`5,133,068 A
`7/1992 Crus et 31
`5,168,565 A
`12/1992 Morita
`5,193,183 A
`3/1993 Bachman
`5,197,005 A
`3/1993 Shwartz et al.
`5,226,158 A * 7/1993 Horn et al.
`5,239,663 A
`8/1993 Faudemay
`5,247,575 A
`9/1993 Sprague et al.
`5,262,942 A
`11/1993 Earle
`5,297,279 A
`3/1994 Bannon et al.
`5,369,761 A * 11/1994 Conley et al.
`5,379,419 A *
`1/1995 Heffernan et al.
`5,386,557 A *
`1/1995 Boykin et al.
`5,386,559 A *
`1/1995 Eisenberg et al.
`5,408,657 A * 4/1995 Bigelow et 31
`5,459,860 A * 10/1995 Burnett et 31
`5,488,722 A *
`1/1996 Patak
`5,504,885 A * 4/1996 Alashqur
`5,539,870 A * 7/1996 Conrad et 31
`5,542,073 A * 7/1996 Schiefer et 31
`5,548,749 A *
`8/1996 Kroenke et al.
`5,581,785 A * 12/1996 Nakamura et al.
`5,664,177 A * 9/1997 Lowry
`5,826,259 A
`10/1998 Doktor
`5,893,108 A
`4/1999 Srinivasan et 31
`6,105,035 A
`8/2000 Monge et al.
`
`OTHER PUBLICATIONS
`
`364/900
`364/900
`707/4
`364/300
`364/200
`364/513
`707/3
`364/300
`364/200
`364/300
`364/405
`364/200
`364/200
`364/200
`364/300
`364/300
`364/300
`364/200
`364/200
`365/600
`365/600
`395/600
`364/419
`395/600
`365/800
`380/9
`364/408
`395/600
`707/2
`395/600
`395/600
`395/600
`395/600
`707/101
`395/600
`395/600
`345/352
`395/600
`395/600
`707/103
`707/100
`707/4
`707/103
`707/103
`
`MullZ, R. "Design of the Well System", in Entity-Relation(cid:173)
`ship Approach to Systems Analysis and Design, Proceedings
`of the I st International Conference on the Entity-Relation(cid:173)
`ship Approach, Chen, P. ed., 1979, pp. 502-522.*
`Malhotra, A. et al. "Implementing an Entity-Relationship
`Language on a Relational Data Base", IBM Research Report
`12134 (#54499), Aug. 27, 1986.*
`Rybinski, H. "On First-Order-Logic Databases", ACM
`Transactions on Database Systems (TODS), vol. 12, No.3,
`Sep. 1987, pp. 325-349.*
`University of Texas "Data Modeling: the Entity-Relation(cid:173)
`ship Model", downloaded from www.utexas.edu/its/archive/
`windows/database/datamodeling/dm/erintro.html, Feb. 29,
`2004.*
`University of Texas "Data Modeling: Primary and Foreign
`Keys", downloaded from www.utexas.edu/its/archive/win(cid:173)
`dows/database/datamodeling/dm/keys.html, Feb. 29, 2004.*
`Curran, T. "EE22 I-Database Systems & Software Analysis
`and Design", course notes, Dublin City University, School
`of Electronic Engineering, downloaded from www.eeng.d(cid:173)
`cu.ie/-ee221-DB-2.pdf, 2007.*
`
`Microsoft Corporation, "Relational Database Components",
`tutorial, downloaded from msdn.microsoft.com/en-us/li(cid:173)
`brary/aaI74501(SQL.80).aspx, 2007.*
`Korth and Silberschatz, Database System Concepts,
`McGraw-Hill Book Company (New York,
`1986),pp.
`45-105;pp.301-323.
`"Extended Disjunctive Normal Form for Efficient Process(cid:173)
`ing of Recursive Logic Queries", IBM Technical Disclosure
`Bulletin, vol. 30 No. I, Jun. 1987 pp. 360-366.
`Yu et aI, "Automatic Knowledge Acquisition and Mainte(cid:173)
`nance For Semantic Query Optimization", IEEE Transac(cid:173)
`tions on Knowledge and Data Engrn, VI, No.3 Sep. 1989,
`pp.362-375.
`Kifer et aI, "Sygraf: Implementing Logic Programs in a
`Database Style" IEEE Transactions on Software Engnm.
`v:14, N7, Jul. 1988 pp. 92-935.
`EI-Sharkawi et aI, "The Architecture and Implementation of
`Enli: An Example-Based Natural Language Assisted Inter(cid:173)
`face", Parbase 90 IntI. Conf. on Databases, Parallel Architec(cid:173)
`tures & Their Applications, Mar. 7-9, 1990.
`Wilschut et aI, "Pipelining in Query Execution" Parbase-90
`IntI. Conf. on Databases, Parallel Architectures and Their
`Applications, Mar. 7-9, 1990 p. 562.
`BaneJjee et aI., "Data Model Issues for Object-Oriented
`Applications", ACM Transactions on Office Information
`Systems, vol. 5, No. I, Jan. 1987, pp. 3-26.
`Blakely et aI., "Experiences Buildig the Open OODB Query
`Optimizer", 1993, pp. 287-296.
`Markowitz et aI., "Representing Extended Entity-Relation(cid:173)
`ship Structures
`in Relational Databases: A Modular
`Approach", ACM Transactions on Office Information Sys(cid:173)
`tems, vol. 17, No.3, Sep. 1992, pp. 423-464.
`Teorey et aI., "A Logical Design Methodology for Relational
`Databases Using the Extended Entity-Relationship Model",
`Computing Surveys, vol. 18, No.2, Jun. 1986, pp. 197-222.
`Chen, Peter, "Entity-Relationship Approach to Systems
`Analysis and Design", Proceedings of the International Con(cid:173)
`ference in Los Angeles, Dec. 10-12, 1979, pp. 237-257.
`Blakeley et aI., "Experiences Building the Open OODB
`Query Optimizer", 1993, pp. 287-296.
`Zand et aI., "A Survey of Current Object-Oriented Data(cid:173)
`bases", Data Base Advances, Feb. 1995, vol. 26, No. I, pp.
`14-29.
`Straube et aI., "Queries and Query Processing in Object-O(cid:173)
`riented Database Systems", ACM Transactions on Informa(cid:173)
`tion Systems, vol. 8, No.4, Oct. 1990, pp. 387-430.
`Kim et aI., "Semantics and Implementation of Schema Evo(cid:173)
`lution in Object-Oriented Databases", 1987, pp. 311-322.
`Kim et aI., "Composite Object Support in an Object-Ori(cid:173)
`ented Database System", OOPSLA '87 Proceedings, Oct.
`4-8, 1987,pp. 118-125.
`Hull et al.,"Semantic Database Modeling: Survey, Applica(cid:173)
`tions, and Research Issues", ACM Computing Surveys, vol.
`19, No.3, Sep. 1987, pp. 201-260.
`Nixon et aI., "Implementation of a Compiler for a Semantic
`Data Model: Experiences with Taxis", 1987, pp. 118-131.
`Codd, E., "Extending the Database Relational Model
`to
`Capture More Meaning", ACM Transactions on Database
`Systems, vol. 4, No.4, Dec. 1979, pp. 397-434.
`Peckham et aI., "Semantic Data Models", Acm Computing
`Surveys, vol. 20, No.3, Sep. 1988, pp. 153-189.
`Tsurt et aI., "An Implementation of GEM-supporting a
`semantic data model on a relational back-end.", 1984, pp.
`286-295.
`
`002
`
`

`

`US RE40,520 E
`Page 3
`
`Wilkinson et aI., "The Iris Architecture and Implementa(cid:173)
`tion", IEEE Transactions on Knowledge and Data Engineer(cid:173)
`ing, vol. 2, No. I, Mar. 1990,27 pages.
`Gamache et aI., "Addressing Techniques Used in Database
`Object managers O2 and Orion", SIGMOD Record, vol. 24,
`No.3, Sep. 1995, pp. 50-55.
`Kim et aI., "Architecture of the Orion Next-Generation
`Database System", IEEE, 1990, pp. 109-124.
`Klimbie et aI., "Data Base Management", North-Holland
`Publishing Company, 1974, pp. I-59.
`Hudson et aI., "Cactis: A Self-Adaptive, Concurrent Imple(cid:173)
`mentation of an Object-Oriented Database Management
`System", ACM Transactions on Database Systems, vol. 14,
`No.3, Sep. 1989, pp. 291-321.
`the
`Annevelink et aI., "Object SQL-A Language for
`Design and Implementation of Object Databases", Jan. 3,
`1994, pp. 1-21.
`Chen, P., "Entity-Relationship Approach to Information
`Modeling and Analysis", International Conference in Wash(cid:173)
`ington, D.C., Oct. 12-14, 1981, pp. 49-72.
`Wiederhold, G.,
`"Database Design Appendix B",
`McGraw-Hill, 2001, pp. 689-698.
`Hanks, D.R., "The Payoff of Modest Price Adjustments,"
`(Abstract only), Bank Marketing, vol. 12, No.9, p. 13" Sep.
`1980.
`Fishman et aI., "Overview of the Iris DBMS", Association
`for Computing Machinery, Inc., pp. 219-250.
`Halper et aI., "An OODB "Part" Relationship Model", 10
`pages.
`Kim et aI., "Feature of the Orion Object-Oriented Database
`System", pp. 251-282.
`Kim et aI., "Evaluation ofthe Object-relational DBMS Post(cid:173)
`gres .1. Administrative Data", Computing Science, Oct.
`1994, pp. I-52.
`Hendler, James A. Expert Sytems: The User Interface. Albex
`Publishing Corporation. Norwood, NJ. 1988. pp. 31, 46-47,
`109-110,113 and 132-134.
`Rose, Peter S., et al. Financial Institution, Understanding
`and Managing Financial Services, 4th Edition, Richard D.
`Irwin, Inc., 1993. pp. 1-217;328-356;423-446;659-792.
`Parsaye, Kamran & Chignell, Mark. Expert Systems For
`Experts. John Wiley & Sons, 1988. pp. 35-60, 177-178,
`191-210 and 295-309.
`Howcroft, "Contemporary issues in UK bank delivery sys(cid:173)
`tems"., Inter. Jour. of Service Industry Management, vol. 3,
`No. I, pp. 39-56, ISBN 096-4223,1992.
`"The Smart Card's Chief Advocate", Credit Card Manage(cid:173)
`ment, vol. 10, No. I, p. 26+, ISBN: 0896-9329, 1992.
`Bharadwaj et aI., Determinants of success in service indus(cid:173)
`tries: a PIMS-based empirical investigation, Journal of Ser(cid:173)
`vice Marketing, v7n4, pp. 19-40, 1993,23 pages from Dia(cid:173)
`log file 15, acc. # 00813287.
`Cattell, R. and Rogers, T., "Combining Object-Oriented and
`Relational Models of Data", 1986 International Workshop
`on Sep. 26, 1986, pp. 212-213.
`Rumbaugh, J., "Relations as Semantic Constructs in an
`Object-Oriented Language", OOPSLA '87 Proceedings,
`Oct. 4-8, 1987, pp. 466-481.
`Dewan et al. "Engineering the Object-Relation Database
`Model in a-Raid", Lecture Notes in Computer Science, 3rd
`International Conference-Paris, Jun. 21-23, 1989, pp.
`389-403.
`
`Blaha et aI., "Relational Database Design using an Object(cid:173)
`Oriented Methodology", Communications of the ACM, Apr.
`1988, vol. 31, No.4, pp. 414-427.
`Wiederhold, G., "Views, Objects, and Databases" Computer
`Database Architecture, Dec. 1986, pp. 37-44.
`Mark et aI., "Metadata Management", Computer Database
`Architecture, Dec. 1986, pp. 26-36.
`Osborn et aI., "The Design of a relational Database System
`with Abstract Data Types for Domains", ACM Transactions
`on Database Systems, vol.
`II, No.3, Sep. 1986, pp.
`357-373.
`Whang et aI., "Query Optimization in a Memory-Resident
`Domain Relational Calculus Database System", ACM
`Transactions on Database Systems, vol. 15, No. I, Mar.
`1990, pp. 67-95.
`Finkelstein et aI., "Physical Database Design for Relational
`Databases", ACM Transactions on Database Systems, vol.
`13, No. I, Mar. 1988, pp. 91-128.
`Takahashi, J., "Hybrid Relations for Database Schema Evo(cid:173)
`lution", IEEE, 1990, pp. 465-470.
`Khoshaflan, S. and Copeland, G., "Object Identity", Micro(cid:173)
`electronics and Computer Technology Corporation, pp.
`37-46.
`Rowe, L. and Stonebraker, M., "The POSTGRES Data
`Model", Computer Science Division, EECS Department,
`University of California, pp. 1-21.
`Stonebraker, M. and Moore, D., "Object-Relational DBMSs
`The Next Great Wave", Morgan Kaufman Publishers, Inc.,
`1996, pp. 56-61.
`Anon., "Future of European Payment Systems? Integrating
`the Card, ATM's, and Eurocheque," (Abstract only), World
`of Banking, vol. 9, No.2, p. 19, Mach/Apr. 1990.
`Nadler, P.S. "Comment: Pitfalls of Relationship Banking,"
`(Abstract only) American Banker, p. 4, Feb. 3,1992.
`Stuchfield, N., et aI., "Modeling of Profitability of Customer
`Relationships: Development and Impact of Barclays de
`Zoete Wedd's Beatrice," Journal of Management Informa(cid:173)
`tion Systems, vol. 9, No.2, p. 53, Fall 1992.
`Toby J. Teorey, et aI., A Logical Design Methodology for
`Relational Databases Using the Extended Entity-Relation(cid:173)
`ship Model, Computing Surveys, vol. 18, No.2, Jun. 1986,
`pp. 197-222 ("Teorey").
`Daniel R. Dolk, et aI., A Relational Information Resource
`Dictionary System, Computing Practices, Communications
`oftheACM (Jan. 1987).
`M.M. Zloof, Query-by-Example: A Data Base Language,
`IBM Systems Journal, No.4 (1977).
`Rudolph Munz, "Das WEB-Modell", (translated pages), pp.
`155-156, Fig. 10.2.1, (1976) ("MullZ Ill"), with English
`translation.
`Gio Wiederhold, "Database Design Second Edition", Dis(cid:173)
`7-3-1,
`7-3-7,
`closes Definition Tables,
`Sections
`7-4-4,7-4-5, and 9-7-6 and Figs. 8-5, 8-7, 8-9 (1995).
`Pin-Shan Chen, The entity-relationship model-A basis for
`the enterprise view of data 77 (1977).
`Mark L. Gillenson, Database Step-by-step 141-42, 2d Ed.
`(1990).
`The IBM Dictionary of Computing Terms 87 (8th Ed. 1987).
`Webster's New World Dictionary of Computer Terms 107
`(3d Ed. 1988).
`Rudolph MullZ, "Das WEB-Modell" (English Translated
`pages), Chapter 10 (1976),18 pages.
`Introduction to NonStop SQL, Tandem Computers, May
`1988, pp. 1-3-19.
`
`003
`
`

`

`US RE40,520 E
`Page 4
`
`Adiba et a!., "Database Snapshots", Proceedings of the 1980
`International Conference on Very Large Data Bases, IEEE
`1980, pgs. 86-91.
`"Join Index, Materialized View, and
`Blakeley et a!.,
`Hybrid-Hash Join: A Perfonnance Analysis", Technical
`Report No. 280,
`Indiana University Computer Science
`Department, IEEE 1990, pgs. 256-263.
`
`E1masri et a!., "Fundamentals Of Database Systems", 1989.
`Hainaut, J. L., "Theoretical And Practical Tools For Data
`Base Design", Proceedings of the Seventh International
`Conference on Very Large Data Bases, IEEE 1981, pgs.
`215-224.
`* cited by examiner
`
`004
`
`

`

`u.s. Patent
`
`Sep.23,2008
`
`Sheet 1 of 19
`
`US RE40,520 E
`
`I
`
`program
`(Source Code)
`
`~ ~~
`
`~ 112
`
`112d
`
`Compiler
`
`""'114
`
`.-------- -----------------------1~115
`L
`
`122
`
`_
`
`BULK STORAGE
`(Binary Code Strings)
`
`~~
`~-...r-...r~
`~~...............
`
`~~
`~-...r-...r~
`
`~~
`~
`
`Acce~s_CQotr~J
`P-r:9.gr.aro
`132
`Data
`(Object Code)
`r------,
`CPU
`~ 14-~.ld......I~
`14--=:=:.:;:-L---..t
`Addr
`~ 14-..L.llI!¥.!r_--l
`~
`~ 121
`~ r-..../'V" ""'120
`120d
`I
`~----------------------~
`
`131
`
`~ 0
`
`~1
`
`30
`
`"Please find
`all books
`having xxx·
`
`40
`
`1. - - - - -
`2.
`3.
`
`50
`
`UPQATE INPUT:
`(Sal)
`
`aplease add
`new books
`yyy-zzz'
`
`60
`
`FIG. 1A
`(Prior Art)
`
`005
`
`

`

`u.s. Patent
`
`U.S. Patent
`
`Sep.23,2008
`Sep. 23, 2008
`
`Sheet 2 of 19
`Sheet 2 of 19
`
`US RE40,520 E
`US RE40,520 E
`
`............... ,
`
`,
`
`-t 0>
`
`, ...
`
`.2398
`
`£2
`
`C'\I
`..................................................................
`fl
`
`I
`
`I
`
`CO
`
`'0::;
`
`..... ~ -t
`
` €<3im:.9“.
`<X:....
`•
`u.. --
`(!J 0
`- [l.
`
`T""
`
`.....
`
`w5—
`
`:255$922
`~j .......--~::J::;::=~~-J..:... ':":''::'':'':''::'':'':''::'':':".:..:''..:..'.:..:.'..:..'':':~~>.:':',:",:":.:,'.:..:''.;.':..:.~.:.:..:.:.•.:.:.':':"':':'':.:,'.:..:'':.:,':":"':":"f
`223
`053
`
`o
`
`llIllllUl|lllIllum
`
`I
`
`006
`
`006
`
`
`
`

`

`~7
`
`J).
`
`•~ ~~~=~
`
`rFJ
`('D
`'?
`N
`~(H
`
`No
`
`oQ
`
`O
`
`('D
`
`(H
`
`rFJ=(cid:173)
`('D.....
`o........
`
`\0
`
`dr
`
`Jl
`
`~~
`
`U"l
`
`,,=
`N=
`
`~
`
`131
`
`130a
`~
`
`zw
`
`132
`
`FIG. 2A-1
`(Prior Art)
`
`I
`
`KEY-SEQUENCED ORGANIZATION:
`(KSO)
`Record No. _1_
`..--------------------------------
`2 5
`I
`Boo~'s
`Location
`
`Author's
`Name
`
`P11
`
`Book's
`Title
`
`P13
`
`)
`
`230
`
`232
`Name
`Threading
`Pointer
`
`L 11
`
`P12
`
`L 12
`
`236
`Location
`Threading
`Pointer
`
`L 13
`
`.
`
`Record.Addr 11
`
`Record.Addr 12
`
`Record.Addr 13
`
`I
`
`I1IIIII,
`
`I
`
`-----------------~------------~
`Record No.
`PR 12
`2
`~-------
`
`-
`
`I
`1
`
`I
`
`Author's
`Name
`
`P21
`
`---
`
`Book's
`Title
`
`-----
`
`P23
`
`P
`25
`
`II
`
`----_:__
`
`2~------- I
`8oo~'s
`Location
`--- -----
`
`007
`
`

`

`~7
`
`J).
`
`•~ ~~~=~
`
`rFJ
`('D
`'?
`
`N(
`
`.H
`
`~ NooQ
`
`O
`
`('D
`
`,j;o,.
`
`rFJ=(cid:173)
`('D.....
`o........
`
`\0
`
`240
`
`I
`
`I
`
`I
`
`I)
`I
`I
`i
`
`-242
`Name
`Thre,ading
`Pomter
`
`l21
`
`R_ecord,~ddr ~1
`
`p
`
`22
`
`P
`24
`
`L22
`
`R~co~rd.Addr 2~
`
`Location
`Thre,ading
`POinter
`
`L23
`
`_24S __l_-
`I
`I
`R~cord~ddr 2~J
`
`I
`
`I
`
`I
`
`Record No. _3_
`
`~-----------------
`I
`
`Author's
`Name
`
`P31
`
`Book's
`Title
`
`PR 23
`-------------
`255
`Book's
`Location
`
`I
`
`I
`
`IIIIIIII
`
`)
`
`250
`
`252
`Name
`Threading
`Pointer
`
`L 31
`
`P32
`
`254
`Tttle
`Threading
`Pointer
`L32
`
`P34
`
`256
`Location
`Threading
`Pointer
`
`L 33
`
`.
`Record.Addr 31
`
`.
`Record.Addr 32
`
`.
`Record,Addr 33
`
`__ ___ __________ __ _ ___ __ __ ______ ---1
`
`I
`
`dr
`
`Jl
`
`~~=1
`
`1.
`N=
`
`~
`
`FIG.
`2A-1
`FIG.
`2A-2
`
`FIG.2A
`
`FIG. 2A-2
`(Prior Art)
`
`008
`
`

`

`~7
`
`J).
`
`•~ ~~~=~
`
`rFJ
`('D
`'?
`
`N(
`
`.H
`
`~
`
`No
`
`oQ
`
`O
`
`('D
`
`rFJ=(cid:173)
`('D.....
`Ul
`o........
`
`\0
`
`dr
`
`Jl
`
`~~=1
`
`1.
`N=
`
`~
`
`285
`
`Book's
`Location
`
`-
`~P8023
`-
`4~ Book's ~ Book's
`Location
`Title
`
`•
`~t
`
`Book's
`Title
`
`-
`
`Slot
`No._1
`
`Slot
`No...L
`
`Authors
`Name
`
`Author's
`Name
`
`271
`
`<;
`
`I
`21Q
`
`281
`
`~
`
`I
`
`gao
`
`Slot
`No....1-
`
`Author's
`Name
`
`FIG. 28-1
`(Prior Art)
`
`130b
`
`131
`
`2~
`
`132
`
`RELATIVE·TABLE ORGANIZATION:
`(RTO)
`
`•
`~ Book's
`Title
`
`273
`
`t----1
`
`275
`
`Book's
`Location
`
`-
`~P8012
`-
`
`283
`n---1.
`
`009
`
`

`

`u.s. Patent
`
`US. Patent
`
`Sep.23,2008
`Sep. 23, 2008
`
`Sheet 6 of 19
`Sheet 6 0f 19
`
`US RE40,520 E
`US RE40,520 E
`
`____———
`~---------------------
`
`955$
`
`~~..;::;
`
`en C_
`0
`8B
`00 0
`---J
`
`I
`
`en
`
`LO
`
`rP
`mam
`
`8:8305
`£08.xoomw
`I'rv· ::!:w:::Q) l~
`
`N-mN
`Ea:
`....o•
`(!)~-u..
`0E
`
`·C
`
`CD
`N
`
`mm.0.”—
`
`CD
`LO
`
`mmoni
`rP
`
`o.~
`
`o~m
`
`-I"
`
`.
`
`en
`... Q)
`meZ
`°E£(lj
`::JZ«
`
`-o
`
`(J)
`
`~Ew
`
`II
`
`II
`
`~
`18
`'0:In..
`V
`
`Em
`
`86
`
`m.oz
`
`~----------------------
`
`010
`
`010
`
`

`

`~
`7J).
`•
`
`~ ~~~
`
`=
`
`~
`
`rFJ
`('D
`'?
`
`N(
`
`.H
`
`~
`
`No
`
`oQ
`
`O
`
`('D
`
`rFJ=(cid:173)
`('D.....
`......:J
`o........
`
`\0
`
`dr
`
`Jl
`
`~~=1
`
`1.
`N=
`
`~
`
`G1 Pfb~n H ~~ I
`G-{~f~~nH g~ I
`o---------,
`L44l,
`
`L 44
`----1
`
`II
`
`1
`
`1 H~~~eH~b~el
`I 2 H~~~eH~g~el
`I 3 HNI;~eH~~~e I
`Name L_I Home
`="2"
`--.--
`I g__~.i1J P42
`,
`
`0
`
`_
`
`J~
`
`FIG. 3-1
`(Prior Art)
`
`300
`
`130c
`~
`
`~
`
`131
`
`132
`
`331
`
`- ----
`
`- - ---
`
`I
`
`(',
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`,
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`I
`
`IIrIII
`
`l
`
`' - - - -
`
`I_.J
`L41
`
`011
`
`

`

`~7
`
`J).
`
`•~ ~~~=~
`
`rFJ
`('D
`'?
`
`N(
`
`.H
`
`~
`
`No
`
`oQ
`
`O
`
`('D
`
`QO
`
`rFJ=(cid:173)
`('D.....
`o........
`
`\0
`
`dr
`
`Jl
`
`~~=1
`
`1.
`N=
`
`~
`
`. . . . . , - - - - - - - -
`I
`
`I
`I
`
`I
`
`---------------r--------------
`I
`I
`I
`I
`I
`I
`I
`__
`'
`( ,
`I
`II!
`I I IL43 + / L48
`L zz
`
`I
`I
`
`I
`I
`
`I
`I
`
`_.J
`
`L...l
`
`...
`
`. /
`
`G:-,---:
`G: nvv,'"vv:
`G :---j--- :
`G, ..__._-- I
`
`- - - - - - - - - - - - -
`
`.,
`
`--r--------
`I
`Table of
`C
`~ 1....
`I
`~
`
`I
`
`353
`
`I
`I
`
`1
`
`ID
`
`SN
`
`I
`B1
`I
`OwnerHVehicleI
`I
`I
`II
`L_-G1 ~~! Mve~~le ~---~ 46J
`~ or~er~P47
`
`ooo0
`
`1 °f~er Hve~~le I
`
`I
`
`FIG.
`3-1
`FIG.
`3-2
`
`I FIG. 3
`
`FIG. 3-2
`(Prior Art)
`
`012
`
`

`

`u.s. Patent
`
`Sep.23,2008
`
`Sheet 9 of 19
`
`US RE40,520 E
`
`FIG. 4A
`
`RELATION R·1
`
`013
`
`

`

`u.s. Patent
`
`Sep.23,2008
`
`Sheet 10 of 19
`
`US RE40,520 E
`
`FIG. 48
`
`'s business
`{ 1:m }-y
`
`014
`
`

`

`u.s. Patent
`
`Sep.23,2008
`
`Sheet 11 of 19
`
`US RE40,520 E
`
`130-RP
`
`FIG.5
`
`131
`
`132
`
`500
`ENT.DEE )~ble
`
`Entity
`Type
`No.
`=
`Slot No.
`.1.
`
`.2.
`
`.3.
`
`.4.
`
`Entity
`Class Name
`Abbreviation
`(Full Name)
`
`CU
`(Customer)
`
`AD
`(Address)
`
`AC
`(Account)
`
`SU
`(Supplier)
`
`.ETN
`
`I
`
`EA
`t
`
`50Da
`
`Name of
`Single Table
`where instances
`are stored
`
`~Com~an~
`:
`@ddres@
`
`wccoun~
`
`€£Compa~
`
`I
`
`EiT
`
`t
`
`500b
`
`015
`
`

`

`u.s. Patent
`
`Sep.23,2008
`
`Sheet 12 of 19
`
`US RE40,520 E
`
`130-RP
`
`FIG. 6A
`
`131
`
`32
`
`('s Business)
`
`.1
`(Customer)
`
`-BU- @
`-Ow- ~ .3
`-SM- ~ .3
`~ .1
`
`Name of
`Relation R I ti
`Single Table
`e a on
`Type
`Class Name where instances Head Entity
`No.
`of Relation T~e Number T(Fpe Number
`Abbreviation
`=
`(ull Name)
`(Full Name)
`are stored
`Full Name)
`Slot
`No.
`.1
`
`First
`
`Tail Entity 600Y
`
`Cardinalit¥
`
`.2
`(Address)
`
`I
`
`{1:m} Y
`
`IIII
`
`.2
`
`.3.
`
`.4.
`
`('s Owning)
`
`('s 5t.
`Mailing)
`-HQ-
`('S Main
`Headqtrs)
`
`(Account)
`
`(Account)
`
`(Customer)
`
`.1
`(Customer
`
`J
`
`{1:1 }Y
`
`.2
`(Address)
`
`.2
`(Address)
`
`{1:1 } N
`
`{1:1 } y
`
`.RTN
`
`-RA-
`
`RiT
`
`ETN h
`
`ETN
`
`t1
`
`) 600) 60 ) 600d)
`
`600
`
`Optional
`Second thru Fifth
`Tail Entity
`Names
`(type)
`600e
`
`IIII
`I
`
`II
`
`Mandatory
`Head
`Coupling
`600g
`
`016
`
`

`

`u.s. Patent
`
`Sep.23,2008
`
`Sheet 13 of 19
`
`US RE40,520 E
`
`130-RP
`
`131
`
`132
`
`FIG. 68
`
`.6QQ
`REl.D
`
`T2
`(602)
`
`.4
`(Supplier
`
`T3
`(603)
`
`j .5
`
`(Area)
`
`Tail-Activation
`Mask
`(606)
`
`T5
`(60S)
`
`T4
`(604)
`.6
`.3
`(Phone (Account) .0000
`No.)
`
`Optional
`Second thru Fifth
`Tail Entity
`Names
`Region
`~ \
`
`.1
`
`.2
`
`.3
`
`.4
`
`.5
`
`\
`)
`)
`
`')
`)
`<
`\
`)
`<
`
`tRelation
`Type
`No.
`
`(Branch)
`
`J .7
`j
`
`.7
`(Branch)
`
`.8
`~ontact
`erson)
`
`.6
`.8
`(Phone (Contact
`No.)
`Person)
`
`\
`\
`
`Entity
`Type Number
`(and Name)
`
`.3 j
`
`(Account
`
`T1
`
`.0000 [
`[
`
`.0000
`
`•• oeo
`
`/
`
`?
`)
`\
`
`S
`)
`\
`?
`)
`'\
`
`/
`
`00000
`I
`I I
`
`dJ \\
`
`T2
`
`T3
`
`T4
`
`T5
`
`017
`
`

`

`~7
`
`J).
`
`•~ ~~~=~
`
`rFJ
`('D
`'?
`
`N(
`
`.H
`
`~
`
`No
`
`oQ
`
`O
`
`('D
`
`,j;o,.
`
`rFJ=(cid:173)
`('D........
`o........
`
`\0
`
`dr
`
`Jl
`
`~~=1
`
`1.
`N=
`
`~
`
`_
`
`FIG. 7-1
`
`130-AP
`
`700
`
`REQUEST
`for:
`(a)Sea~ch
`(b) InqUiry -
`(c) Update
`(d) Restructure
`-Schema
`Involving
`there~~t~_nShiP:
`
`~-----------------------------------,
`
`I
`I
`i
`
`780
`
`~
`
`740
`INQ.DEF
`-Relation- Level
`-Entity-
`L746 abc ~ ~
`--------r .11 ETN II EiN HRTNI[]j[] w
`I
`I .2 [][]~[JJ OJ
`/3~~ . L!J
`I"A""nlrAL.rCi'ilDJ r7l
`\
`
`L.___
`
`I
`
`I
`I
`
`I
`I
`
`I
`I
`
`I
`....
`
`I
`
`I
`I
`
`"
`
`I
`
`I
`
`I
`I
`
`.4~J] I-su-I~:g]
`.
`.
`.51 cul~ I-SU-II ADI~
`
`L744
`
`"-
`
`.
`
`ENT.DEF
`r-b,
`2. L.@J T.Addresses
`
`I
`I
`
`;
`
`__
`r-.
`I
`,--.....,.,,-~,
`I
`I
`
`I
`-----..L.
`
`I
`,
`I
`l . -
`
`11.4~~W ~
`I~~
`I ~
`AiN
`) Head
`ReI. Tail(1)
`lYRe. __El
`~ __Ei
`AiT! @~~~~ ~743
`r:::1-:l r;;;;-t r::J:ln ! KSO
`• 1L733 ~
`r---~EL~~-~_~_I~~I~I::~:II::I~: I'
`t .3lQ!J JJ ~ ~.1J
`!
`I
`1
`I ENT.DEF
`I
`rb b
`1. L9!J IT.Companies
`I
`I
`I
`\
`
`600
`
`I
`
`I
`1 , . , - - -
`\
`L 751 \
`_______ 1
`I
`
`018
`
`

`

`~7
`
`J).
`
`•~ ~~~=~
`
`rFJ
`('D
`'?
`N
`(.H
`
`~ N0
`
`0
`QO
`
`rFJ
`
`('D
`
`=-
`('D.....
`....
`Ul
`....
`0
`....
`
`\0
`
`---------\
`~
`
`- - I - - - - - - - - - - -
`
`.... -
`
`! .6~.5 ~ID.4 ! ---,-----.,------
`! ETN~ R~T~
`I
`! L752
`EiT-1=
`EiT-2= t
`T.Companies L
`I
`1------.1 I~~ggr~~~§.
`710
`720
`I
`
`!
`
`-----j
`I
`
`I
`
`i
`
`j
`
`Allen's Automobiles
`
`Bob's Books Inc.
`
`"
`
`I
`
`I
`
`I
`
`I
`
`I
`!
`
`I
`I
`
`I
`i
`
`i
`I
`
`I
`
`I
`
`.11 220 Literature Street
`
`.21
`
`445 Medical Plaza
`
`Computer Center ltd.
`
`Dr. Dogood P.C.
`
`Expert Electronics
`
`Fred's Furniture
`
`Ei
`
`,
`
`i
`I
`I
`I
`I
`I
`
`I
`I
`
`II
`I"'-.J L732
`
`:~7M
`
`106 Car Corner
`
`I
`.3
`I
`I
`I
`I
`'------.4 555 Transistor Lane
`I
`L734
`.
`
`.5 386 Business Machine Dr.
`
`.6
`
`.EiN
`
`1000 Office Plaza
`
`Ei
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`,
`,
`i
`
`i
`I
`I
`I
`I
`I
`I
`I
`
`dr
`
`Jl
`
`~~=1
`
`1.
`N=
`
`~
`
`II
`-
`a
`I
`I
`IL_________________
`
`FIG. 7-2
`
`FIG.
`7-1
`I FIG.
`7-2
`
`I FIG. 7
`
`019
`
`

`

`u.s. Patent
`
`Sep.23,2008
`
`Sheet 16 of 19
`
`US RE40,520 E
`
`BULK STORAGE
`(Binary Gode Strings)
`
`Access Control
`Program
`(S~
`~
`
`130-R
`
`130"~
`
`RELjDEF
`
`RElrDEF
`
`jRiT-1\ jRiT-2\ r
`
`~~~
`
`~ 812
`
`812d
`
`One-Time
`Compiler ~814
`
`ENTiDEF
`
`ENT1DEF
`
`ENTfEF
`
`EiT-1
`
`EiT·2
`
`EiT-3
`
`132
`
`150
`
`870
`
`FIG. 8
`
`Access Control
`Program
`(~I4-...Iol.al.l~
`~14-~.I.LL......-1
`
`CPU
`
`II
`
`~ !
`110 :
`J
`
`__
`
`.
`
`.----
`
`I
`-1
`
`~:
`
`~
`820d
`
`- - - - - - - - - -
`
`QUERY INPUT:
`(Sal)
`·Please find
`ali books
`having xxx·
`
`:
`
`1
`1
`
`140
`
`1. - - - -
`2. ----
`3. ----
`
`UPDATE INPUT:
`(SOL)
`"Please add
`new books
`yyy-zzz"
`
`160
`
`Restructure
`Schema:
`(Sal)
`"Please add
`new REl
`Rnn-Rmm"
`
`020
`
`

`

`~7
`
`J).
`
`•~ ~~~=~
`
`rFJ
`('D
`'?
`
`N(
`
`,H
`
`~
`
`No
`
`oQ
`
`O
`
`rFJ=(cid:173)
`('Da....
`o........
`
`......:J
`
`\0
`
`dr
`
`Jl
`
`~~=1
`
`1.
`N=
`
`~
`
`_
`
`70
`
`h
`
`'"
`
`(730)
`
`{
`.'.;
`
`~;:
`
`HIT
`sRiT1
`RELATION STORAGE AND SEARCH MEANS
`' ~ '
`CR' ~~
`
`JI511\ ~ JJJI
`
`____ ... _
`
`0. __
`
`_
`
`:::::::::::LLiL
`
`901
`
`910
`
`9.00
`
`Starting QUERY
`
`FIG. 9-1
`
`I
`
`960
`
`Lvl-1 ( ETN4' ??
`
`- RTN4- ?)
`
`Abt2r.eYi.~d..Re.sutlS-List
`
`.:.:
`....
`
`.RTN ~[ffiJ-1 H= II 11= II T2= I
`DD-DDD
`DD-DDD
`
`600
`
`INQUIRY INPUT FORM
`.-L..-902
`INQUIRY GUIDE MEANS
`Lvl-1 (ErN 1- EiN 1- RTN 1- 1).:;:..;··..;:,;:........;..,:(..:;..:..;·;::.::...:::.:::;:...:;:.:;::.~·.:;.';;;·.:;.·i::.:;;.:;:.:::.
`C
`TN 1)
`..'
`;.:.
`sRTN
`Lvl-2?
`- R 2-
`;:.
`1
`':':"'~';''''
`??
`Lvl-3 (; :;; - RTNS- ~ ......:... :~~~
`:i
`:~1
`~~
`915 ~~:
`:~~
`/ ~::;
`.;':
`I."·
`.:~~
`,~::~:
`.~
`
`I- Lvl:2_ Lvl-~ _ -.-JLvl-4
`Ei-2a
`Ei-32a.1
`- - ~ Ei-32a.2
`
`Ei-2b
`
`Ei-32b.1
`Ei-32b.2
`
`_
`
`----....
`1'-
`-- ~kEi-32b.3---,
`
`021
`
`

`

`~7
`
`J).
`
`•~ ~~~=~
`
`rFJ
`('D
`'?
`
`N(
`
`,H
`
`~
`
`No
`
`oQ
`
`O
`
`('D
`
`QO
`
`rFJ=(cid:173)
`('D.........
`o........
`
`\0
`
`r------- 971~1-------------
`
`81
`
`sEiN
`920
`
`Details
`Filter
`
`;.:.::....:...'r'.'
`
`Intermediate Answers
`List Means
`Ei-01
`Ei-02
`Ei-03
`
`80
`
`990
`
`Detailed Resutls Display
`Aliens' Autos--·------106 Car Comer
`Experfs Electronics---555 Transistor Lane
`Bob's Books In~.------220 Literature Street
`
`950
`
`sETNx
`r
`,
`ENTITY DEFINE MEANS
`.ETN [ill-[§IJ
`D-D
`
`~
`
`ENTIn' STORAGE
`MEANS
`
`IErr-11IEiT-2\IEiT-31
`
`dr
`
`Jl
`
`~~=1
`
`1.
`N=
`
`~
`
`FIG. 9-1
`
`I
`
`FIG. 9-2
`
`I FIG. 9
`
`FIG. 9-2
`
`022
`
`

`

`~7
`
`J).
`
`•~ ~~~=~
`
`rFJ
`('D
`'?
`
`N(
`
`.H
`
`~ NooQ
`
`O
`
`('D
`
`\0
`
`rFJ=(cid:173)
`('D.........
`o........
`
`\0
`
`dr
`
`Jl
`
`~~=1
`
`1.
`N=
`
`~
`
`..
`
`Ending
`Instances
`H
`Ii,i,k/E1
`~
`~~
`
`~ Accoun
`
`K-i
`.2>3 ~
`
`10,p,q!E1
`~
`~~
`
`e'r'S,t'E1
`
`Ix,y,zlE1
`
`Starting
`Instance----------I..~
`
`IalE1 HSF'
`
`\.../.
`
`I
`
`Level ·1
`Intermediate
`Instance's}
`T
`Ib/E2
`~~
`~~
`
`Level-2
`.. Intermediate
`Instance's)
`
`'s Holder
`
`Z¥
`I" k1R1 R-S~
`I,j,
`
`~ =-
`
`Ic,d1R2
`
`V Group
`Ie dlE3
`Ib /E3 '
`~ ~
`~~
`
`II,m,nlR1
`
`'s Holder
`<~=
`qJR"2>3<;
`O,p,1
`
`I
`
`Only one of tails, 11, T2, T3,
`is active for any single starting
`instance of account
`
`FIG. 10
`
`(j~F"""';':;;;~::;;:=::J perso;-
`
`Ie f/E2
`,
`
`r,s,tIR1
`
`)C==~7===
`Ic,dlR3(
`
`Company
`
`Ix,y,zlR1
`
`~ ~ 's Holder e'" m'nlE1
`1 P ~ 's Holder
`! - ~ Aceoun
`~ Of ~ 'sHolder e
`2>-SS
`Iu,v,w/E1
`? Accoun
`~1 7 ~
`;;)e
`
`023
`
`

`

`US RE40,520 E
`
`1
`EASILY EXPANDABLE DATA PROCESSING
`SYSTEM AND METHOD
`
`Matter enclosed in heavy brackets [ ] appears in the
`original patent but forms no part ofthis reissue specifica(cid:173)
`tion; matter printed in italics indicates the additions
`made by reissue.
`
`This application is a continuation of application Ser. No.
`08/439,207, filed May II, 1995, now U.S. Pat. No. 5,675,
`779, which is a divisional of Ser. No. [08/083,361] 081083,
`861, filed Jun. 28, 1993, now [issued;] u.s. Pat. No. 5,604,
`899, which issued on Feb. 18, 1997, which is a continuation
`ofSer. No. 07/526,424, filed May 21,1990, now abandoned.
`
`BACKGROUND OF THE INVENTION
`
`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 dis(cid:173)
`closed program modules are subject to copyright protection.
`The copyright owner has no objection to the facsimile repro(cid:173)
`duction by anyone of the patent document (or the patent
`disclosure as it appears in the files or records of the u.s.
`Patent and Trademark Office) for the sole purpose of study(cid:173)
`ing 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(cid:173)
`executable form.
`
`Field ofInvention
`
`The present invention relates generally to computer data(cid:173)
`base management systems and more specifically to appara(cid:173)
`tus and methods for modifying and searching through large
`scale databases at high speed.
`
`Description of Related Art
`
`Modem computer systems are capable of storing volumi(cid:173)
`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 textural information stored in a
`conventional encyclopedia or in the telephone directory of a
`large city. Moreover, modem computer systems can sift 50
`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 finan(cid:173)
`cial 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 organization of the stored
`information is needed in order to minimize retrieval time.
`The methods by which pieces of information are orga(cid:173)
`nized within a computer, searched through or reorganized,
`often parallel techniques used by older types of manual
`
`2
`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 posi(cid:173)
`tioned such that each card is directly adjacent to no more
`than two others (for each typical examination there is a pre(cid:173)
`ceding card, the card under examination and a following
`card in the stack). On the front surface of each index card a
`10 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
`15 "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
`20 then by title. This defines a "key-sequenced" type of data(cid:173)
`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
`25 examined immediately after its alphabetically preceding
`card and immediately before is alphabetically succeeding
`card. When a new book is acquired, the key-sequenced data(cid:173)
`base is easily "updated" by inserting a new card between two
`previously created cards. Similarly, if a book is removed
`30 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
`35 alphabetically ordered set of index cards and retrieve the
`requested information. However, if a library use