Patent Description:
A common problem in database technology is to ensure short response times to database queries or requests which require complex, long and resource-intensive processing, e.g. due to large volumes of data. For example, such computing-power consuming processing has to be performed in response to so-called "open queries" which contain only little input information (e.g. only one or two parameters out of a dozen possible parameters are specified and/or the specified value ranges of the parameters are broad) and, consequently, lead to a large number of results in general. Possibilities to speed up data processing by increasing hardware performance are limited. Thus, attention is drawn to improving the mechanisms underlying the complex, long and resource-intensive processing in order to respond to such queries.

One general approach to shorten response times is to prepare results to be returned in response to expected requests (e.g. by pre-computing or pre-collecting such results) and to maintain the corresponding query results in a pool of prepared results. Requests are then actually not processed and responses on the basis of the large original data basis, but are directed to the pool of prepared results.

Another issue, however, which comes along with such result preparing approaches, is to keep the prepared results up-to-date in order to ensure that prepared results returned in response to data requests correctly reflect the outcome of a complex, long and resource-intensive processing. In case the underlying original data basis changes, the prepared results get outdated and answering requests on the basis of the pool of prepared results would deliver incorrect prepared results. Thus, update strategies are employed to keep the pool of prepared results up-to-date.

Various relatively simple update strategies are known in the prior art like, for example, re-computing the entire domain of prepared results frequently, establishing and maintaining re-computation schedules manually and re-computing prepared results when they are getting too old.

Somewhat more sophisticated update strategies have been developed, as e.g. described by <CIT> and <CIT>.

<CIT> concerns an availability system used in a travel planning system. The system includes a cache having entries of availability information regarding airline seats. A cache manager manages entry information in the cache in order to keep information in the cache correct, current, complete or otherwise as useful as possible. In response to a query directed to the cache, the cache manager determines if a stored answer is stale and, if this is the case, sends an availability query to a source of availability information. Cache entries to be modified are obtained by asynchronous notifications from external systems and determined by a deterministic, predictive or statistical model.

Similarly, <CIT> pertains to an information retrieval system wherein information received from information sources is cached for future use, such as for future client requests. Proactive queries can be generated to populate a cache and/or to update presently cached information. In an airline information system, proactive queries are ordered on the basis of statistics or predictive indications such a nearness of departure time, the age of cached data, remaining seats in an aircraft, holidays or special events or equipment type. In addition, updates are received by external notifications from airlines such as AVS messages.

Moreover, <CIT> describes a mechanism for automatically refreshing documents in a cache by using a statistics-based probabilistic model. For each document, the cache determines a probability Psi(t) that a cached object i is stale at a particular time t (i.e. the server has changed that object) and a probability Pri(h) that object i is requested by a user by request time h. The cache refreshes those objects with the highest product Pi = Psi(t) x Pri(h), i.e. the probability that an outdated object is returned to the user with the next request. To maintain these probability values, the cache maintains and tracks historical statistics for the cached objects such as an estimated mean interval between server updates EUI. EUI of an object is e.g. updated when the object itself is updated by the server or the object is not updated after its estimated mean refresh time has elapsed.

<CIT> relates to refreshing a cache based on query responses provided by a searching system in response to queries. A cache entry is provided for each unique query if space is available in the cache. A temperature value is assigned to each cache entry based on a frequency of occurrence of the corresponding query. An age value is assigned to each cache entry based on a time of last refresh or creation of the corresponding query response. The age of the cache entries is periodically updated and the temperature of a cache entry is updated when a corresponding query occurs. If system resources are available, the query response of a cache entry is refreshed based on the temperature and age of the cache entry. Refreshing is limited if resources are unavailable.

The article "<NPL>et al. studies possibilities to refresh a local copy of an autonomous data source to maintain the copy up-to-date. Inter alia, the Poisson process is described as an approach to model the probabilistic evolution of an element.

Moreover, <CIT> provides a method and system for automatically refreshing documents in a cache. For each document, the cache estimates a probability distribution of times for client requests for that document and a probability distribution of times for server changes to that document. The cache estimates a probability distribution of times for client requests for that document, and determines a cumulative probability distribution which reflects the estimated marginal hit rate at the storage limit of the cache and the marginal advantage of adding storage to the cache.

The documentation "<NPL>et al. describes how to use Oracle Web Cache to cache both static and dynamically generated content from one or more application Web servers.

According to one aspect, a method for handling data requests directed to a database environment is provided. The database environment has a least one first platform providing original results to be stored in a second platform as prepared results. The second platform maintains a pool of the prepared results having been prepared via the first platform in order to be returned to data requests. The database environment further has a control unit for processing the data requests directed to the database environment. Each prepared result maintained in the pool of the second platform is associated with an update indicator being a measure that the associated prepared result kept in the pool of the second platform is to be updated. The control unit receives a data request. The control unit determines at least one prepared result corresponding to the data request. The control units compares the update indicator of the determined prepared result corresponding to the data request with a threshold value. If the comparison indicates a requirement to update the prepared result, the control unit retrieves an updated version of the at least one prepared result from the first platform. The control unit updates the prepared result in the pool of the second platform and the associated update indicator based on the updated version of the at least one prepared result by storing a new timestamp of the update of the at least one prepared result. The control unit returns the updated version of the at least one result. On the other hand, if the comparison does not indicate a requirement to update the at least one prepared result, the control unit returns the at least one determined prepared result. The update indicator is defined by (<NUM> - acc) • t, wherein acc is a probability that the associated prepared result is valid and t is an age of the associated prepared result, wherein acc = e-λt, wherein the validity rate λ is an indicator of how frequently the prepared result changes.

In this way, the accuracy of the prepared results (i.e. the prepared results are still in line with the original response data) is enhanced in the long term, as will be explained in detail below.

According to a second aspect, a control unit being arranged accordingly is provided.

According to a third aspect, a computer program to be executed by a control unit and enabling the control unit with respective functionality is provided.

Further aspects are defined by the dependent claims.

The subsequent description of embodiments is based on the accompanying set of figures in which similar reference numerals refer to similar elements and messages and in which:.

Before turning to the description of the embodiments on the basis of <FIG>, a few more general aspects are elaborated first with reference to <FIG>.

As already outlined at the outset, the methodologies described herein relate to database systems which offer prepared results to clients requesting data from a database system. The technical aim of preparing results before they are requested from clients is generally to decrease response times for responding to such data requests. Hereinafter, the term "prepared" is used to relate any sort of pre-processing, pre-computation and pre-collection of results in an asynchronous manner, i.e. independently from and prior to a data request from a client. Examples for a preparation of results are Internet crawlers collecting or copying the content of Internet web servers as well as results generated in response to earlier data requests that are maintained in a cache for fast retrieval, but also complex and time-intensive computations of search results on the basis of underlying data as it is e.g. described for priced travel recommendations by <CIT> and <CIT>. The term "database" is meant to encompass any types of structured information storage system such as standard stand-alone databases like SQL server or Oracle databases as well as complex, distributed and/or proprietary storage systems, relational databases including database management systems or object-oriented database systems and the like. The term "data request" is used herein as a general term for any types of inquiries to a database system in order to retrieve data including any type of information retrieval requests such as transactional queries, requests for batch computations, SQL queries and other forms.

<FIG> illustrates such a database environment <NUM> at an abstract level. Original data, hereinafter also referred to as original results, are provided by a first platform <NUM>. In general, the first platform <NUM> is either an original data source itself, such as an inventory database or a database maintaining any kind of original and generally valid results, or accesses one or more original data sources in order to prepare original results. Examples of the latter kind are a search engine accessing Internet websites and a computation platform computing priced travel recommendations based on fares stored in a fare database. If the first platform <NUM> generates/computes/collects the original results by accessing other/further original data sources in order to prepare original results, the first platform <NUM> provides results which generally accurately reflect the current content of the original response data. More than one first platform <NUM> can be present in the database environment <NUM>.

The database environment <NUM> further includes a second platform <NUM> which maintains a pool <NUM> of results which have been prepared via the first platform <NUM>. The second platform <NUM> is e.g. a cache which caches results having been retrieved via the first platform <NUM>, or the second platform <NUM> is e.g. a server holding a repository of the content of crawled websites, or the second platform <NUM> is e.g. a search platform maintaining pre-computed priced travel recommendations, as described by <CIT>.

In general, the first platform <NUM> providing original response data and the second platform <NUM> maintaining the pool <NUM> of prepared results differ from each other in technical terms as follows: The second platform <NUM>, due to the preparation of the results, provides a cheaper (in terms of computation costs) and/or faster access to the results compared to the first platform <NUM>. This relation between the first platform <NUM> and the second platform <NUM> can also be expressed the other way around, i.e. the first platform <NUM> generally responds more slowly and responses from the first platform <NUM> involve higher computation costs than responses from the second platform <NUM> because the first platform <NUM> still has to prepare the results (e.g. retrieve the requested content from the original Internet website, or compute the requested priced travel recommendations on the basis of fares kept in a fare database). As the computation resources of the first platform <NUM> are limited, the number of accesses to the first platform <NUM> should be kept within a certain limit. For example, CPU consumption or memory load of the first platform <NUM> must not exceed a given limit. This constraint may be translated into a limit of the number of accesses to the first platform per time unit (e.g. <NUM> accesses per second). For these reasons, the first platform <NUM> is not solicited each time in order to respond to data requests. Rather, responses are generally formed by utilizing the prepared results stored in the pool <NUM> of the second platform <NUM>. In this way, the second platform <NUM> acts as a shield in front of the first platform <NUM>, thereby reducing the load on the (computationally expensive) first platform <NUM>.

On the other hand, however, the prepared results stored in the pool of the second platform <NUM> are not necessarily perfectly synchronized with the original results provided by the first platform <NUM>. In general, the prepared results of the second platform <NUM> represent older versions of original result being provided by the first platform <NUM> and the respective version of the original result provided by the first platform <NUM> might have changed since the last update of the corresponding prepared result maintained in the second platform <NUM>. Furthermore, the second platform <NUM> does not necessarily store prepared results corresponding to all existing original results, i.e. prepared results might be missing in the second platform <NUM>. Prepared results stored in the pool <NUM> of the second platform <NUM> which correctly reflect their corresponding result provided by the first platform are hereinafter referred to as valid prepared results or as accurate prepared results, while outdated prepared results stored in the pool <NUM> of the second platform <NUM> are referred to as invalid prepared results or inaccurate prepared results.

Thus, the technical problem arises to maximize the accuracy and validity of the prepared results stored in the pool <NUM> of the second platform <NUM> and the accuracy and validity of prepared results returned to inquiring clients, respectively, i.e. to maintain prepared results in the second platform <NUM> that are consistent with the original response data provided by the first platform <NUM> as much as possible, in order to respond to data request with a high portion of valid prepared results.

The database environment <NUM> is further coupled to at least one, but generally a plurality of clients <NUM>. Clients <NUM> such as applications on user terminals retrieve results from the database environment <NUM> by directing data requests to the database environment <NUM> via an interface <NUM>. The technical characteristics of the interface <NUM> depend on the particular implementation of the database environment <NUM>. For example, the interface <NUM> encompasses wireless communication including <NUM>/<NUM>/<NUM> (including packet-oriented mobile data exchange as well as SMS) and/or WiFi communication in the case the client <NUM> is situated on a mobile communications device. Alternatively or in addition, the interface <NUM> features wired communication using standard network protocols employed in local area networks and/or wide area networks including the Internet such Ethernet, TCP/IP, SMTP with POP3 or IMAP, HTTP, webservice-related protocols such as SOAP, etc..

A data request transmitted from a client <NUM> via interface <NUM> includes one or more retrieval criteria constraining the request. For example, if the data request is an Internet search request, the data request might carry a search string, search text or search phrase as search criteria. A further search criterion may be the language of websites to be searched or an indication of a point of time of the first availability of the requested search string, search text or search phrase. According to another example, the data request is a database request for a product or service offered by a service provider platform such as an Internet book store or a travel provider. In that case, the data request might include e.g. an upper price limit or a price range for the service or product and desired characteristics of the product/service such as book title, travel origin and destination, etc..

Data requests issued by a client <NUM> are received by a further entity of the database environment <NUM>, the control unit <NUM> (<FIG>). In general, the control unit <NUM> processes incoming data requests in order to device whether response results are retrieved from the second platform <NUM> and/or the first platform <NUM>. To this end, the control unit functions as an intermediate unit controlling the data flow within the database environment <NUM> and the results to be returned to the client <NUM>.

Basically, controlling the data flow by the control unit <NUM> takes into account the two following aspects: On the one hand, as already explained above, retrieving prepared results fulfilling the request criteria included in a data request from the pool <NUM> of the second platform <NUM> has the advantage of a faster response time (compared to generating the results by the first platform <NUM>) and relieves the first platform <NUM> from potential overloads. On the other hand, however, serving a data request by retrieving original results provided by the first platform <NUM> allows to update the respective prepared results maintained in the pool <NUM> of the second platform <NUM>. Thus, a portion of results to be returned in response a data requests can be intentionally retrieved from the first platform <NUM>, although corresponding prepared results are available in the second platform <NUM>. These results are thus newly prepared by the first platform <NUM> and returned to the requesting client <NUM> and stored in the pool <NUM> of the second platform <NUM> thereby updating the corresponding prepared results.

The technical problem is then to decide which portions of the data requests being transmitted from the clients <NUM> to the control unit <NUM> are to be responded on the basis of the pool <NUM> of the second platform <NUM> and which portions of the data requests are to be responded on the basis of the first platform <NUM> in order to update the prepared results maintained in the pool <NUM> of the second platform <NUM>.

To this end, the control unit <NUM> utilizes an update indicator which is associated with each prepared result maintained in the pool <NUM> of the second platform <NUM>. In general, the update indicator is a measure whether or not the associated prepared result kept in the pool <NUM> of the second platform <NUM> needs to be updated. The update indicator is defined by (<NUM> - acc) · t (cf. <FIG>), wherein acc is a probability that the associated prepared result is valid and t is an age of the associated prepared result. Before turning to the message sequences involved in the processing of and responding to a data request, the nature of the update indicator is elaborated in more detail first.

A given prepared result i kept in the pool <NUM> of the second platform <NUM> can be specified by the following parameters:.

With these parameters, the validity probability of the prepared results stored in the pool <NUM> of the second platform <NUM> can be defined as follows:
The validity probability of all prepared results kept in the pool <NUM> of the second platform <NUM> can be considered as the mean validity, also referred to as "global accuracy", which is defined by <MAT> with N being the number of prepared results stored in the pool <NUM> of the second platform <NUM>.

Now introducing the above-mentioned exemplary probabilistic model based on the validity rate λi, the global accuracy is given by: <MAT>.

The validity probability of the prepared results in the pool <NUM> of the second platform <NUM> from the perspective of the clients <NUM> (also referred to as "user accuracy") is then defined in that each validity probability value is weighted by the popularity of the respective prepared result. Thus, the proportion of probably accurate client accesses to the prepared results as opposed to the expected proportion of accurate prepared results is: <MAT> wherein ptot is defined as the sum of all pi.

The update indicator utilized by the control unit <NUM> to decide whether to return prepared results maintained in the pool <NUM> of the second platform <NUM> or whether to retrieve updated prepared results from the first platform <NUM> in order to both, return the updated results to the requesting client <NUM> as well as update the respective prepared results in the pool <NUM> of the second platform <NUM> thereby increasing the validity of the prepared results in the second platform <NUM> is formed by these parameters assigned to each of the prepared results in the second platform <NUM>. In the most basic form, the update indicator described herein is given by (<NUM> - acc) · t, for a particular prepared result i by (<NUM> - acci) · ti. On some embodiments, refined definitions based on this basic form are utilized, such as <MAT>, or <MAT>. These variations of the update indicators and their technical significance are explained in more detail further below.

Irrespective which of the aforementioned definitions of the update indicator is utilized, the control unit <NUM> employs the update indicator as follows (see <FIG> and <FIG>).

The control unit <NUM> receives a data request <NUM> from a client <NUM>. Then, the control unit <NUM> determines at least one prepared result corresponding to the data request <NUM> (activity <NUM>). Thus, the control unit <NUM> processes the data request <NUM>, determines the data retrieval criteria included in the data request <NUM> (examples have already been given above) and identifies a number of prepared results which fulfill the data retrieval criteria. The specific manner how these prepared results fulfilling the data retrieval criteria are identified by the control unit <NUM> depends on the architecture of the database environment <NUM> (a particular example is given further below with reference to <FIG> and <FIG>). For example, in the case of the data request <NUM> being an SQL query, the control unit <NUM> determines the query parameters indicated the SQL query and retrieves identification information identifying prepared results (e.g. primary key values) fulfilling the query parameters of the SQL query from the second platform <NUM> or another module existing within the database environment <NUM> for that purpose.

This determination of prepared results fulfilling data retrieval criteria of the data request <NUM> does not necessarily include a retrieval of the content of the prepared results, yet. Rather, it is sufficient to identify these prepared results e.g. on unique identifiers such as their primary key values. In some embodiments, however, activity <NUM> already encompasses retrieval of the content of the prepared results fulfilling data retrieval criteria of the data request <NUM> from the second platform <NUM>.

Further on, the control unit <NUM> compares the update indicators of the determined prepared results with a threshold value (activity <NUM> in <FIG> and <FIG>). At a more detailed level, this activity <NUM> involves a determination of the update indicator values of each of the determined prepared result. To this end, the control unit <NUM> e.g. retrieves respective control data such as the timestamps of the last update of the determined prepared results e.g. from a control database, calculates the ages t of the determined prepared results, retrieves the validity rates being associated with the determined prepared results, calculates the validity probability acc of the determined prepared results and then computes (<NUM> - acc) · t for each of the determined prepared results. The computed values for the update indicator of the determined results are then compared to the threshold value. The threshold value controls the amount of prepared results which are updated via the first platform <NUM> in response to receiving data requests <NUM> and the complimentary amount of prepared results which are not updated in response to receiving data requests <NUM>, but returned to the client <NUM> from the pool <NUM> of the second platform <NUM>.

The comparison either indicates a need to update the respective prepared result if the update indicator value exceeds the threshold or the comparison indicates that the respective prepared result does not need to be updated if the update indicator value does not exceed the threshold (for reasons of simplicity, we here assume that the comparison yields the same indications for all of the determined prepared results - in practice, the comparison may also indicate that a portion of the determined prepared results should be updated and the remaining portion of the determined prepared results do not need to be updated; this situation is explained further below with reference to <FIG> and <FIG> and is also applicable to any other examples described herein).

In the case the comparison indicates a requirement to update the prepared results (box <NUM> in <FIG>), the control unit <NUM> retrieves updated versions of the determined prepared results from the first platform <NUM> (e.g. by relaying the data request to the first platform <NUM>) (message <NUM> in <FIG>). The first platform <NUM> prepares the updated versions of the prepared results and returns these updated versions of the prepared results to the control unit <NUM>. The control unit <NUM> receives the updated versions of the prepared results from the first platform <NUM> by message <NUM>. The control unit <NUM> then updates the determined prepared search result in the pool <NUM> of the second platform <NUM> (activity <NUM> in <FIG>). In addition, the control unit <NUM> also updates the update indicator values associated with the determined prepared results (also activity <NUM> in <FIG>) by storing the new timestamp of this update of the determined prepared results. Finally, the control unit <NUM> returns the updated version of the determined prepared results to the client <NUM> by message <NUM>. Note that activities <NUM> and <NUM> may also occur in a different order, i.e. the control unit <NUM> first returns the prepared results to the client <NUM> and then updates the prepared results in the second platform and the associated update indicators.

On the other hand, in the case the comparison <NUM> does not indicate a requirement to update the determined prepared results (box <NUM> in <FIG>), the control unit <NUM> returns the determined prepared results to the client <NUM> by message <NUM>, without updating the prepared results by inquiring the first platform <NUM>.

The above basic definition of the update indicator as being given by (<NUM> - acc) · t encompasses the technical effect of providing an improved validity of the prepared results in the long run, as will be explained next.

The present inventors have recognized that repeatedly updating such prepared results having a higher validity rate λi which are regularly outdated by a change of their corresponding underlying original response data or updating such prepared results that yield promote the user accuracy as defined above is non-optimal. Such a strategy is, for example, described by <CIT> by proposing to update those objects in a cache with the highest product Pi = Psi(t) x Pri(h), as explained above at the outset. Also focusing on updating prepared results with the best gain-cost ratio being e.g. defined as <MAT> is likewise non-optimal. The present inventors have realized that these strategies only yield short-term increases of the prepared results' accuracy, but might cause an accuracy degradation of the pool <NUM> in the long run.

On the other hand, the update indicator as proposed herein provides a long-term accuracy increase of the prepared results stored in the second platform <NUM> by establishing a decision metric to either respond to a data request either with prepared results updated by the first platform <NUM> (which at the same time update the corresponding prepared results in the second platform <NUM>) or to respond to a data request either with non-updated prepared results being held in the second platform <NUM> without inquiring the first platform <NUM> and updating these prepared results in the second platform <NUM>. The long-term accuracy increase effect of the update indicator proposed herein will become apparent to the skilled person from the following explanations.

As explained above, previously known update strategies focus on updating prepared results which are likely to be invalid, i.e. employ an update indicator of (<NUM> - acci), or refined versions of this such as <MAT>. Further, as also explained above, the computation costs to update a prepared result i by the first platform is denoted as ci. These costs c; are incurred with each update of the prepared result i by the first platform <NUM>. Thus, if e.g. the prepared result i is updated twice as often as another prepared result over a longer period of time, the accumulated amount of ci over this longer period of time is twice as high as the accumulated costs for updating the other prepared result during the same period of time. Therefore, the long-term update costs of a prepared result i can be defined by considering the long-term update frequency fi of the prepared result i (e.g. f; = <NUM> updates of i within <MAT> or f; = <NUM> updates of i within <MAT>) <MAT>.

Considering these long-term update costs leads to the insight that prepared results should be updated in a way providing the highest accuracy gain at the lowest long-term update costs, i.e. with the highest <MAT>. The actual long-term update frequency fi is generally unknown, but can be approximated by the following consideration: If, in response to a data request <NUM>, it is decided to update a given prepared result i which has not been refreshed for a time period of ti, the long-term update frequency of this prepared result i is assumed to be <MAT>. This will actually become true if the decision to update the prepared result i is indeed by taken. In other words, <MAT> is considered as a potential long-term update frequency of the prepared result i. For this reason, the ratio <MAT> can be used as an estimation of the long-term update costs of a given prepared result i. In general, a long-term accuracy optimization of the prepared result stored in the pool <NUM> of the second platform <NUM> should therefore update the prepared results with the highest <MAT>.

This definition of the update indicator can still be generalized when assuming that the update cost ci is equal and constant for all prepared results and the update costs constraint is e.g. only employed to limit the number of updates of prepared results per unit of time via the first platform <NUM>. In this case, the factor c; can be removed from the update indicator resulting in the definition of the update indicator as introduced above, i.e..

As also briefly indicated above, further refinements of this update indicator are possible, e.g. when additionally considering the popularity of prepared results, i.e. the user accuracy (for illustrative purposes): <MAT> or <MAT>.

Furthermore, acc; may be replaced by the specifically employed probabilistic model modeling the validity of prepared results decreasing over time, such as acci = e-λiti as deduced further above. This results in more specific version of the update indicator definitions, namely <MAT> or (for illustrative purposes) <MAT> or (for illustrative purposes) <MAT> or (for illustrative purposes) <MAT>.

<FIG> present a more specific example of a database environment <NUM>. This example differs from the more general architecture shown by <FIG> in that it includes certain additional components, namely the control data store <NUM> and the predictive model manager <NUM>. The control data store <NUM> is connected to the control unit <NUM> via interface <NUM> and to the predictive model manager via interface <NUM>. The predictive model manager is connected to the first platform <NUM> via interface <NUM>, to the control unit <NUM> via interface <NUM> and to the control data store via interface <NUM>.

The control data store <NUM> stores data to compute the update indicator for given prepared results stored in the pool <NUM> of the second platform <NUM>. In particular, the control data store <NUM> stores timestamps indicating the last update time of the prepared results in order to compute the age ti at a given point of time. Optionally, the control data store <NUM> stores data to model the probability for prepared results maintained in the pool <NUM> of the second platform <NUM> to be accurate, for example the validity rates λi of the prepared results in order to compute acci = e-λiti at a given point of time. Optionally, the control data store <NUM> further stores additional control data utilized to determine the values of the various examples of the update indicator as described above, e.g. the request rate (popularity) pi of the prepared results stored in the pool <NUM> of the second platform <NUM> and/or the computation costs c; to update prepared results. The control data kept by the control data store <NUM> is associated with the prepared results stored maintained in the pool <NUM> of the second platform <NUM>. Thus, the control data stored <NUM> also stores identification information of the prepared results in order to associate the control data with the prepared results. For example, a database record of the control data store <NUM> is defined as follows:.

The identification of the prepared results utilized in the control data store <NUM> is, for example, the primary key values of the prepared results as stored in the pool <NUM> of the second platform <NUM>.

In some embodiments, the control data store <NUM> is an integrated part of the control unit <NUM>. In other embodiments, the control data store <NUM> is an integrated part of the second platform <NUM>. In this case, the control data maintained by the control data store <NUM> is e.g. stored in a database table being associated with the database table(s) of the prepared results in the pool <NUM>. In still other embodiments, the control data store is a stand-alone component (e.g. realized by a dedicated server system).

The predictive model manager <NUM> is arranged to update certain control data stored by the control data store, such as the validity rates λi, the popularity pi, and the update costs ci. In order to determine current values for these parameters, the predictive model manager <NUM> receives input data from the first platform <NUM> and from the control unit <NUM>. More specifically, the first platform <NUM> transmits information about the updated prepared results (the updates occurring in response to messages <NUM> (<FIG>)) to the predictive model manager <NUM>, i.e. which results have been updated at which time and whether or not the updates led to a different content of the updated results. The first platform <NUM> also transmits information regarding the computation costs to update prepared results to the model manager <NUM> (these information are determined by the first platform itself by monitoring the updates of the various prepared results and the update costs involved and/or from log information received from an original source of the prepared results such as webservers). The control unit <NUM> transmits information about incoming data requests <NUM> and the prepared results requested by the data requests <NUM> to the predictive model manager <NUM>, e.g. which prepared results were returned to inquiring clients at which times. In some embodiments, this input communication from the first platform <NUM> and/or from the control unit <NUM> to the predictive model manager <NUM> occurs asynchronously from processing and serving data requests <NUM> as visualized by <FIG>, <FIG>, <FIG>, <FIG>, <FIG> and <FIG>. In other embodiments, the first platform <NUM> transmits the information about an updated prepared result to the predictive model manager <NUM> synchronously with the update, e.g. immediately after the first platform <NUM> has returned the updated result to the control unit <NUM>. In such embodiments, also the control unit <NUM> may transmit the information about incoming data requests <NUM> and respective returned results to clients <NUM> to the predictive model manager <NUM> synchronously with the processing of the data requests <NUM>, e.g. immediately after the control unit <NUM> has returned the corresponding results to the inquiring client <NUM>.

The predictive model manager <NUM> processes these inputs from the first platform <NUM> and the control unit <NUM> and provides current control information resulting from the processing to the control data store <NUM>. More specifically, the predictive model manager <NUM> utilizes the information about the updated prepared results received from the first platform <NUM>, encompassing at least the information whether or not an update of a prepared result by the first platform led to a change of the content of the prepared result and a timestamp of the update, to maintain validity rates λi for each of the prepared results stored in the pool <NUM> of the second platform <NUM>. The predictive model manager <NUM> utilizes the information about the computational costs received from the first platform <NUM> to maintain the parameters ci for each prepared result i stored in the pool <NUM> of the second platform <NUM>. The predictive model manager <NUM> utilizes the information about the incoming data requests <NUM> received from the control unit <NUM> and correspondingly requested prepared results in order to maintain the popularity values pi for each of the prepared results stored in the pool <NUM> of the second platform <NUM>. The resulting current values of λi, pi and/or ci are transmitted from the predictive model manager to the control data store <NUM> and are thus made available to the control unit <NUM> in order to determine the update indicator values in the course of processing incoming data requests <NUM> (activity <NUM>). Updates of the current values of λi, pi and/or ci are sent by the predictive model manager <NUM> to the control data store in regular intervals and/or on demand, i.e. when values of control data have been changed.

In some embodiments, the predictive model manager <NUM> and/or the control data store <NUM> employ a distributed batch framework utilizing e.g. Apache Hadoop® enabling both components to execute intensive computing processes with large amounts of data (e.g. in the order of PetaBytes) on server clusters.

Exemplary message sequences occurring in the exemplary architecture of <FIG> are shown by <FIG> and <FIG>. Similar to <FIG> and <FIG>, <FIG> shows the variant in which the update indicator values of the prepared results to be returned to the client <NUM> indicate a need to update the prepared results and <FIG> shows the variant in which the update indicator values of the prepared results to be returned to the client <NUM> do not indicate a need to update the prepared results.

In both variants, the process begins with a transmission of a data request <NUM> from the client <NUM> to the control unit <NUM>. In response to receiving the data request <NUM>, the control unit <NUM> determines identification information (e.g. primary key values) of prepared results which fulfill criteria included in the data request <NUM> and associated update indicator values (activity 31A). As a simple example, the data request <NUM> requests the number of available seats in the flight LH123 on <NUM>st July <NUM>. In response to receiving this data request <NUM>, the control unit <NUM> utilizes the key "LH123-1JUL15" already included in the request to retrieve the last update time of the prepared result LH123-1JUL15-<NUM> (i.e. the prepared result indicates <NUM> free seats, wherein the number <NUM> of available seats is not known to the control unit <NUM> at that stage) and the validity rate λLH123-1JUL15 from the control data store <NUM>. The control data store <NUM> responds with respective values of the update timestamp and validity rate λLH123-1JUL15 (activity 31B in <FIG> and <FIG>). The control unit <NUM> then calculates the update indicator of the prepared result LH123-1JUL15-<NUM> (activity 31C in <FIG> and <FIG>) by calculating the age tLH123-1JUL15 (last update timestamp of LH123-1JUL15-<NUM> minus current time) and then calculating (<NUM> - e-λiti) ti.

The control unit <NUM> then performs the comparison of the calculated update indicator value with the threshold value (activity <NUM> in <FIG> and <FIG>). If the comparison indicates a need to update the LH123-1JUL15-<NUM> (box <NUM> in <FIG>), the control unit <NUM> retrieves an updated version of the prepared result from the first platform <NUM> (activity <NUM> in <FIG>). In an embodiment, the first platform itself is an original inventory of available flight seats and returns the update value (e.g. LH123-1JUL15-<NUM>, i.e. <NUM> free seats) to the control unit <NUM> on the basis of its own inventory data. In another embodiment, the first platform <NUM> retrieves the requested current available seat information from further sources and returns the updated prepared result LH123-1JUL15-<NUM> to the control unit <NUM> afterwards (activity <NUM> in <FIG>). The control unit <NUM>, after having received the updated prepared result from the first platform <NUM>, returns the updated prepared result to the client <NUM> (activity <NUM> in <FIG>), updates the prepared result in the pool <NUM> of the second platform <NUM> (e.g. by replacing the previous outdated value <NUM> with the updated, current value <NUM>, activity 36A) and also updates the last update timestamp of LH123-1JUL15 in the control data store <NUM> (activity 36B). Note that activities 36A, 36B and <NUM> may occur in any order.

Alternatively, the comparison between the current update indicator value of LH <NUM>-<NUM> JUL <NUM> and the threshold conducted by control unit <NUM> (activity <NUM>) indicates that an update of LH123-1JUL15 is not necessary (box <NUM> in <FIG>). In this case, the control unit <NUM> retrieves the value of LH123-1JUL15 (e.g. <NUM> available seats) from the pool <NUM> of the second platform <NUM> (activity 40A in <FIG>) and returns this value as a response to data request <NUM> to the client <NUM> (activity activity <NUM>).

In other embodiments, depending on the content and definition of the prepared results and criteria included in the data request <NUM>, activity <NUM> is more complex (<FIG> and <FIG>) e.g. because the key values of the prepared results in which the client <NUM> is interested are not included in the data request <NUM> and, thus, a search may be required to determine which prepared results fulfill the search criteria included in the data request <NUM>. For example, the prepared results stored by the pool <NUM> specify pre-computed priced travel recommendations and the data request <NUM> e.g. asks for the cheapest travels between Frankfurt and Boston with a departure between <NUM>st July <NUM> and <NUM>th July <NUM> and a stay duration between <NUM> and <NUM> days. In scenarios of this type, in some embodiments, the control unit <NUM> first identifies prepared results stored in the pool <NUM> of the second platform <NUM> which fulfill search criteria of the data request <NUM>. Thus, in these embodiments, activity 31A (<FIG>) is an inquiry of the control unit <NUM> to the second platform <NUM> in order to retrieve identification information of prepared results complying with the search criteria included in the data request <NUM>. Referring to the latest example, the second platform <NUM> e.g. returns all travel recommendations stored in the pool <NUM> for travels between Frankfurt and Boston with a departure between <NUM>st July <NUM> and <NUM>th July <NUM> and a stay duration between <NUM> and <NUM> days (activity 31B in <FIG>).

The control unit <NUM> then determines the update indicator values for all identified prepared results in the manner described above (retrieving the respective control data from the control data store <NUM> by activities 31C and 31D in <FIG> and calculating the update indicator values by activity 31E in <FIG>) and performs the comparison between update indicator value and threshold for each identified prepared result (activity <NUM> in <FIG>). For all prepared results for which the comparison indicates a need to update the respective prepared result (box <NUM> in <FIG>), the control unit <NUM> retrieves an updated version of the respective prepared result from the first platform <NUM> (activities <NUM> and <NUM> in <FIG>). Optionally, as regards the remaining prepared results for which the comparison between update indicator and threshold value does not indicate a need to update, the control unit <NUM> retrieves the content of these not-to-be-updated prepared results from the second platform <NUM> (activities 40A and 40B in <FIG>; this applies if the control unit <NUM> has not already retrieved the content of all the prepared results fulfilling the search criteria with activities 31A and 31B beforehand). After having received the updated versions of the prepared results in response to request <NUM> (activity <NUM>), the control unit <NUM> stores the updated prepared results in the pool <NUM> of the second platform <NUM> (activity 36A in <FIG>), updates the update timestamps of the updated prepared results in the control data store <NUM> (activities 36B in FIG. B), optionally post-processes the prepared results retrieved from the second platform <NUM> and the updated versions of the prepared results retrieved from the first platform <NUM> (activity <NUM> in <FIG>), which is e.g. a determination of a subset of prepared results out of the updated prepared results and the not-updated prepared results determined before to be returned to the client <NUM> (in the above example, selecting the most inexpensive travel recommendation), and returns these results to the client <NUM> (activity <NUM> in <FIG>).

In some embodiments, still different message flows are employed, depending on the particular characteristics of the database model(s) employed by the database environment <NUM> and structure and criteria included in the data requests <NUM>. For example, in some embodiments, post-processing of prepared results (activity <NUM> in <FIG>) is not employed, but all the prepared results retrieved from the second platform <NUM> and all updated versions of the prepared results retrieved from the first platform <NUM> are returned to the client <NUM>. In such embodiments, the prepared results retrieved from the second platform <NUM> are already returned to the client <NUM> as soon as they are available (activity <NUM> in <FIG>) which is generally earlier than retrieval of the updated versions of the prepared results from the first platform <NUM> concludes (because updating prepared results by the first platform generally requires substantially more time than retrieving prepared results from the second platform <NUM>, as explained in detail above). Hence, in this situation, activity <NUM> of <FIG> then only encompasses returning the updated versions of the prepared results retrieved from the first platform <NUM>.

In some embodiments, the message flow shown in <FIG> and <FIG> is also adapted in that the post-processing activity <NUM> is performed already at an earlier stage, for example by the control unit <NUM> after having received the content of the prepared results with activity 31B or by the second platform <NUM> before returning the prepared results (or at least their identities) with activity 31B. Again referring to the above example of returning the cheapest travel recommendation for travels between Frankfurt and Boston with a departure between <NUM>st July <NUM> and <NUM>th July <NUM> and a stay duration between <NUM> and <NUM> days, in some embodiments, the second platform <NUM> is arranged to determine a limited number of the most inexpensive travel recommendations for travels between Frankfurt and Boston with a departure between <NUM>st July <NUM> and <NUM>th July <NUM> and a stay duration between <NUM> and <NUM> days (as opposed to returning all priced travel recommendations for travels between Frankfurt and Boston with a departure between <NUM>st July <NUM> and <NUM>th July <NUM> and a stay duration between <NUM> and <NUM> days stored in the pool <NUM>). For example, with activity 31B in <FIG>, the second platform <NUM> returns only the five cheapest travel recommendations. The subsequent activities of the control unit <NUM> (activities 31C, 31D, 31E, <NUM>-<NUM>) are then limited to only these five retrieved prepared results and are performed in the same manner as described above.

In some embodiments, the threshold value is dynamically adapted depending on the load of the first platform <NUM>. In this way, by using the adaptive threshold value, the amount of prepared results which are updated via the first platform <NUM> and therefore the load of the first platform are controlled. If the load of the first platform <NUM> is too high (too many prepared results are updated via the first platform <NUM> in a given time unit) and the load is to be reduced, the threshold value is increased with the effect that the portion of prepared results which are updated via the first platform <NUM> is decreased and the portion of prepared results which are retrieved from the second platform <NUM> and returned to the client <NUM> without update is increased. If, on the other hand, the first platform <NUM> has free resources which can be utilized to update more prepared results in a given time unit than currently updated, the threshold value is decreased with the effect that the portion of prepared results which are updated via the first platform <NUM> is increased and the portion of prepared results which are retrieved from the second platform <NUM> and returned to the client <NUM> without update are decreased.

In some embodiments, dynamically adapting the threshold value is realized by maintaining a feedback control loop <NUM> between the first platform <NUM> and the control unit <NUM> (<FIG>). The feedback control loop <NUM> is defined by three variables, namely the control value <NUM>, the setpoint <NUM> and the actuating variable <NUM>. The control value <NUM> is the variable to be controlled (to be kept constant at a given target level) and is therefore defined by a current actual load factor of the first platform <NUM>. The setpoint <NUM> of the feedback control loop <NUM> is given by a desired target load factor of the first platform <NUM>. The actuating variable of the feedback control loop <NUM> is the threshold value which impacts the actual load factor of the first platform, i.e. controls the control value <NUM>.

In some embodiments, the feedback control loop <NUM> is realized by the first platform <NUM> and the control unit <NUM> communicating with each other in regular intervals as follows. The first platform regularly compares the current actual load factor <NUM> with the desired target load factor <NUM>. If the current actual load factor <NUM> is N% higher than the desired target load factor <NUM> (e.g. <NUM>%), the threshold value is increased by a ratio N/B% (e.g. <NUM>% divided by <NUM> = <NUM>%) wherein B is a smoothing avoiding overreactions of the dynamic threshold value adaption and enabling a smooth convergence between the current load <NUM> and the target load <NUM>. As a result of the decreased threshold value, the current actual load factor <NUM> will decrease. If, on the other hand, the current actual load factor <NUM> is below the desired target load factor <NUM> by N%, the threshold value is decreased by N/B%, resulting in a higher amount of prepared results being updated with the first platform <NUM> and, thus, increasing the current actual load factor <NUM>.

Finally, <FIG> is a diagrammatic representation of a computer system which provides the functionality of the control unit <NUM>. Within the control unit <NUM>, a set of instructions, to cause the computer system to perform any of the methods discussed herein, are executed. The control unit <NUM> includes a processor <NUM>, a main memory <NUM> and a network interface device <NUM>, which communicate with each other via a bus <NUM>. Optionally, the control unit <NUM> further includes a static memory <NUM> and a disk-drive unit <NUM>. A video display <NUM>, an alpha-numeric input device <NUM> and a cursor control device <NUM> may form a user interface for e.g. an administrator to control the control unit <NUM>.

The network interface device <NUM> connects the control unit <NUM> to the first platform <NUM> via the interface <NUM> and to the second platform <NUM> via the interface <NUM>. The network interface device <NUM> also connects the control unit <NUM> to the clients <NUM> via interface <NUM>. A set of instructions (i.e. software) <NUM> embodying any one, or all, of the methods described above, resides completely, or at least partially, in or on a machine-readable medium, e.g. the main memory <NUM> and/or the processor <NUM>. A machine-readable medium on which the software <NUM> resides may also be a non-volatile data carrier (e.g. a non-removable magnetic hard disk or an optical or magnetic removable disk) which is part of disk drive unit <NUM>. The software <NUM> may further be transmitted or received as a propagated signal e.g. via the Internet or any other network through the network interface device <NUM>. Basic operation of the control unit <NUM> including user interface and network communication is controlled by operating system <NUM>.

The present approach to control routing of incoming data requests by the control unit to the first platform and or to the second platform on the basis of the update indicator (<NUM> - acc) · t being compared with the threshold value provides an improved the long-term validity of prepared results maintained in the pool of the second platform. This approach allows to optimally determine which prepared results to be returned in response to data requests are to be retrieved from the first platform and thereby updated in the second platform. In this way, an ineffective focus on repeatedly updating very volatile prepared result is avoided, thereby improving the accuracy/validity of the prepared results in the long run.

Claim 1:
A method for handling data requests directed to a database environment, the database environment (<NUM>) comprising a least one first platform (<NUM>) providing original results to be stored in a second platform (<NUM>) as prepared results, the second platform (<NUM>) maintaining a pool of the prepared results in order to be returned to data requests, and a control unit (<NUM>) for processing the data requests directed to the database environment (<NUM>), wherein each prepared result maintained in the pool of the second platform (<NUM>) is associated with an update indicator being a measure that the associated prepared result kept in the pool of the second platform (<NUM>) is to be updated, the method comprising:
- receiving, by the control unit (<NUM>), a data request;
- determining, by the control unit (<NUM>), at least one prepared result corresponding to the data request;
- comparing, by the control unit (<NUM>), the update indicator of the determined prepared result corresponding to the data request with a threshold value;
- in response to the control unit (<NUM>) determining that the comparison indicates a requirement to update the prepared result,
→ retrieving, by the control unit (<NUM>) from the first platform (<NUM>), an updated version of the at least one prepared result;
→ updating, by the control unit (<NUM>), the prepared result in the pool of the second platform (<NUM>) and the associated update indicator based on the updated version of the at least one prepared result by storing a new timestamp of the update of the at least one prepared result; and
→ returning, by the control unit (<NUM>), the updated version of the at least one result,
- in response to the control unit (<NUM>) determining that the comparison does not indicate a requirement to update the at least one prepared result,
→ the control unit (<NUM>) returning the at least one determined prepared result;
wherein the update indicator is defined by (<NUM> - acc) · t, wherein acc is a probability that the associated prepared result is valid and t is an age of the associated prepared result, wherein acc = e-λ t , wherein the validity rate λ is an indicator of how frequently the prepared result changes.