`Ex. 1004 / Page 1 of 89
`
`
`
`Docker $607P/PTO Filings/Spec wpd
`
`SEARCH-ON-THE-FLY WITH MERGE FUNCTION
`
`Related Applications
`
`This application is a continuation-in-part ofApplication Serial Number 09/513,340,
`
`filed February 25, 2000,entitled Search-On-The-Fly/Sort-On-The-Fly Search Engine, which
`
`is hereby incorporated by reference.
`
`Technical Field
`
`The technicalfield is information managementsystems,interfaces, andmechanisms, and
`
`methods for searching one or more databases.
`
`Background
`
`In the most general sense, a database is acollection ofdata. Various architectures
`
`have been devised to organize data in a computerized database. Typically, a computerized
`
`database includes data stored in mass storage devices, such as tape drives, magnetic hard disk
`
`drives and optical drives. Three main database architectures are termedhierarchical, network
`
`and relational. A hierarchical database assigns different data typesto different levels ofthe
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`+12
`
`13
`
`14
`
`5
`
`
`
`15 hierarchy. Links between data items on onelevel and data items onadifferent level are simple
`
`
`
`{3
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`22
`23
`24
`
`25
`
`26
`
`27
`
`28
`
`and direct. However, a single data item can appear multiple times in a hierarchical database
`
`and this creates data redundancy. To eliminate data redundancy, anetwork database stores
`
`data in nodes having direct access to any other node in the database. There is no need to
`
`duplicate data since all nodes are universally accessible. In arelational database,the basic unit
`
`ofdata is a relation. A relation correspondsto a table having rows, with each row called a
`
`tuple, and columns, with each column called an attribute. From a practical standpoint, rows
`represent records ofrelated data and columnsidentify individual data elements. The order in
`which therows and columns appearinatablehas no significance. Inarelational database, one
`can add anew column to a table without having to modify older applicationsthat access other
`
`columnsin the table. Relational databases thus provideflexibility to accommodate changing
`
`needs.
`
`All databases require a consistent structure, termed a schema, to organize and manage
`
`the information. In arelational database, the schema is a collection oftables. Similarly, for each
`
`Ex. 1004 / Page 2 of 89
`
`Ex. 1004 / Page 2 of 89
`
`
`
`—_
`
`oOoNNDNNHPWNY
`
`
`
`Docket $607/PTO Filngs/Spee wpd
`
`table, there is generally one schemato whichit belongs. Once the schemais designed, atool,
`known as a database management system (DBMS),is used to build the database and to
`operate ondatawithinthe database. TheDBMSstores,retrieves and modifies dataassociated.
`with the database. Lastly, to the extent possible, the DBMSprotects data from corruption and
`
`unauthorized access.
`
`Ahumanusercontrols the DBMSbyproviding a sequence ofcommandsselected from
`adata sublanguage. The syntax ofdata sublanguages varies widely. The AmericanNational
`StandardsInstitute (ANSI) andthe International Organization for Standardization (ISO) have
`adopted Structured English Query Language (SQL) as a standard data sublanguage for
`relational databases. SQL comprisesa data definition language (DDL), a data manipulation
`language (DML),anda data control language (DCL). The DDL allowsusers to define a
`database, to modify its structure and to destroy it. The DML providesthetools to enter,
`modify and extract data from the database. The DCL providestools to protect data from
`corruption and unauthorized access. Although SQLis standardized, most implementations of
`the ANSIstandard have subtle differences. Nonetheless, the standardization of SQL has
`
`greatly increasedthe utility of relational databases for many applications.
`Although accessto relational databasesis facilitated by standard data sublanguages,
`usersstill must have detailed knowledge ofthe schemato obtain needed information froma
`
`database since one can design many different schemasto representthe storage ofa given
`collection ofinformation. For example,in an electronic commerce system, productinformation,
`
`such as product SKU,product name,product description, price, and tax code, may be stored
`ina single table within arelational database. In anotherelectronic commerce system, product
`SKU,productname,description, andtax code maybestored in one table while product SKU
`and productpriceare stored in a separate table. In this situation, a SQL query designed to
`retrieve aproductprice from a databaseofthefirst electronic commerce system is notuseful
`for retrievingthe price for the same productin the otherelectronic system’s database because
`
`the differences in schemas require the use ofdifferent SQL queriesto retrieve productprice.
`
`-2-
`
`1
`
`sagenelssche
`
`Ex. 1004 / Page 3 of 89
`
`Ex. 1004 / Page 3 of 89
`
`
`
`1
`
`2
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`27
`
`Docket 5607/PTO Filtings/Spec wod.
`
`As aconsequence, developersofretail applications accessing product information from
`
`relational databases may have to adapt their SQL queries to each individual schema. This, in
`turn, preventstheirapplicationsfrombeingusedinenvironments wherethere are awidevariety
`
`of databases having different schemas, such as the World Wide Web.
`
`A further problem with conventional search engines is a tendency to return very large
`
`amounts ofdata, or to require the search parameters to be narrowed. When large amounts of
`
`data are presented, the display may take many “pages”before all data is seen by the user. The
`
`time and expense involved in such a data review maybe significant.
`
`Summary
`
`A Sort-on-the-Fly/Search-on-the-Fly search engine (hereafter, search-on-the-fly
`
`search engine) providesan intuitive meansfor searching databases, allowing a user to access
`
`data in the database without having to know anything about the database structure. A user
`
`selects a desired search term, and a database managersearchesthe databasefor all instances
`
`ofthe desired term, even ifa specific file or table does not contain the instance. For example,
`
`ifauser wants to search the database using the nameofspecific individualas a database entry
`
`point, the database managerwill search the databaseusing the desired name,and will organize
`
`the search results so thatall entries associated with that nameare displayed. The database
`
`need not have a specific file (in a flat database) or atable (in arelational database) ofnames.
`
`The user may perform further on-the-fly searches to narrow or focus the search results, or for
`
`other reasons. For example, given search results for all namesthat include the name “Smith,”
`
`the user maythen decide to search for all “Smiths”that include an association to an addressin
`
`New Jersey. The search-on-the-fly search engine then conductsa further search using this
`
`criteria and produces a second search result. Further narrowing or broadening ofthe search
`
`are permitted, with the search-on-the-fly search engine returning results based on any new
`
`criteria.
`
`In an embodiment, the search-on-the-fly search engine uses graphical user interfaces
`
`(GUIs) and one or more icons to makethe search processas efficient as possible. The GUIs
`
`3.
`
`
`
`
`3
`
`Ex. 1004 / Page 4 of 89
`
`Ex. 1004 / Page 4 of 89
`
`
`
`Docket 5607/PTO Filings/Spec wpd
`
`1
`
`may incorporate one ormore pull down menus ofavailable search terms. As auser selects an
`
`
`
`2 item fromafirst pulldown menu, a subsequent pulldown menudisplays choices that are
`
`
`
`3
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`available for searching. The process continues until the search engine has displayed a discrete
`
`data entry from the database. The pulldown menusare not pre-formatted. Instead, the
`
`pulidown menusare created “on-the-fly”as the user steps through the searchprocess. Thus,
`
`the search-on-the-fly search engineis inherently intuitive, and allows auser with little or no
`
`knowledge of the database contents,its organization, or a search engine search routine to
`
`execute comprehensive searches that return generally accurate results.
`
`The search-on-the-fly search engine also searches on key words specifiedby the user.
`
`The search-on-the-fly search engine can be used to exclude certain items. The search-on-the-
`
`fly search engine incorporates other advanced features such as saving search results by
`
`attaching a cookie to a user’s computer, and associating icons with the search results.
`
`The search-on-the-fly search engine may be used with both internal and external
`
`databases. For example, the search-on-the-fly search engine may be used with a company
`
`internal database and one or more databases accessible through the Internet.
`
`The search-on-the-fly search engine is user-friendly. With one interface, manydifferent
`
`types of databases or database schemas may be searched or sorted.
`
`Finally, the search-on-the-fly technique, and other techniques discussed above may be
`
`used in conjunction with amethod ofdoing business, particularly abusiness methodthat uses
`
`the Internet as a communications backbone.
`
`Description of the Drawings
`
`The detailed descriptionwill referto the following figures, inwhichlike numerals refer
`
`to like objects, and in which:
`
`Figure | is a block diagram ofa system that uses a search-on-the-fly/sort-on-the-fly
`
`search engine;
`
`Figure 2 is another overall block diagram of the system of Figure 1;
`
`A.
`
`Ex. 1004 / Page 5 of 89
`
`Ex. 1004 / Page 5 of 89
`
`
`
`t
`
`
`
`°
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`27
`
`Docket 5607/PTO Fiings/Spec wpd.
`
`Figure 3 is a detailed block diagram ofthe search engine used with the system of
`
`Figure 2;
`
`Figure 4 is an example of a search-on-the-fly using the search engine of Figure 3;
`
`Figures 5 - 9 are detailed block diagrams of components of the search engine of
`
`Figure 3;
`
`Figure 10 is another example ofa search-on-the-fly using the search engineof Figure
`
`3;
`
`Figures 11 - 15b are additional examples of a search-on-the-fly using the search
`
`engine of Figure 3;
`
`Figures 16 - 20 are flow charts illustrating operations of the search engine ofFigure
`
`3;
`
`Figure 21 illustrates a further function of the search engine of Figure 3 in which
`
`results of more than one search are combined;
`
`Figures 22 - 26 illustrate graphical user interfaces that may be displayed in
`
`conjunction with operation of the system of Figure 1;
`
`Figure 27 is a flowchart illustrating an alternate operation of the query generator;
`
`Figure 28 is a flowchart illustrating an alternate operation of the truncator;
`
`Figures 29 - 36 illustrate user interfaces with search results from a search on thefly and
`
`a merge function;
`
`Figures 37 - 39 illustrate a keyword search result form a search on thefly with the
`
`merge function; and
`
`Figures 40-49 illustrate additional search results.
`
`Detailed Description
`
`Ordinary search engines place constraints on any search. In particular, a partial
`
`ordering ofavailable searchcriteria limits application ofthe search engineonly to certain search.
`
`sequences. The useris given a choice ofsearch sequences,and the order in whichindividual
`
`search steps in the search sequence becomeavailablelimits the direction ofthe search. A user
`
`-5-
`
`Ex. 1004 / Page 6 of 89
`
`Ex. 1004 / Page 6 of 89
`
`
`
`Docket 5607/PTO Filings/Spec wpd.
`
`who desires to take a vacation cruise may use an Internet search engine to find a desired
`vacationpackage. The searchbegins withpresentationofalistofgeneral categories, andthe
`user clicks on “travel,” which producesa list of subcategories. The user then clicks on.
`“cruises” from theresultinglist ofsubcategories, and so on in a cumulative narrowing of
`possibilities until the user finds the desired destination,date, cruiseline, andprice. The order
`in which choices become available amountsto a predefined“searchtree,” and the unspoken
`assumption ofthe search engine designeris that the needs and thoughtprocesses ofany user
`will naturally conform tothis predefined search tree.
`To an extent, predefined constraints arehelpful in that predefined constraints allow a
`search engineto logically and impersonally ordertheuser’s thoughts in such awaythat ifthe
`user has a clear idea ofwhat objectthe user wants, andifthe objectis there to be found,then
`the useris assured offinding the object. Indeed,the usermay wantto knowthat choosing any
`available category in a search sequence will produce an exhaustive and disjunctivelist of
`subcategories fromwhich another choice canbe made. Unfortunately, an unnecessarilyhigh
`cost is too oftenpaid forthisknowledge: The useris unnecessarily locked into a limited set of
`choice sequences, and withoutsufficient prior knowledge ofthe object being sought, this
`limitation can become a hindrance. Specifically, where prescribed search constraints are
`incompatible with the associative relationshipsintheuser’s mind, a conflict can arise between
`the thought processesof the user and the function of the search engine.
`Atonetime, such conflicts were written offto the unavoidable differences between
`computers and the humanmind. However, some “differences” are neither unavoidable nor
`problematic. In the case ofsearch engine design,the solution is simple: upon selecting a
`category or entering akeyword, the user can be given notonly a list ofsubcategories, but the
`option to applypreviously available categories as well. In slightly more technicalterms, the
`open topology ofthe searchtree canbearbitrarily closed by permitting search sequencesto
`loop and converge. Previouslists can be accessed and used as points ofdivergence from
`
`1
`2
`3
`4
`5
`6
`7
`8
`9
`10
`11
`12
`13
`14
`15
`16
`17
`18
`19
`20
`21
`22
`23
`24
`25
`26
`
`-6-
`
`
`
`Ex. 1004 / Page 7 of 89
`
`Ex. 1004 / Page 7 of 89
`
`
`
`i
`
`2
`3
`4
`5
`6
`
`7
`8
`9
`10
`11
`12
`13
`14
`15
`16
`17
`18
`19
`20
`21
`22
`23
`24
`25
`26
`
`27
`
`Docket 5607/PTO Filings/Spec wpd.
`
`which new sub-sequences branchoff, and the attributes corresponding to distinct sub-
`
`sequencescan later be merged.
`A sort-on-the-fly/search-on-the-fly search engine(hereafter, search-on-the-fly search
`engine) providesan intuitive meansfor searching various types ofdatabases, allowing auser
`to accessdata in the database without having to know anything about the databasestructure.
`A userselects a desired search term, and a database manager searchesthe databaseforall
`
`instances ofthe desired term, evenifaspecificfile or table does not contain the instance. For
`example, ifa user wants to search the database using the name ofa specific individualas a
`database entry point, the database managerwill search the database using the desiredname,
`andwill organize the searchresults so thatall entries associated with that nameare displayed.
`The database need not havea specific file (in a flat database) or a table (in a relational
`database) ofnames. The usermay perform further on-the-fly searches to narrow the search
`results, or for otherreasons. The search engine then conducts a further search using this criteria
`and produces a secondsearch result. Further narrowing or broadening ofthe search are
`permitted, with the search engine returning results based on any new criteria.
`Figure 1 isa block diagram of a system 10 that uses the search-on-the-fly search
`engine. In Figure 1, a database 12 is accessed using a hardware/software interface device 100
`to provide data to a user terminal 14, Additional databases 13 and 15 may also be accessed.
`bythe terminal 14 using the device 100. The databases 12, 13 and 15 may use different
`schemas, or may use asame schema. Aswill be described later, the device 100 may include
`the search-on-the-fly search engine. In an altemative embodiment,the search-on-the-fly search
`enginemaybe co-located withthe terminal 14. Inyet another embodiment,the search-on-the-
`fly search engine maybe incorporatedinto the structure ofone or more ofthe databases 12,
`13 and 15. The device 100 mayinterface with any one or more ofthe databases 12, 13 and
`15 using a network connection such as through the Internet, for example. Other
`communications mediums mayalso be usedbetweenthe terminal 14, the device 100 and any
`
`one or more ofthe databases 12, 13 and 15. These mediums mayinclude the public switched
`
`-7-
`
`
`
`Ex. 1004 / Page 8 of 89
`
`Ex. 1004 / Page 8 of 89
`
`
`
`§
`
`
`
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`27
`
`Docket 5607/PTO Filngs/Spec wpd
`
`telephone network (PSTN),cable television delivery networks, Integrated Services Digital
`
`Networks (ISDN), digital subscriber lines (DSL), wireless means, including microwave and
`
`radio communications networks,satellite distribution networks, and any othermedium capable
`
`of carrying digital data.
`
`The system shown in Figure 1 is but one ofmanypossible variations. The search-on-
`
`the-fly search engine could also be incorporated within a single computer, such as a personal
`
`computer, a computer network with a host server and one ormore userstations, an intranet,
`
`and an Internet-based system, as shown in Figure 2. Referring again to Figure 2, the terminal
`
`14 may be any device capable ofdisplaying digital data including handheld devices, cellular
`
`phones, geosynchronouspositioningsatellite (GPS) devices, wrist-worn devices, interactive
`
`phonedevices, household appliances, televisions, television set top boxes, handheld computers,
`
`and other computers.
`
`Figure 3 is a detailed block diagram ofan exemplary search-on-the-fly search engine
`
`125. The search engine 125 includes arequest analyzer 130 that receives search requests 114
`
`from the terminal 14 (not shownin Figure 3) and sends out updated requests 115 to a query
`
`generator 150. A status control 140 receives a status update signal 116 and arequest status
`
`control signal 118 and sends out a request status response 119 to the request analyzer 130.
`
`Thestatus control 140 also keeps track ofsearch cycles,that is, the numberofsearchiterations
`
`performed. The query generator 150 receives the updated requests 115 from the request
`
`analyzer 130 and sends a database access signal 151 to a database driver 170. The query
`
`generator 150 receives results 153 ofa search ofthe database 12 (not shown inFigure 3) from
`
`the database driver 170. The query generator 150 providesa display signal 175 to the terminal
`
`14. The database driver 170 sends a database access signal 171 to the database 12. Finally,
`
`a database qualifier 160 receives information 161 from the database driver 170 and provides
`
`alist 163 ofavailable data fields from the database 12. As will be described later, the list of
`
`available datafields 163 may be displayed to auser at the terminal 14, and may be sorted and
`
`processed using the request analyzer 130 in conjunctionwith the database qualifier 160. The
`
`-8-
`
`Ex. 1004 / Page 9 of 89
`
`Ex. 1004 / Page 9 of 89
`
`
`
`Docket 5607/PTO Filings/Spec wpd
`
`database qualifier 160 also receives search information and other commands131 from the
`
`request analyzer 130.
`The search engine 125 may identify a database schemaby simplyusinga trial and error
`process. Alternatively,the search engine 125 mayuse othertechniques know inthe art. Such
`techniques are described, for example,inU.S. Patent 5,522,066, “Interface for Accessing
`Multiple Records Stored in Different File System Formats,” and U.S. Patent 5,974,407,
`“Method and Apparatus for Implementing a Hierarchical Database Management System
`(HDBMS)Using aRelationalDatabase Management System (RDBMS)adtheImplementing
`Apparatus,” the disclosures of whichis hereby incorporated by reference.
`The search engine 125 provides search-on-the-fly search capabilities and more
`
`conventional search capabilities. In either case, the search engine 125 may perform a
`preliminary database access function to determineifthe user has accessto the database 12.
`The search engine 125 also determinesthe database schemato decideif the schemais
`compatible with the user’s dataprocessing system. Ifthe database schemais not compatible
`with the user’s processing system,the search engine 125 mayattempt to perform necessary
`
`translationsso thatthe userat the terminal 14 may access and view data in the database 12.
`
`Alternatively, the search engine 125 may provide a prompt for the user indicating
`
`incompatibility between the terminal 14 and a selected database.
`The search engine 125 may conducta search using one or more search cycles. A
`
`search cycle includes receipt ofarequest 114, any necessary formatting ofthe request 114,
`
`and any necessary truncation steps. The search cycle ends whenaresultlist 175 isprovided
`
`to the terminal 14. The search engine 125 mayretain a statusofeach past and current search
`
`cycle so that the user can modify the searchat a later time. The user may also use this feature
`ofretaining a status ofpast and current search cycles to combine results ofmultiple searches,
`
`using, for example, a Boolean AND function, a Boolean ORfunction,or other logic function.
`
`The abovelisted functions will be described in more detail later.
`
`1
`
`2
`3
`4
`5
`6
`7
`8
`9
`10
`
`11
`12
`13
`14
`15
`
`16
`
`17
`
`18
`19
`
`20
`
`21
`
`22
`
`23
`24
`
`25
`
`26
`
`-9-
`
`
`
`Ex. 1004 / Page 10 of 89
`
`Ex. 1004 / Page 10 of 89
`
`
`
`1
`
`2
`
`td
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`27
`
`
`
`Docket 5607/PTO Filimes/Spec wpd.
`
`The search-on-the-fly fiinction ofthe search engine 125 begins by determining available
`
`data fields ofthe database 12, The database 12 may have its data organized in one ormore
`
`data fields, tables, or otherstructures, and each such data field may be identified by a data field
`
`descriptor. In manycases, the data field descriptor includes enoughtextfor the userat the
`
`terminal 14 to determine the general contents ofthe datafield. The list ofdata fields may then
`
`be presentedat the terminal14, for example, in a pull downlist. An example ofsucha data
`
`field resultlist is shown in Figure 4, whichis from a federal database showingdatarelated to
`
`managed health
`
`care
`
`organizations.
`
`This
`
`database
`
`is
`
`available
`
`at
`
`http://Atobaccopapers.org/dnid.htm. In Figure4,thefirst data field listed is “PlanType,’ which
`
`is shown in result list 156. Other data field descriptors show the general categories ofdatain
`
`the database.
`
`Using the terminal 14, the user may select one ofthe data field descriptors to be
`
`searched. For example, the user could select “city.” Ifa number ofentries, or records,in the
`
`city data field is short, a furtherresult list ofcomplete city names may be displayed. Ifthe
`
`entries are too numerous to be displayed within a standard screensize, for example, the search
`
`engine 125 may,in an iterative fashion, attempt to reduce,or truncate,the result list until the
`
`result list may be displayed. In the example shown in Figure4, entries in the city data field are
`
`so numerous (the database includes all US.cities that have amanagedhealth care organization)
`
`that the search engine 125 has produceda result list 157 that shows onlya first letterofthe city.
`
`Based on the available database datafields, the user may thenperform a further search-on-the-
`
`fly. In this case, the user may choose cities whosefirst initial is ‘““N.” The search engine 125
`
`then returns a result list 158 ofcities whose namesstart with the letter “N.” Because in this
`
`instancethe result list 158 is short, no further truncation is necessary to produce amanageable
`
`list.
`
`Figure 5 is a more detailed block diagram ofthe request analyzer 130. A protocol
`
`analyzer 133 receives the request 114 and provides an output 135 to aconstraint collator 136.
`
`The protocol analyzer 133 examines the received request 114, determines a formatofthe
`
`-10-
`
`Ex. 1004 /Page 11 of 89
`
`Ex. 1004 / Page 11 of 89
`
`
`
`Docket 5607/PTO Filings/Spec wpd.
`
`request 114, andperforms anynecessary translationsto make therequest formatcompatible
`with the database to be accessed. Ifthe databaseto be accessed by the terminal 14 is part of
`a same computer system as the terminal 14, then the protocol analyzer 133 may not be
`required to perform anytranslationsor to reformat the request 1 14. Ifthe database to be
`accessedis notpart ofthe same computer system as the terminal 14, thentheprotocol analyzer
`133 mayberequired to reformat the request 114. The reformatting may be needed, for
`example, when arequest 114 is transmitted over anetwork, such astheInternet, to a database
`coupled to the network.
`The constraint collator 136 provides the updatedrequest 115 (whichmaybe an initial
`request, or a subsequentrequest) to the query generator 150. The constraint collator 136 is
`responsible for interpretingtherequest 114, The constraint collator 136 performsthis function
`by comparing the request 114 against information stored in the status control 140. In
`particular, the constraint collator 136 sends the requeststatus control signal 118to the status
`control 140 and receives the request status response 119. The constraint collator 13 6 then
`comparesthe requeststatus response 119 to constraint informationprovidedwith the request
`114 to determineifthe constraint status should be updated (e.g., because the request 114
`includes anew constraint). In an embodiment,the constraint collator 136 compares constraint
`information in a current request 114 to constraint informationresidinginthestatus control 140,
`and ifthe currentrequest 114 includes anewconstraint, such as anewnarrowing request (for
`example, whentheuserclicks, touchesorpoints overa field shown inalast searchcycle), then
`the constraint collator 136 adds the updated information and sendsthe updatedrequest11 5
`to the query generator 150. Ifthe constraint status should be updated, the constraint collator
`136 sends the status update 118 to the status control 140. Ifthe request 114 is a refresh
`request, the constraint collator 136 sends areset command131 to the database qualifier 160.
`The updatedrequest1 15 (possiblywith anew constraint) is then sent to the query analyzer 150
`
`for further processing.
`
`1
`2
`3
`4
`5
`6
`7
`8
`9
`10
`il
`12
`13
`14
`15
`16
`17
`18
`19
`20
`21
`22
`23
`24
`25
`
`26
`
`-l1-
`
`
`
`Ex. 1004 / Page 12 of 89
`
`Ex. 1004 / Page 12 of 89
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`27
`
`Docket $607/PTO Filings/Spec wpd
`
`Figure 6 is a block diagram ofthe query generator 150. The overall functions ofthe
`
`query generator 150 are to scan a database,such as the database 12, using the database driver
`
`170, andto collect search results based on constraints supplied by the request analyzer130.
`
`The query generator 150 then returns the search results 175 to the terminal 14.
`
`The query generator 150 includes a truncator 152 and a dispatcher 154. The truncator
`
`152 receives the updated request 115, including a new constraint, ifapplicable. ‘The truncator
`
`152 creates new queries, based on new constraints, and applies the new requests 151 to the
`
`database 12 using the database driver 170. The truncator 152 may include a variable limit 155
`
`that is set, for example, according to acapacity ofthe terminal 14 to display the search results
`
`175, Ifdataretrieved from the database 12 exceed the limit value, the truncator 152 adjusts
`
`asize (e.g., anumber ofentries or records) ofthe data until a displayable result listis achieved.
`
`One method ofadjusting thesize is by cycling (looping). Othermethods mayalso be used to
`
`adjust the size ofthe result list. For example, the terminal 14 may be limited to displaying 20
`
`lines ofdata (entries, records) from the database 12. The truncator 152 will cycle until the
`
`displayedresult list is at most 20 lines. In an embodiment, the truncation process used by the
`
`truncator 152 assumesthat ifthe user requests all values in a particular data field from the
`
`database 12, and there are no other constraints provided with the request 114, and ifthe size
`
`ofthe resultingresultlist is larger than some numeric parameter related to a display size ofthe
`
`terminal14,then the constraints may be modifiedby the truncator 152 so that the result list can
`
`accommodated (e.g., displayed on one page) by the terminal 14. For example, instead ofa
`
`fullname ofacity, some part ofthe name- the first n letters - is checked against the database
`
`12 again, and n is reduced until the result list is small enough for the capacity ofthe terminal 14.
`
`Ifthe maximum numberofdisplayable results is three (3), and the database 12 contains the
`
`namesofsix cities “Armandia, Armonk, New Orleans, New York, Riverhead, Riverdale,” then
`
`the first attempt to “resolve”the result list will stop after a result list display is created with the
`
`full name of the cities:
`
`Armandia, Armonk, New Orleans... (the limit was reached)
`
`-12-
`
`
`
`‘3
`
`Ex. 1004 / Page 13 of 89
`
`Ex. 1004 / Page 13 of 89
`
`
`
`e
`
`
`
`
`
`3
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`27
`
`Docket 5607/PTO Filings/Spec wpd
`
`Try again with 7 characters:
`
`Armandia, Armonk, New Orl, New Yor, (limit reached again)
`
`Again with 5 characters:
`
`Armandia, Armonk, New O, New Y,(limit reached again)
`
`Again with 3 characters:
`
`Arm (...), New (...), Riv(...)}. These results may now be displayed on the terminal 14. The
`
`display of Arm, New, Riv can then be used to conduct a further search-on-the-fly. For
`
`example, auser could then select Riv for a further search-on-the-fly. The result list returned
`
`would then list two cities, namely Riverhead and Riverdale.
`
`In another embodiment, a fixed format is imposed suchthat all queries generated
`
`against a database will have preset limits corresponding to the capacity of the terminal 14.
`
`In yet another embodiment, the truncator 152 may adjustthefield size by division or
`
`other means. For example,ifthe display limit has been reached, the truncator 125 may reduce
`
`the field size, X by a specified amount. In an embodiment, X may be divided by two.
`
`Alternatively, X may be multipliedby anumberless than 1, such as 3/4, for example. Adjusting
`
`the field size allows the search engine 125 to perform more focused searches and provides
`
`more accurate search results.
`
`In still another embodiment, the usermayselect a limit that will cause the truncator 152
`
`to adjust the field size. For example, the user could specify that a maximum often entries
`
`should be displayed.
`For certain data fields, a terminal 14, such as a hand-held device for example, may
`
`have avery limited display capacity. Alternatively a usermayspecify a limit on the number of
`
`entries for display. In these twoillustrated cases, the search engine 125 may return aresultlist
`
`175 ofthe request 114 on multiple display pages, and the user may toggle between these
`
`multiple display pages. As an example,ifthe terminal 14 is limited to displaying amaximum of
`
`ten entries, and ifthe request 114 results in areturn ofa data field comprising the 400largest
`
`cities in the UnitedStates, the truncator 152 will producea list of23 entries comprising 23
`
`-13-
`
`Ex. 1004 / Page 14 of 89
`
`Ex. 1004 / Page 14 of 89
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`
`
`x
`
`Docket 5607/PTO Fihngs/Spec wpd
`
`alphabetical characters (nocities that begin with Q, Y or Z - see Figure 4). The search engine
`
`125 may then display the results on three pages. Alternatively, the trancator 152 could
`
`producea list ofletter groups into which the cities wouldfall, such as A-D, E-~G, H-M, N-R,
`
`and R-X, for example. In another alternative, the search engine 125 may send anotice to the
`
`terminalthat the request 114 cannot be accommodated on the terminal 14 andmay prompt the
`
`user to add an additional constraintto the request 1 14,so that a search result maybe displayed
`
`at the terminal 14.
`
`Adjusting the data field size also provides more convenient search results for the user.
`
`For example, ifa user were to access an Internet-based database for booksforsale, and were
`
`to requesta list ofall booktitles beginning withtheletter “F,”’ a commonsearch engine might
`
`returm several hundredtitles or more, displaying perhaps twenty titles (entries) at a time. The
`
`user would then haveto look through each ofmanypagesto find a desiredtitle. This process
`
`could be very time-consuming and expensive. Furthermore,ifthe searchresults were toolarge,
`
`the commonsearch engine might return a notice saying the results were too large for display
`
`and might promptthe userto select an alternative search request. However, performing the
`
`same search using the search engine 125 allowsthe truncator 152 to reduce the size ofthe
`
`information displayed to amanageable level. In this example, ifthe request 114 includes the
`
`constraint “F,” the truncator 152 will loop through the data in a data field that includes book
`
`titles starting with theletter “F”until a listis available that