`Ex. 1004 / Page 1 of 89
`
`
`
`Docket 5607PIPTO FlltngS/Spcc wpd
`
`SEARCH-ON-THE-FLY WITH MERGE FUNCTION
`
`Related Applications
`
`This application is a continuation—in—part ofApplication Serial Number 09/5 1 3 ,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 technical field is information management systems, interfaces, andmechanisms, and
`
`methods for searching one or more databases.
`
`Background
`
`In the most general sense, a database is a collection ofdata. Various architectures
`
`have been devised to organize data in a computerized database. Typically, acomputerized
`
`l
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`l 1
`
`«’ 12
`
`database includes data stored in mass storage devices, such as tape drives, magnetic hard disk
`
`1 3
`
`1 4
`
`l 5
`
`1 6
`
`1 7
`
`18
`
`19
`
`20
`
`2,1
`
`22
`
`23-
`
`24
`
`25
`
`26
`
`27
`
`28
`
`drives and optical drives. Three main database architectures are termed hierarchical, network
`
`and relational. A hierarchical database assigns different data types to different levels ofthe
`
`hierarchy. Links between data items on one level and data items on a different level are simple
`
`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 corresponds to a table having rows, with each row called a
`
`tuple, and columns, with each column called an attribute. From apractical standpoint, rows
`
`represent records ofrelated data and columns identify individual data elements. The order in
`
`which the rows and columns appear in atable has no significance. In arelational database, one
`
`can add a new column to a table Without having to modify older applications that access other
`
`columns in the table. Relational databases thus provide flexibility 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
`
`
`
`\DOOQO‘xUl-h-UJNr—i
`
`\IQUI-pwwl—‘OKDOOQQUI‘PWNP‘O
`NNNNNNNNt—Iv—‘r—tr—Ir—AHn—ts—LH.‘
`
`Docket $607IP'1'O Filings/Spec wpd
`
`table, there is generally one schema to which it belongs. Once the schema is designed, atool,
`
`known as a database management system (DBMS), is used to build the database and to
`
`operate on data within the database. The DBMS stores, retrieves and modifies data associated
`
`with the database. Lastly, to the extent possible, the DBMS protects data fiom corruption and
`
`unauthorized access.
`
`Ahuman user controls the DBMS by providing a sequence ofcommands selected flour
`
`a data sublanguage. The syntax ofdata sublanguages varies widely. The American National
`
`Standards Institute (ANSI) and the International Organization for Standardization (IS0) have
`
`adopted Structured English Query Language (SQL) as a standard data sublanguage for
`
`relational databases. SQL comprises a data definition language (DDL), a data manipulation
`
`language (DML), and a data control language (DCL). The DDL allows users to define a
`
`database, to modify its structure and to destroy it. The DML provides the tools to enter,
`
`modify and extract data from the database. The DCL provides tools to protect data from
`
`corruption and unauthorized access. Although SQL is standardized, most implementations of
`
`the ANSI standard have subtle differences. Nonetheless, the standardization of SQL has
`
`greatly increased the utility of relational databases for many applications.
`
`Although access to relational databases is facilitated by standard data sublanguages,
`
`users still must have detailed knowledge ofthe schema to obtain needed information from a
`
`database since one can design many different schemas to represent the storage of a given
`
`collection ofinformation. For example, in an electronic commerce system, product information,
`
`such as product SKU, product name, product description, price, and tax code, may be stored
`
`in a single table within a relational database. In another electronic commerce system, product
`
`SKU, product name, description, and tax code maybe stored in one table while product SKU
`
`and product price are stored in a separate table. In this situation, a SQL query designed to
`
`retrieve aproduct price fi'om a database ofthe first electronic commerce system is not useful
`
`for retrieving the price for the same product in the other electronic system’s database because
`
`the differences in schemas require the use ofdifferent SQL queries to retrieve product price.
`
`-2-
`
`
`
`.
`
`.-::q«wn3-;.m:aw
`
`Ex. 1004 / Page 3 of 89
`
`Ex. 1004 / Page 3 of 89
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`1 1
`
`12
`
`13
`
`14
`
`1 5
`
`1 6
`
`17
`
`1 8
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`27
`
`Docket SSW/PTO Filings/Spec wpd
`
`As a consequence, developers of retail applications accessing product information from
`
`relational databases may have to adapt their S QL queries to each individual schema. This, in
`
`turn, prevents their applications frombeingused in environments where there 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 may be significant.
`
`Summary
`
`A Sort-on—the-Fly/Search—on—the—Fly search engine (hereafier, search—on~the- fly
`
`search engine) provides an intuitive means for searching databases, allowing a user to access
`
`data in the database without having to know anything ab out the database structure. A user
`
`selects a desired search term, and a database manager searches the database for all instances
`
`ofthe desired term, even ifa specific file or table does not contain the instance. For example,
`
`ifa user wants to search the database using the name ofa specific individual as a database entry
`
`point, the database manager will search the database using the desired name, and will organize
`
`the search results so that all entries associated with that name are 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 names that include the name “Smith,”
`
`the user may then decide to search for all “Smiths” that include an association to an address in
`
`New Jersey. The search-on—the—fly search engine then conducts a 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 returnng 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 make the search process as efficient as possible. The GUIs
`
`-3-
`
`
`
`
`a.
`
`Ex. 1004 / Page 4 of 89
`
`Ex. 1004 / Page 4 of 89
`
`
`
`Dockc15607/PTO Filing/Spec wpd
`
`may incorporate one or more pull down menus ofavailable search terms. As a user selects an
`
`item from a first pulldown menu, a subsequent pulldown menu displays choices that are
`
`available for searching. The process continues until the search engine has displayed a discrete
`
`data entry from the database. The pulldown menus are not pre-formatted. Instead, the
`
`pulldown menus are created “on—the—fly” as the user steps through the search process. Thus,
`
`the search—on—the—fly search engine is 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 specified by 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, many difi‘erent
`
`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 method that uses
`
`the Internet as a communications backbone.
`
`Description of the Drawings
`
`The detailed description will refer to the following figures, inwhich like numerals refer
`
`to like objects, and in which:
`
`Figure 1 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;
`
`I
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`1 O
`
`11
`
`12
`
`13
`
`14
`
`15
`
`1 6
`
`17
`
`l 8
`
`1 9
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`=
`
`
`
`,3
`
`Ex. 1004 / Page 5 of 89
`
`Ex. 1004 / Page 5 of 89
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`l 0
`
`1 l
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`l 8
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`2 6
`
`27
`
`Docket 5607/PTO Filings/Spec wpd
`
`Figure 3 is a detailed block diagram of the 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 engine of 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 the fly and
`
`a merge function;
`
`Figures 37 — 39 illustrate a keyword search result form a search on the fly 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 search criteria limits application ofthe search engine only to certain search
`
`sequences. The user is given a choice ofsearch sequences, and the order in which individual
`
`search steps in the search sequence become available limits the direction ofthe search. A user
`
`-5-
`
`
`
`Ex. 1004 / Page 6 of 89
`
`Ex. 1004 / Page 6 of 89
`
`
`
`Docket SEW/PTO Filings/Spec wpd
`
`who desires to take a vacation cruise may use an Internet search engine to find a desired
`
`vacation package. The search begins with presentation ofa list ofgeneral categories, and the
`
`user clicks on “travel,” which produces a list of subcategories. The user then clicks on
`
`“cruises” from the resulting list of subcategories, and so on in a cumulative narrowing of
`
`possibilities until the user finds the desired destination, date, cruise line, and price. The order
`
`in which choices become available amounts to a predefined “search tree,” and the unspoken
`
`assumption ofthe search engine designer is that the needs and thought processes ofany user
`
`will naturally conform to this predefined search tree.
`
`To an extent, predefined constraints are helpful in that predefined constraints allow a
`
`search engine to logically and irnpersonally order the user’ 3 thoughts in such a way that ifthe
`
`user has a clear idea ofwhat object the user wants, and ifthe obj ect is there to be found, then
`
`the user is assured offinding the object. Indeed, the usermay want to know that choosing any
`
`available category in a search sequence will produce an exhaustive and disjunctive list of
`
`subcategories from which another choice canbe made. Unfortunately, an unnecessarily high
`
`cost is too ofien paid for this knowledge: The user is unnecessarily locked into a limited set of
`
`choice sequences, and without sufficient prior knowledge ofthe object being sought, this
`
`limitation can become a hindrance. Specifically, where prescribed search constraints are
`
`incompatible with the associative relationships in the user’s mind, a conflict can arise between
`
`the thought processes of the user and the function of the search engine.
`
`At one time, such conflicts were written offto the unavoidable differences between
`
`computers and the human mind. However, some “differences” are neither unavoidable nor
`
`problematic. In the case of search engine design, the solution is simple: upon selecting a
`
`category or entering a keyword, the user can be given not only a list ofsubcategories, but the
`
`option to apply previously available categories as well. In slightly more technical terms, the
`
`open topology ofthe search tree canbe arbitrarily closed by permitting search sequences to
`
`loop and converge. Previous lists can be accessed and used as points of divergence from
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`l 0
`
`l 1
`
`1 2
`
`1 3
`
`14
`
`1 5
`
`16
`
`17
`
`l 8
`
`1 9
`
`20
`
`2 1
`
`22
`
`23
`
`24
`
`25
`
`26
`
`-6-
`
`
`
`Ex. 1004 / Page 7 of 89
`
`Ex. 1004 / Page 7 of 89
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`1 O
`
`1 1
`
`1 2
`
`1 3
`
`14
`
`1 5
`
`16
`
`17
`
`1 8
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`27
`
`Docket 5607/?‘1‘0 {Ming/Spec wpd
`
`which new sub-sequences branch off, and the attributes corresponding to distinct sub—
`
`sequences can later be merged.
`
`A sort—on-the—fly/search—on—the—fly search engine (hereafter, search—on—the—fly search
`
`engine) provides an intuitive means for searching various types ofdatabases, allowing auser
`
`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 manager searches the database for all
`
`instances ofthe desired term, even ifa specific file or table does not contain the instance. For
`
`example, ifa user wants to search the database using the name ofa specific individual as a
`
`database entry point, the database manager will search the database using the desired name,
`
`and will organize the search results so that all entries associated with that name are displayed.
`
`The database need not have a specific file (in a flat database) or a table (in a relational
`
`database) ofnames. The user may perform further on—the-fly searches to narrow the search
`
`results, or for other reasons. The search engine then conducts a fiirther search using this criteria
`
`and produces a second search result. Further narrowing or broadening of the search are
`
`permitted, with the search engine returning results based on any new criteria.
`
`Figure 1 is a 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 auser terminal 14. Additional databases 1 3 and 15 may also be accessed
`
`by the terminal 14 using the device 100. The databases 12, 13 and 15 may use different
`
`schemas, or may use a same schema. As will be described later, the device 100 may include
`
`the search-on—the—fly search engine. In an alternative embodiment, the search—on—the-fly search
`
`engine maybe co—located with the terminal 14. In yet another embodiment, the search-on-the—
`
`fly search engine may be incorporated into the structure ofone or more ofthe databases 12,
`
`1 3 and 1 5. The device 100 may interface with any one or more ofthe databases 12, 1 3 and
`
`15 using a network connection such as through the Internet, for example. Other
`
`communications mediums may also be usedbetween the terminal 14, the device 100 and any
`
`one or more ofthe databases 12, 1 3 and l 5. These mediums may include 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
`
`l 1
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`1 8
`
`19
`
`20
`
`2 1
`
`22
`
`23
`
`24
`
`25
`
`26
`
`27
`
`Docket SSW/PTO Filings/Spec wpd
`
`telephone network (P STN), 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 other medium capable
`
`of carrying digital data.
`
`The system shown in Figure 1 is but one ofmany possible 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 or more user stations, 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, geosynchronous positioning satellite (GPS) devices, wrist-worn devices, interactive
`
`phone devices, household appliances, televisions, television set top boxes, handheld computers,
`
`and other computers.
`
`Figure 3 is a detailed block diagram of an exemplary search-on—the-fly search engine
`
`125. The search engine 125 includes arequest analyzer 130 that receives search requests 1 14
`
`from the terminal 14 (not shown in Figure 3) and sends out updated requests 1 15 to a query
`
`generator 150. A status control 140 receives a status update signal 1 16 and arequest status
`
`control signal 1 18 and sends out a request status response 1 19 to the request analyzer 130.
`
`The status control 140 also keeps track ofsearch cycles, that is, the number of search iterations
`
`performed. The query generator 150 receives the updated requests 115 fiom the request
`
`analyzer 130 and sends a database access signal 151 to a database driver 170. The query
`
`generator 1 50 receives results 1 53 ofa search ofthe database 12 (not shown inFigure 3) from
`
`the database driver 170. The query generator 150 provides a 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 1 60 receives information 161 from the database driver 170 and provides
`
`a list 163 of available data fields from the database 12. As will be described later, the list of
`
`available data fields 163 may be displayed to a user at the terminal 14, and may be sorted and
`
`processed using the request analyzer 1 3 0 in conj unction with the database qualifier 160. The
`
`—8—
`
`:
`
`
`
`Ex. 1004 / Page 9 of 89
`
`Ex. 1004 / Page 9 of 89
`
`
`
`Docket sew/mo Filings/Spec wpd
`
`database qualifier 160 also receives search information and other commands 13 1 from the
`
`request analyzer 130.
`
`The search engine 125 may identify a database schemaby simply using atrial and error
`
`process. Alternatively, the search engine 125 may use other techniques lmow 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 US Patent 5,974,407,
`
`“Method and Apparatus for Implementing a Hierarchical Database Management System
`
`(HDBMS) Using a Relational Database Management System (RDBMS) ad the Implementing
`
`Apparatus,” the disclosures of which is 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 determine ifthe user has access to the database 12.
`
`The search engine 125 also determines the database schema to decide if the schema is
`
`compatible with the user’ 3 data processing system. Ifthe database schema is not compatible
`
`with the user’ s processing system, the search engine 125 may attempt to perform necessary
`
`translations so that the user at 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 conduct a search using one or more search cycles. A
`
`search cycle includes receipt ofarequest 1 14, any necessary formatting ofthe request 1 14,
`
`and any necessary truncation steps. The search cycle ends when aresult list 175 is provided
`
`to the terminal 14. The search engine 125 may retain a status ofeach past and current search
`
`cycle so that the user can modify the search at 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 OR function, or other logic function.
`
`The above listed functions will be described in more detail later.
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`1 1
`
`12
`
`13
`
`1 4
`
`1 5
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`-9-
`
`
`
`Ex. 1004 /Page 10 of 89
`
`Ex. 1004 / Page 10 of 89
`
`
`
`l
`
`2
`
`b:
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`1 3
`
`14
`
`1 5
`
`16
`
`1 7
`
`l 8
`
`1 9
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`27
`
`Dockel 5607/PTO Filings/Spec wpd
`
`The search—on—the—fly function ofthe search engine 125 begins by determining available
`
`data fields ofthe database 12. The database 12 may have its data organized in one or more
`
`data fields, tables, or other structures, and each such data field may be identified by a data field
`
`descriptor. In many cases, the data field descriptor includes enough text for the user at the
`
`terminal 14 to determine the general contents ofthe data field. The list ofdata fields may then
`
`be presented at the terminal 14, for example, in a pull down list. An example ofsuch a data
`
`field result list is shown in Figure 4, which i s from a federal database showing data related to
`
`managed health
`
`care
`
`organizations.
`
`This
`
`database
`
`is
`
`available
`
`at
`
`http ://tobaecopapers.org/dnld.htm. In Figure 4, the first data field listed is “PlanType,” which
`
`is shown in result list 156. Other data field descriptors show the general categories ofdata in
`
`the database.
`
`Using the terminal 14, the user may select one of the data field descriptors to be
`
`searched. For example, the user could select “city.” If a number ofentries, or records, in the
`
`city data field is short, a further result list of complete city names may be displayed. Ifthe
`
`entries are too numerous to be displayed within a standard screen size, 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 Figure 4, entries in the city data field are
`
`so numerous (the database includes all U. S. cities that have amanaged health care organization)
`
`that the search engine 125 has produced a result list 1 57 that shows only a first letter ofthe city.
`
`Based on the available database data fields, the user may then perform a further search-on—the—
`
`fly. In this case, the user may choose cities whose first initial is “N.” The search engine 125
`
`then returns a result list 15 8 ofcities whose names start with the letter “N.” Because in this
`
`instance the result list 15 8 is short, no further truncation is necessary to produce a manageable
`
`list.
`
`Figure 5 is a more detailed block diagram ofthe request analyzer 130. A protocol
`
`analyzer l 3 3 receives the request 1 14 and provides an output 135 to a constraint collator 136.
`
`The protocol analyzer 133 examines the received request 1 14, determines a format of the
`
`-10-
`
`
`
`Ex. 1004 /Page 11 of 89
`
`Ex. 1004 / Page 11 of 89
`
`
`
`Docket SGDWP’TO Filings/Spec w'pd
`
`request 1 14, and performs any necessary translations to make the request format compatible
`
`with the database to be accessed. Ifthe database to 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 any translations or to reformat the request 1 14. Ifthe database to be
`
`accessed is not part ofthe same computer system as the terminal 14, then the protocol analyzer
`
`133 may be required to reformat the request 114. The reformatting may be needed, for
`
`example, when arequest 1 14 is transmitted over anetwork, such as the Internet, to a database
`
`coupled to the network.
`
`The constraint collator 136 provides the updated request 1 15 (which may be an initial
`
`request, or a subsequent request) to the query generator 150. The constraint collator 136 is
`
`responsible for interpreting the request 1 14. The constraint collator 136 performs this function
`
`by comparing the request 1 14 against information stored in the status control 140. In
`
`particular, the constraint collator 136 sends the request status control signal 1 18 to the status
`
`control 140 and receives the request status response 1 19. The constraint collator 13 6 then
`
`compares the request status response 1 19 to constraint informationprovided with the request
`
`1 14 to determine if the constraint status should be updated (e.g., because the request 114
`
`includes a new constraint). In an embodiment, the constraint collator 136 compares constraint
`
`information in a current request 1 14 to constraint information residing in the status control 140,
`
`and ifthe current request 1 14 includes a new constraint, such as a new narrowing request (for
`
`example, when the user clicks, touches or points over a field shown in a last search cycle), then
`
`the constraint collator 13 6 adds the updated information and sends the updated request 1 15
`
`to the query generator 150. Ifthe constraint status should be updated, the constraint collator
`
`13 6 sends the status update 1 18 to the status control 140. If the request 1 14 is a refresh
`
`request, the constraint collator 136 sends areset command 131 to the database qualifier 160.
`
`The updated request 1 1 5 (possibly with a new constraint) is then sent to the query analyzer 150
`
`for further processing.
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`1 1
`
`12
`
`13
`
`14
`
`1 5
`
`16
`
`1 7
`
`1 8
`
`1 9
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`-11-
`
`
`
`Ex. 1004 /Page 12 of 89
`
`Ex. 1004 / Page 12 of 89
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`l l
`
`12
`
`l 3
`
`14
`
`l 5
`
`l 6
`
`1 7
`
`1 8
`
`l 9
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`27
`
`Docket 5607/PTO Filmy/Spec wpd
`
`Figure 6 is a block diagram ofthe query generator 150. The overall fiinctions ofthe
`
`query generator 1 5 0 are to scan a database, such as the database 12, using the database driver
`
`170, and to collect search results based on constraints supplied by the request analyzer l 30.
`
`The query generator 1 5 0 then returns the search results 1 75 to the terminal 14.
`
`The query generator 150 includes a truncator 152 and a dispatcher 154. The truncator
`
`1 52 receives the updated request 1 15, including a new constraint, ifapplicable. The truncator
`
`152 creates new queries, based on new constraints, and applies the new requests 1 5 1 to the
`
`database 12 using the database driver 1 70. The truncator 152 may include a variable limit 155
`
`that is set, for example, according to a capacity ofthe terminal 14 to display the search results
`
`l 75 . Ifdata retrieved from the database 12 exceed the limit value, the truncator 1 52 adjusts
`
`a size (e.g., a number ofentries or records) ofthe data until a displayable result list is achieved.
`
`One method ofadjusting the size is by cycling (looping). Other methods may also 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
`
`displayed result list is at most 20 lines. In an embodiment, the truncation process used by the
`
`truncator l 52 assumes that ifthe user requests all values in aparticular data field from the
`
`database 12, and there are no other constraints provided with the request 1 l4, and ifthe size
`
`ofthe resulting result list is larger than some numeric parameter related to a display size ofthe
`
`terminal 14, then the constraints may be modified by the truncator l 52 so that the result list can
`
`accommodated (e. g., displayed on one page) by the terminal 14. For example, instead ofa
`
`full name ofa city, some part ofthe name - the first 11 letters — is checked against the database
`
`1 2 again, and n is reduced until the result list is small enough for the capacity ofthe terminal 14.
`
`Ifthe maximum number ofdisplayable results is three (3), and the database 12 contains the
`
`names ofsix 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-
`
`
`
`Ex. 1004 /Page 13 of 89
`
`Ex. 1004 / Page 13 of 89
`
`
`
`QWNQMAWNH
`
`NNNNNNMNHHHb—lb—‘r—‘h—lv—‘HH\lO‘iUI-PWNF'OVDOOQO‘iU‘I—bUJNfio
`
`
`
`Docket 5607IPTO Filmgs/Spec ma
`
`Try again with 7 characters:
`
`Arrnandia, Arrnonk, New Orl, New Yor, (limit reached again)
`
`Again with 5 characters:
`
`Armandia, Armonk, New 0, New Y, (limit reached again)
`
`Again with 3 characters:
`
`Arm (, . .), New (. . .), Riv (. . .). These results may nowbe displayed on the terminal 14. The
`
`display of Am, 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 such that all queries generated
`
`against a database will have preset limits corresponding to the capacity of the terminal 14.
`
`In yet another embodiment, the truncator 1 52 may adjust the field 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 specifi ed amount. In an embodiment, X may be divided by two.
`
`Alternatively, X may be multiplied by anumber less 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 user may select a limit that will cause the truncator 152
`
`to adjust the field size. For example, the user could specify that amaximum 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 user may specify a limit on the number of
`
`entries for display. In these two illustrated cases, the search engine 125 may return a result list
`
`175 of the request 1 14 on multiple display pages, and the user may toggle between these
`
`multiple display pages. As an example, ifthe terminal 14 is limited to displaying a maximum of
`
`ten entries, and ifthe request 1 14 results in aretum ofa data field comprising the 400 largest
`
`cities in the United States, the truncator 152 will produce a list of23 entries comprising 23
`
`-13-
`
`Ex. 1004 /Page 14 of 89
`
`Ex. 1004 / Page 14 of 89
`
`
`
`l
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`1 1
`
`12
`
`1 3
`
`14
`
`1 5
`
`1 6
`
`1 7
`
`1 8
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`
`
`g,
`
`Dockcl sew/no Filmy/Spec Wpd
`
`alphabetical characters (no cities that begin with Q, Y or Z - see Figure 4). The search engine
`
`12 5 may then display the results on three pages. Alternatively, the truncator 1 52 could
`
`produce a list ofletter groups into which the cities would fall, such as A—D, E-G, H—M, N—R,
`
`and R—X, for example. In another alternative, the search engine 125 may send a notice to the
`
`terminal that the request 1 14 cannot be accommodated on the terminal 14 and may prompt the
`
`user to add an additional constraint to 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, if a user were to access an Internet—based database for books for sale, and were
`
`to request a list ofall book titles beginning with the letter “F,” a common search engine might
`
`return several hundred titles or more, dis