Handling data requests

Handling data requests directed to a database environment including a first platform, a second platform, and a control unit. The control unit receives a request, determines a prepared result corresponding to the data request and compares an update indicator of the determined prepared result with a threshold value. In response to the comparison, the control unit either retrieves the prepared result from the second platform and returns it or retrieves an updated version of the at least one prepared result from the first platform, updates the prepared result in the second platform and the associated update indicator, and returns the updated version of the prepared result. The update indicator may be defined by (1−acc)·t, wherein acc is a probability that the associated prepared result is valid and t is an age of the associated prepared result.

BACKGROUND

The present invention generally relates to database technology and, more specifically, is directed to a methods and systems for handling incoming data requests considering the accuracy of prepared results to be returned to a data request.

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.

A 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 accompanies 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.

Improved methods and systems are needed for handling incoming data requests considering the accuracy of prepared results to be returned to a data request.

SUMMARY

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. 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 (1−acc)·t, wherein acc is a probability that the associated prepared result is valid and t as an age of the associated prepared result.

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.

DETAILED DESCRIPTION

The methodologies described herein relate to database systems that offer prepared results to clients requesting data from a database system. A 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. 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. 1illustrates such a database environment1at an abstract level. Original data, hereinafter also referred to as original results, are provided by a first platform3. In general, the first platform3is 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 platform3generates/computes/collects the original results by accessing other/further original data sources in order to prepare original results, the first platform3provides results which generally accurately reflect the current content of the original response data. More than one first platform3can be present in the database environment1.

The database environment1further includes a second platform4which maintains a pool5of results which have been prepared via the first platform3. The second platform4is e.g., a cache that caches results having been retrieved via the first platform3, or the second platform4is e.g., a server holding a repository of the content of crawled websites, or the second platform4is e.g., a search platform maintaining pre-computed priced travel recommendations.

In general, the first platform3providing original response data and the second platform4maintaining the pool5of prepared results differ from each other in technical terms as follows: The second platform4, 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 platform3. This relation between the first platform3and the second platform4can also be expressed the other way around, i.e., the first platform3generally responds more slowly and responses from the first platform3involve higher computation costs than responses from the second platform4because the first platform3still 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 platform3are limited, the number of accesses to the first platform3should be kept within a certain limit. For example, CPU consumption or memory load of the first platform3must 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., 10 accesses per second). For these reasons, the first platform3is not solicited each time in order to respond to data requests. Rather, responses are generally formed by utilizing the prepared results stored in the pool5of the second platform4. In this way, the second platform4acts as a shield in front of the first platform3, thereby reducing the load on the (computationally expensive) first platform3.

On the other hand, however, the prepared results stored in the pool of the second platform4are not necessarily perfectly synchronized with the original results provided by the first platform3. In general, the prepared results of the second platform4represent older versions of original result being provided by the first platform3and the respective version of the original result provided by the first platform3might have changed since the last update of the corresponding prepared result maintained in the second platform4. Furthermore, the second platform4does not necessarily store prepared results corresponding to all existing original results, i.e., prepared results might be missing in the second platform4. Prepared results stored in the pool5of the second platform4which 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 pool5of the second platform4are referred to as invalid prepared results or inaccurate prepared results.

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

The database environment1is further coupled to at least one, but generally a plurality of clients6. Clients6such as applications on user terminals retrieve results from the database environment1by directing data requests to the database environment1via an interface7. The technical characteristics of the interface7depend on the particular implementation of the database environment1. For example, the interface7encompasses wireless communication including 2G/3G/4G (including packet-oriented mobile data exchange as well as SMS) and/or WiFi communication in the case the client6is situated on a mobile communications device. Alternatively or in addition, the interface7features 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 client6via interface7includes 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 client6are received by a further entity of the database environment1, the control unit2(FIG. 1). In general, the control unit2processes incoming data requests in order to device whether response results are retrieved from the second platform4and/or the first platform3. To this end, the control unit functions as an intermediate unit controlling the data flow within the database environment1and the results to be returned to the client6.

Basically, controlling the data flow by the control unit2takes 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 pool5of the second platform4has the advantage of a faster response time (compared to generating the results by the first platform3) and relieves the first platform3from potential overloads. On the other hand, however, serving a data request by retrieving original results provided by the first platform3allows to update the respective prepared results maintained in the pool5of the second platform4. Thus, a portion of results to be returned in response a data requests can be intentionally retrieved from the first platform3, although corresponding prepared results are available in the second platform4. These results are thus newly prepared by the first platform3and returned to the requesting client6and stored in the pool5of the second platform4thereby updating the corresponding prepared results.

The technical problem is then to decide which portions of the data requests being transmitted from the clients6to the control unit2are to be responded on the basis of the pool5of the second platform4and which portions of the data requests are to be responded on the basis of the first platform3in order to update the prepared results maintained in the pool5of the second platform4.

To this end, the control unit2utilizes an update indicator which is associated with each prepared result maintained in the pool5of the second platform4. In general, the update indicator is a measure whether or not the associated prepared result kept in the pool5of the second platform4needs to be updated. The update indicator is defined by (1−acc)·t (cf.FIG. 1), 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 pool5of the second platform4can be specified by the following parameters.

The age tiof the prepared result i denotes the time since the first preparation or the last update (whichever occurred last) of the prepared result i via the first platform3. The age tican be calculated dynamically at a given point of time by computing the time interval since the last preparation of the prepared result i (current time minus time of last preparation/update). To this end, the timestamp of the most recent preparation of the prepared result is stored in order to compute the age tiof the prepared result i when necessary.

The probability accithat the prepared result i is valid. This probability can be predicted by a probabilistic model modeling the validity behavior of prepared results. An example of such a model is based on a validity rate of a prepared result i which is described next.

The validity rate λiof the prepared result i is an indicator of how frequently the result i prepared by the first platform3changes and thus how fast the prepared result i stored in the pool5of the second platform4becomes invalid due to changes of the result i provided by the first platform3(e.g., due to changes of the data kept by the first platform3or by changes in data kept by other data sources on the basis of which the first platform3computes the result i). This validity rate λiof a given prepared result i is, for example, statistically derived from the occurrence and the outcomes of past preparations and updates and comparisons of the updated prepared result i with its previous state or values in order to determine whether the prepared result i with age tiwas still valid (its state or value is not changed by the update) or whether the prepared result i with age tiwas invalid (its state or value is changed by the update). For example, it has been determined that a particular prepared result i has a validity rate λiof 10% per hour meaning that the probability of i being valid decreases by 10% every hour. At the time of an update of the prepared result i, i is generally 100% valid. After one hour, i is valid with a probability of 90%. After two hours the validity of i is 81% (=90% decreased by another 10%). After three hours, i's probable validity is at 72.9%, and so on.

As mentioned above, the validity rate λican be employed to provide an estimate of the probability for a prepared result to stay valid after a given time P (unchanged after t)=e−λitwhich, in some embodiments, is considered to be the probability of a prepared result being valid or, in other words, not being outdated acci=e−λiti. Two exemplary functions of this probable accuracy decreasing over time are depicted byFIG. 3. Function16represents a prepared result which potentially remains more accurate (or, more correctly, stays at a higher probability of being valid over time) than another prepared result associated with function17. For example, the prepared result represented by function16has 70% probability of being still valid at 35 hours after its last re-computation, while the other prepared result characterized by function17is only valid up to about 50% at 35 hours after its latest re-computation. Functions16and17may also represent whole sets of prepared results and then indicate proportions of the sets of prepared results likely being valid at a time passed since the last update of the set.

The popularity piof the prepared result i is an average access frequency to this prepared result by the clients6via interface7. Some embodiments aim at achieving a better accuracy for these prepared results which are more often requested by the clients6than other prepared results.

The update cost cirelates to computation resources (such as the amount of CPU time, but also encompassing e.g., network resources required e.g., to collect original response data from other sources as mentioned above) of the first source to update the prepared result i. In some embodiments, indications of cifor different prepared results are available (e.g., from previous updates). In this case, the update cost parameter can be used to favor updating prepared results requiring less computation resources than other prepared results in order to update more prepared results. Otherwise, an assumption can be made that all prepared results have the same update costs. In any case, in some embodiments, the update cost parameter is used to limit the number of updates per time unit to the amount of computing resources available at the first platform3, i.e., Σi updatedci≤Resources for each unit of time.

With these parameters, the validity probability of the prepared results stored in the pool5of the second platform4can be defined as follows.

The validity probability of all prepared results kept in the pool5of the second platform4can be considered as the mean validity, also referred to as “global accuracy”, which is defined by

Global⁢⁢Accuracy=1N⁢∑i∈pool⁢acci
with N being the number of prepared results stored in the pool5of the second platform4.

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

The validity probability of the prepared results in the pool5of the second platform4from the perspective of the clients6(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:

User⁢⁢Accuracy=∑i∈pool⁢piptot⁢acci=∑i∈pool⁢piptot⁢e-λi⁢ti
wherein ptotis defined as the sum of all pi.

The update indicator utilized by the control unit2to decide whether to return prepared results maintained in the pool5of the second platform4or whether to retrieve updated prepared results from the first platform3in order to both, return the updated results to the requesting client6as well as update the respective prepared results in the pool5of the second platform4thereby increasing the validity of the prepared results in the second platform4is formed by these parameters assigned to each of the prepared results in the second platform4. In the most basic form, the update indicator described herein is given by (1−acc)·t, for a particular prepared result i by (1−acci)·ti. On some embodiments, refined definitions based on this basic form are utilized, such as

(1-acc)·tc,or⁢⁢p·(1-acc)·tc.
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 unit2employs the update indicator as follows (seeFIG. 2AandFIG. 2B).

The control unit2receives a data request30from a client6. Then, the control unit2determines at least one prepared result corresponding to the data request30(activity31). Thus, the control unit2processes the data request30, determines the data retrieval criteria included in the data request30(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 unit2depends on the architecture of the database environment1(a particular example is given further below with reference toFIGS. 4 and 5). For example, in the case of the data request30being an SQL query, the control unit2determines 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 platform4or another module existing within the database environment1for that purpose.

This determination of prepared results fulfilling data retrieval criteria of the data request30does 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, activity31already encompasses retrieval of the content of the prepared results fulfilling data retrieval criteria of the data request30from the second platform4.

Further on, the control unit2compares the update indicators of the determined prepared results with a threshold value (activity32inFIG. 2AandFIG. 2B). At a more detailed level, this activity32involves a determination of the update indicator values of each of the determined prepared result. To this end, the control unit2e.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 (1−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 platform3in response to receiving data requests30and the complimentary amount of prepared results which are not updated in response to receiving data requests30, but returned to the client6from the pool5of the second platform4.

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 toFIGS. 6A and 6Band is also applicable to any other examples described herein).

In the case the comparison indicates a requirement to update the prepared results (box33inFIG. 2A), the control unit2retrieves updated versions of the determined prepared results from the first platform3(e.g., by relaying the data request to the first platform3) (message34inFIG. 2A). The first platform3prepares the updated versions of the prepared results and returns these updated versions of the prepared results to the control unit2. The control unit2receives the updated versions of the prepared results from the first platform3by message35. The control unit2then updates the determined prepared search result in the pool5of the second platform4(activity36inFIG. 2A). In addition, the control unit2also updates the update indicator values associated with the determined prepared results (also activity36inFIG. 2A) such as storing the new timestamp of this update of the determined prepared results. Finally, the control unit2returns the updated version of the determined prepared results to the client6by message37. Note that activities36and37may also occur in a different order, i.e., the control unit2first returns the prepared results to the client6and then updates the prepared results in the second platform and the associated update indicators.

On the other hand, in the case the comparison32does not indicate a requirement to update the determined prepared results (box38inFIG. 2B), the control unit2returns the determined prepared results to the client6by message39, without updating the prepared results by inquiring the first platform3.

The above basic definition of the update indicator as being given by (1−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 λiwhich 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 by proposing to update those objects in a cache with the highest product Pi=Psi(t)×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

pi⁡(1-acci)ci
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 pool5in 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 platform4by establishing a decision metric to either respond to a data request either with prepared results updated by the first platform3(which at the same time update the corresponding prepared results in the second platform4) or to respond to a data request either with non-updated prepared results being held in the second platform4without inquiring the first platform3and updating these prepared results in the second platform4. 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 (1−acci), or refined versions of this such as

pi⁡(1-acci)ci.
Further, as also explained above, the computation costs to update a prepared result i by the first platform is denoted as ci. These costs ciare incurred with each update of the prepared result i by the first platform3. 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 ciover 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 fiof the prepared result i (e.g., fi=20 updates of i within 120 hours=⅙ or fi=6 updates of i within 120 hours= 1/20)
Long Term Update Costsi=ci×fi.

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

1-acciLong⁢⁢term⁢⁢Costi=t⁢1-accici⁢fi.
The actual long-term update frequency fiis generally unknown, but can be approximated by the following consideration: If, in response to a data request30, 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

1ti.
This will actually become true if the decision to update the prepared result i is indeed by taken. In other words,

1t1
is considered as a potential long-term update frequency of the prepared result i. For this reason, the ratio

citi
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 pool5of the second platform4should therefore update the prepared results with the highest

This definition of the update indicator can still be generalized when assuming that the update cost ciis 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 platform3. In this case, the factor cican be removed from the update indicator resulting in the definition of the update indicator as introduced above, i.e., (1−acci)·ti.

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:

Furthermore, accimay be replaced by the specifically employed probabilistic model modeling the validity of prepared results decreasing over time, such as acci=e−λitias deduced further above. This results in more specific version of the update indicator definitions, namely

FIG. 4present a more specific example of a database environment1. This example differs from the more general architecture shown byFIG. 1in that it includes certain additional components, namely the control data store10and the predictive model manager12. The control data store10is connected to the control unit2via interface11and to the predictive model manager via interface15. The predictive model manager is connected to the first platform3via interface13, to the control unit2via interface14and to the control data store via interface15.

In some embodiments, the control data store10stores data to compute the update indicator for given prepared results stored in the pool5of the second platform4. In particular, the control data store10stores timestamps indicating the last update time of the prepared results in order to compute the age tiat a given point of time. Optionally, the control data store10stores data to model the probability for prepared results maintained in the pool5of the second platform4to be accurate, for example the validity rates λiof the prepared results in order to compute acci=e−λitiat a given point of time. Optionally, the control data store10further 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) piof the prepared results stored in the pool5of the second platform4and/or the computation costs cito update prepared results. The control data kept by the control data store10is associated with the prepared results stored maintained in the pool5of the second platform4. Thus, the control data stored10also 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 store10is defined as follows:
(identification of prepared result i, last update time of i, λi, pi, ci)

The identification of the prepared results utilized in the control data store10is, for example, the primary key values of the prepared results as stored in the pool5of the second platform4.

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

The predictive model manager12is 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 manager12receives input data from the first platform3and from the control unit2. More specifically, the first platform3transmits information about the updated prepared results (the updates occurring in response to messages34(FIG. 2A)) to the predictive model manager12, 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 platform3also transmits information regarding the computation costs to update prepared results to the model manager12(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 unit2transmits information about incoming data requests30and the prepared results requested by the data requests30to the predictive model manager12, e.g., which prepared results were returned to inquiring clients at which times. In some embodiments, this input communication from the first platform3and/or from the control unit2to the predictive model manager12occurs asynchronously from processing and serving data requests30as visualized byFIGS. 2A, 2B, 5A, 5B, 6A and 6B. In other embodiments, the first platform3transmits the information about an updated prepared result to the predictive model manager12synchronously with the update, e.g., immediately after the first platform3has returned the updated result to the control unit2. In such embodiments, also the control unit2may transmit the information about incoming data requests30and respective returned results to clients6to the predictive model manager12synchronously with the processing of the data requests30, e.g., immediately after the control unit2has returned the corresponding results to the inquiring client6.

The predictive model manager12processes these inputs from the first platform3and the control unit2and provides current control information resulting from the processing to the control data store10. More specifically, the predictive model manager12utilizes the information about the updated prepared results received from the first platform3, 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 λifor each of the prepared results stored in the pool5of the second platform4. The predictive model manager12utilizes the information about the computational costs received from the first platform3to maintain the parameters cifor each prepared result i stored in the pool5of the second platform4. The predictive model manager12utilizes the information about the incoming data requests30received from the control unit2and correspondingly requested prepared results in order to maintain the popularity values pifor each of the prepared results stored in the pool5of the second platform4. The resulting current values of λi, piand/or ciare transmitted from the predictive model manager to the control data store10and are thus made available to the control unit2in order to determine the update indicator values in the course of processing incoming data requests30(activity31). Updates of the current values of λi, piand/or ciare sent by the predictive model manager12to 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 manager12and/or the control data store10employ 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 ofFIG. 4are shown byFIGS. 5A and 5B. Similar toFIGS. 2A and 2B,FIG. 5Ashows the variant in which the update indicator values of the prepared results to be returned to the client6indicate a need to update the prepared results andFIG. 5Bshows the variant in which the update indicator values of the prepared results to be returned to the client6do not indicate a need to update the prepared results.

In both variants, the process begins with a transmission of a data request30from the client6to the control unit2. In response to receiving the data request30, the control unit2determines identification information (e.g., primary key values) of prepared results which fulfill criteria included in the data request30and associated update indicator values (activity31A). As a simple example, the data request30requests the number of available seats in the flight LH123 on 1 Jul. 2015. In response to receiving this data request30, the control unit2utilizes the key “LH123-1JUL15” already included in the request to retrieve the last update time of the prepared result LH123-1JUL15-42 (i.e., the prepared result indicates 42 free seats, wherein the number42of available seats is not known to the control unit2at that stage) and the validity rate λLH123-1JUL15from the control data store10. The control data store10responds with respective values of the update timestamp and validity rate λLH123-1JUL15(activity31B inFIGS. 5A and 5B). The control unit2then calculates the update indicator of the prepared result LH123-1JUL15-42 (activity31C inFIG. 5AandFIG. 5B) by calculating the age tLH123-1JUL15(last update timestamp of LH123-1JUL15-42 minus current time) and then calculating (1−e−λiti)ti.

The control unit2then performs the comparison of the calculated update indicator value with the threshold value (activity32inFIG. 5AandFIG. 5B). If the comparison indicates a need to update the LH123-1JUL15-42 (box33inFIG. 5A), the control unit2retrieves an updated version of the prepared result from the first platform3(activity34inFIG. 5A). In an embodiment, the first platform itself is an original inventory of available flight seats and returns the update value (e.g., LH123-1JUL15-23, i.e., 23 free seats) to the control unit2on the basis of its own inventory data. In another embodiment, the first platform3retrieves the requested current available seat information from further sources and returns the updated prepared result LH123-1JUL15-23 to the control unit2afterwards (activity35inFIG. 5A). The control unit2, after having received the updated prepared result from the first platform3, returns the updated prepared result to the client6(activity37inFIG. 5A), updates the prepared result in the pool5of the second platform4(e.g., by replacing the previous outdated value42with the updated, current value23, activity36A) and also updates the last update timestamp of LH123-1JUL15 in the control data store10(activity36B). Note that activities36A,36B and37may occur in any order.

Alternatively, the comparison between the current update indicator value of LH123-1JUL15 and the threshold conducted by control unit2(activity32) indicates that an update of LH123-1JUL15 is not necessary (box38inFIG. 5B). In this case, the control unit2retrieves the value of LH123-1JUL15 (e.g., 42 available seats) from the pool5of the second platform4(activity40A inFIG. 5B) and returns this value as a response to data request30to the client6(activity activity39).

In other embodiments, depending on the content and definition of the prepared results and criteria included in the data request30, activity31is more complex (FIGS. 6A and 6B) e.g., because the key values of the prepared results in which the client6is interested are not included in the data request30and, thus, a search may be required to determine which prepared results fulfill the search criteria included in the data request30. For example, the prepared results stored by the pool5specify pre-computed priced travel recommendations and the data request30e.g., asks for the cheapest travels between Frankfurt and Boston with a departure between 1 Jul. 2015 and 10 Jul. 2015 and a stay duration between 11 and 15 days. In scenarios of this type, in some embodiments, the control unit2first identifies prepared results stored in the pool5of the second platform4which fulfill search criteria of the data request30. Thus, in these embodiments, activity31A (FIG. 6A) is an inquiry of the control unit2to the second platform4in order to retrieve identification information of prepared results complying with the search criteria included in the data request30. Referring to the latest example, the second platform4e.g., returns all travel recommendations stored in the pool5for travels between Frankfurt and Boston with a departure between Jul. 1, 2015 and Jul. 10, 2015 and a stay duration between 11 and 15 days (activity31B inFIG. 6A).

The control unit2then determines the update indicator values for all identified prepared results in the manner described above (retrieving the respective control data from the control data store10by activities31C and31D inFIG. 6Aand calculating the update indicator values by activity31E inFIG. 6A) and performs the comparison between update indicator value and threshold for each identified prepared result (activity32inFIG. 6A). For all prepared results for which the comparison indicates a need to update the respective prepared result (box33inFIG. 6A), the control unit2retrieves an updated version of the respective prepared result from the first platform3(activities34and35inFIG. 6B). 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 unit2retrieves the content of these not-to-be-updated prepared results from the second platform4(activities40A and40B inFIG. 6B; this applies if the control unit2has not already retrieved the content of all the prepared results fulfilling the search criteria with activities31A and31B beforehand). After having received the updated versions of the prepared results in response to request34(activity35), the control unit2stores the updated prepared results in the pool5of the second platform4(activity36A inFIG. 6B), updates the update timestamps of the updated prepared results in the control data store10(activities36B in FIG. B), optionally post-processes the prepared results retrieved from the second platform4and the updated versions of the prepared results retrieved from the first platform3(activity41inFIG. 6B), 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 client6(in the above example, selecting the most inexpensive travel recommendation), and returns these results to the client6(activity37inFIG. 6B).

In some embodiments, still different message flows are employed, depending on the particular characteristics of the database model(s) employed by the database environment1and structure and criteria included in the data requests30. For example, in some embodiments, post-processing of prepared results (activity41inFIG. 6A) is not employed, but all the prepared results retrieved from the second platform4and all updated versions of the prepared results retrieved from the first platform3are returned to the client6. In such embodiments, the prepared results retrieved from the second platform4are already returned to the client6as soon as they are available (activity39inFIG. 6B) which is generally earlier than retrieval of the updated versions of the prepared results from the first platform3concludes (because updating prepared results by the first platform generally requires substantially more time than retrieving prepared results from the second platform4, as explained in detail above). Hence, in this situation, activity37ofFIG. 6Bthen only encompasses returning the updated versions of the prepared results retrieved from the first platform3.

In some embodiments, the message flow shown inFIGS. 6A and 6Bis also adapted in that the post-processing activity41is performed already at an earlier stage, for example by the control unit2after having received the content of the prepared results with activity31B or by the second platform4before returning the prepared results (or at least their identities) with activity31B. Again referring to the above example of returning the cheapest travel recommendation for travels between Frankfurt and Boston with a departure between Jul. 1, 2015 and Jul. 10, 2015 and a stay duration between 11 and 15 days, in some embodiments, the second platform4is arranged to determine a limited number of the most inexpensive travel recommendations for travels between Frankfurt and Boston with a departure between Jul. 1, 2015 and Jul. 10, 2015 and a stay duration between 11 and 15 days (as opposed to returning all priced travel recommendations for travels between Frankfurt and Boston with a departure between Jul. 1, 2015 and Jul. 10, 2015 and a stay duration between 11 and 15 days stored in the pool5). For example, with activity31B inFIG. 6B, the second platform4returns only the five cheapest travel recommendations. The subsequent activities of the control unit2(activities31C,31D,31E,32-38) 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 platform3. In this way, by using the adaptive threshold value, the amount of prepared results which are updated via the first platform3and therefore the load of the first platform are controlled. If the load of the first platform3is too high (too many prepared results are updated via the first platform3in 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 platform3is decreased and the portion of prepared results which are retrieved from the second platform4and returned to the client6without update is increased. If, on the other hand, the first platform3has 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 platform3is increased and the portion of prepared results which are retrieved from the second platform4and returned to the client6without update are decreased.

In some embodiments, dynamically adapting the threshold value is realized by maintaining a feedback control loop16between the first platform3and the control unit2(FIG. 7). The feedback control loop16is defined by three variables, namely the control value17, the setpoint18and the actuating variable19. The control value17is 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 platform3. The setpoint18of the feedback control loop16is given by a desired target load factor of the first platform3. The actuating variable of the feedback control loop16is the threshold value which impacts the actual load factor of the first platform, i.e., controls the control value17.

In some embodiments, the feedback control loop16is realized by the first platform3and the control unit2communicating with each other in regular intervals as follows. The first platform regularly compares the current actual load factor17with the desired target load factor18. If the current actual load factor17is N % higher than the desired target load factor18(e.g., 10%), the threshold value is increased by a ratio N/B % (e.g., 10% divided by 2=5%) wherein B is a smoothing avoiding overreactions of the dynamic threshold value adaption and enabling a smooth convergence between the current load17and the target load18. As a result of the decreased threshold value, the current actual load factor17will decrease. If, on the other hand, the current actual load factor17is below the desired target load factor18by N %, the threshold value is decreased by N/B %, resulting in a higher amount of prepared results being updated with the first platform3and, thus, increasing the current actual load factor17.

Finally,FIG. 8is a diagrammatic representation of a computer system which provides the functionality of the control unit2. Within the control unit2, a set of instructions, to cause the computer system to perform any of the methods discussed herein, are executed. The control unit2includes a processor81, a main memory82and a network interface device83, which communicate with each other via a bus84. Optionally, the control unit2further includes a static memory85and a disk-drive unit86. A video display87, an alpha-numeric input device88and a cursor control device89may form a user interface for e.g., an administrator to control the control unit2.

The network interface device83connects the control unit2to the first platform3via the interface9and to the second platform4via the interface8. The network interface device83also connects the control unit2to the clients6via interface7. A set of instructions (i.e., software)90embodying 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 memory82and/or the processor81. A machine-readable medium on which the software90resides 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 unit86. The software90may further be transmitted or received as a propagated signal e.g., via the Internet or any other network through the network interface device83. Basic operation of the control unit2including user interface and network communication is controlled by operating system91.

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 (1−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.

The program code embodied in any of the applications/modules described herein is capable of being individually or collectively distributed as a program product in a variety of different forms. In particular, the program code may be distributed using a computer-readable storage medium having computer-readable program instructions thereon for causing a processor to carry out aspects of the embodiments of the invention.

Computer-readable storage media, which is inherently non-transitory, may include volatile and non-volatile, and removable and non-removable tangible media implemented in any method or technology for storage of information, such as computer-readable instructions, data structures, program modules, or other data. Computer-readable storage media may further include RAM, ROM, erasable programmable read-only memory (EPROM), electrically erasable programmable read-only memory (EEPROM), flash memory or other solid state memory technology, portable compact disc read-only memory (CD-ROM), or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to store the desired information and which can be read by a computer. A computer-readable storage medium should not be construed as transitory signals per se (e.g., radio waves or other propagating electromagnetic waves, electromagnetic waves propagating through a transmission media such as a waveguide, or electrical signals transmitted through a wire). Computer-readable program instructions may be downloaded to a computer, another type of programmable data processing apparatus, or another device from a computer-readable storage medium or to an external computer or external storage device via a network.

Computer-readable program instructions stored in a computer-readable medium may be used to direct a computer, other types of programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer-readable medium produce an article of manufacture including instructions that implement the functions, acts, and/or operations specified in the flow-charts, sequence diagrams, and/or block diagrams. The computer program instructions may be provided to one or more processors of a general purpose computer, a special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the one or more processors, cause a series of computations to be performed to implement the functions, acts, and/or operations specified in the flow-charts, sequence diagrams, and/or block diagrams.

In certain alternative embodiments, the functions, acts, and/or operations specified in the flow-charts, sequence diagrams, and/or block diagrams may be re-ordered, processed serially, and/or processed concurrently consistent with embodiments of the invention. Moreover, any of the flow-charts, sequence diagrams, and/or block diagrams may include more or fewer blocks than those illustrated consistent with embodiments of the invention.