Methods and apparatus for ranking uncertain data in a probabilistic database

Methods and apparatus for ranking uncertain data in a probabilistic database are disclosed. An example method disclosed herein comprises using a set of data tuples representing a plurality of possible data set instantiations associated with a respective plurality of instantiation probabilities to store non-deterministic data in a database, each data tuple corresponding to a set of possible data tuple instantiations, each data set instantiation realizable by selecting a respective data tuple instantiation for at least some of the data tuples, the method further comprising determining an expected rank for each data tuple included in at least a subset of the set of data tuples, the expected rank for a particular data tuple representing a combination of weighted component ranks of the particular data tuple, each component rank representing a ranking of the data tuple in a corresponding data set instantiation, each component ranking weighted by a respective instantiation probability.

FIELD OF THE DISCLOSURE

This disclosure relates generally to database processing and, more particularly, to methods and apparatus for ranking uncertain data in a probabilistic database.

BACKGROUND

In many data processing and analysis applications, especially those involving large amounts of data, top-k ranking queries are often used to obtain only the k most relevant data tuples for inspection, with relevance represented as a score based on a scoring function. There are many existing techniques for answering such ranking queries in the context of deterministic relational databases in which each data tuple is an ordered sequence of deterministic attribute values. A typical deterministic relational database employs a deterministic relation to encode a set of tuples each having the same attributes to yield a single data set instantiation, with each tuple representing a particular deterministic occurrence of an ordered sequence of the attribute values. A top-k query of such a deterministic relational database returns the k tuples having the top scores in the single data set instantiation based on a specified scoring function that evaluates the ordered sequence of attribute values to determine a single score for each tuple.

A probabilistic database uses an uncertainty relation to encode the set of tuples into multiple possible non-deterministic data set instantiations due to the randomness associated with each tuple. Accordingly, each tuple may exhibit different scores having respective different likelihoods for some or all of the different possible non-deterministic data set instantiation realized by the uncertainty relation. Because each tuple can be associated with multiple different scores having respective different likelihoods, conventional top-k query techniques that rank tuples assuming a single score per tuple are generally not applicable in a probabilistic database setting.

DETAILED DESCRIPTION

Methods and apparatus for ranking uncertain (e.g., non-deterministic) data in a probabilistic database are disclosed herein. An example ranking technique described herein to rank data stored in a probabilistic database implemented by a database server uses a set of data tuples representing multiple possible data set instantiations to store the uncertain (e.g., non-deterministic) data in the probabilistic database. In the example ranking technique, each data tuple stored in the probabilistic database is capable of being realized by the database server into one of a set of possible data tuple instantiations through use of an uncertainty relation. Additionally, each possible data set instantiation is capable of being realized by the database server through use of the uncertainty relation to select particular data tuple instantiations of at least some of the data tuples in the set of data tuples for inclusion in the possible data set instantiation. Furthermore, each possible data set instantiation is associated with a respective instantiation probability representing the likelihood that the respective possible data set instantiation occurs among the entire set of possible data set instantiations.

The example ranking technique also determines an expected rank, or an approximate expected rank, for at least some of the data tuples. For example, in response to a top-k query, expected ranks may be determined for only a sufficient number of data tuples needed to determine the k data tuples having the top score. In contrast with conventional ranking of deterministic data in which each data tuple has a single rank associated with the single deterministic data set instantiation, the expected rank for a particular uncertain (e.g., non-deterministic) data tuple represents a combination of component rankings of the particular data tuple in each of the possible non-deterministic data set instantiations. Additionally, each such component ranking is weighted by the respective instantiation probability associated with the possible non-deterministic data set instantiation from which the component ranking of the particular data tuple is determined. In other words, each component ranking of a data tuple is weighted by the likelihood that the data tuple will actually have the component ranking when a particular one of the possible non-deterministic data set instantiations is realized.

The methods and apparatus described herein to determine expected ranks for data tuples stored in a probabilistic database can be tailored to take advantage of the uncertainty relation used by the probabilistic database to store and process the data tuples. For example, as discussed in greater detail below, the ranking techniques described herein can be tailored to determine expected ranks in conjunction with probabilistic databases employing an attribute-level uncertainty relation that associates sets of scores and respective score probabilities with each data tuple and then realizes a possible non-deterministic data set instantiation by selecting a score for each data tuple according to its score probability. Additionally or alternatively, the ranking techniques described herein can be tailored to determine expected ranks in conjunction with probabilistic databases employing a tuple-level uncertainty relation that associates each data tuple with a score and a score probability and then realizes a possible non-deterministic data set instantiation by determining whether to include each data tuple in the data set instantiation based on its score probability and a set of exclusion rules. Furthermore, pruning techniques are described that can potentially reduce the number of data tuples that need to be accessed to determine expected ranks in response to top-k queries.

As discussed above, in the context of deterministic databases, top-k ranking queries are often used to obtain only the k top data tuples for inspection. It can be argued that providing top-k queries in probabilistic databases may be even more important than in deterministic databases because the uncertainty relation can encode and realize many possible non-deterministic data set instantiations (also referred to herein as possible “worlds”), instead of only the single data set instantiation associated with the deterministic database. While there have been some attempts to implement ranking queries for probabilistic databases, most (if not all) of the existing techniques lack at least some of the intuitive properties of a top-k query over deterministic data. For example, as described below, top-k ranking queries for deterministic databases storing deterministic data exhibit the properties of exact-k (or exactness), containment, unique-rank, value-invariance and stability. In contrast, most (if not all) of the existing techniques for implementing top-k ranking queries for probabilistic databases fail to satisfy at least one of these properties. However, unlike the existing techniques, top-k queries for probabilistic databases based on the expected ranks determined by the example ranking techniques described herein do satisfy all of the properties of exact-k, containment, unique-rank, value-invariance and stability, as described in greater detail below.

Additionally, at least some example implementations of the ranking techniques described herein are adapted to determine expected ranks and process associated top-k queries efficiently for various models of uncertain (e.g., non-deterministic) data, such as the attribute-level and tuple-level uncertainty models. For example, for an uncertainty relation used to store N data tuples in a probabilistic data base, the processing cost for at least some of the example implementation described herein is shown to be on the order of N log N operations (denoted “O(N log N)”), which is on a par with simply sorting the data tuples. In contrast, existing attempts to implement ranking queries for probabilistic databases typically require a higher processing cost, typically on the order of O(N2) operations. Furthermore, in scenarios where there is a high cost for generating or accessing each data tuple, pruning techniques based on probabilistic tail bounds are described that allow early termination of the expected ranking procedure and still guarantee that the top-k data tuples have been found.

Turning to the figures, a block diagram of an example environment of use100for an example probabilistic database server105implementing an example probabilistic database110and an example expected ranking unit115according to the methods and/or apparatus described herein is illustrated inFIG. 1. The example environment of use100also includes a data network120configured to interconnect one or more example data capture units125and/or one or more example data sources130with the example probabilistic database server105. In the illustrated example, the data capture unit(s)125and/or the data source(s)130provide uncertain data to the probabilistic database server105via a data interface135for storage in the probabilistic database110. The example expected ranking unit115operates to rank the uncertain data stored in the probabilistic database105in response to one or more queries, such as a top-k ranking query, received form an example interface terminal140via a query interface145. Although the example environment of use100depicted inFIG. 1illustrates the example probabilistic database server105, the example data capture unit(s)125, the example data source(s)130and the example interface terminal140as being separate devices interconnected by the example data network120, the example methods and apparatus described herein may be used in many alternative environments in which uncertain data is to be ranked.

The example data network120included in the example environment of use100may be implemented by any type of data networking technology. For example, the data network120may be implemented by a local area network (LAN), a wide area network (WAN), a wireless LAN and/or WAN, a cellular network, the Internet, etc., and/or any combination thereof. Additionally, the example interface terminal140may be implemented by any type of terminal device, such as a personal computer, a workstation, a PDA, a mobile telephone, etc. In the illustrated example, the interface terminal140is configured to allow a user to formulate a query, such as a top-k ranking query, for receipt via the query interface145of the probabilistic database server105using any type of database query language, technique, topology, etc. In the case of a top-k or similar ranking query, the example interface terminal140is also configured to allow a user to specify one of multiple techniques for determining the ranking, at least in some example implementations. Additionally, the example interface terminal140is configured to display or otherwise present the query results, such as the top-k rankings, returned from via the query interface145from the probabilistic database server105. Although the interface terminal140is shown as being connected to the probabilistic database server105via the data network120in the illustrated example, the interface terminal140alternatively could be integrated with the probabilistic database server105.

Top-k ranking queries are a useful tool for focusing attention on data that is likely to be most relevant to a particular query. To support such rankings, data tuples stored in the example probabilitistic database110are associated with one or more scores determined by an example score computation unit150, usually using one or more scoring functions. In an example implementation, the score computation unit150determines one or more scores for each data tuple based on a pre-defined scoring function. In another example implementation, the score computation unit150additionally or alternatively determines one or more scores for each data tuple based on a user-defined scoring function specified via the example interface terminal140. For example, the example interface terminal140could be used to specify a query-dependent scoring function in a k-nearest-neighbor query of the example probabilistic database110which has been configured to store spatial information. In such an example, the score can be specified to be the distance of a data point to a query point. When the data points each correspond to multiple uncertain (e.g., noisy) measurements, the scores (e.g., distances) determined by the scoring function can be modeled as random variables and stored in the example probabilistic database110using an uncertainty model, as described in greater detail below. As another example, if the probabilistic database110stores data tuples each having multiple uncertain attributes on which a ranking query is to be performed, the user typically can specify a scoring function via the example interface terminal140that combines the multiple attributes to produce scores for use in ranking the tuples.

Additionally, the one or more scores determined by the example score computation unit150are each associated with a respective score probability determined by an example score probability computation unit155. In response to a top-k ranking query received via the example query interface145, the example expected ranking unit115returns the top-k (or k top ranked) data tuples from the example probabilistic database110based on the score and score probabilities determined by the example score computation unit150and the example score probability computation unit155for each of the stored data tuples. Example of scores and respective score probabilities that can be determined by the example score computation unit150and the example score probability computation unit155, as well as the resulting rankings determined by the example expected ranking unit115, are described in greater detail below.

In the example environment of use100, potentially massive quantities of data may need to be stored in the example probabilistic database110, which is why determining an ordering, or ranking, based on score is beneficial. However, an additional challenge in the example environment of use100is that the data is also inherently fuzzy or uncertain. For example, the data provided by the data source(s)130may correspond to multimedia and/or unstructured web data that has undergone data integration and/or schema mapping. Such data may be stored in the example probabilistic database110as data tuples each associated with one or more scores and respective score probabilities (e.g., such as confidence factors), with the scores and score probabilities reflecting how well the data tuples matched other data from other example data sources130. As another example, an example data capture unit125may provide measurement data, such as sensor readings obtained from a example sensor160, measured distances to a query point, etc. Such data is often inherently noisy, and is can be represented in the example probabilistic database110by a probability distribution rather than a single deterministic value. More broadly, any type of data source130, data capture unit125and/or sensor160can provide the uncertain data to be stored in the example probabilistic database110

As discussed in greater detail below, the example probabilistic database110is capable of representing a potentially large number of possible realizations, or non-deterministic data set instantiations, of the stored probabilistic data. This can result in a correspondingly large, and even exponential, increase relative to conventional deterministic relational databases in the size of the relation used to represent the stored data. Accordingly, it can be a challenge to extend the familiar semantics of the top-k queries to the probabilistic database setting, and to answer such queries efficiently.

For example, in deterministic database settings having deterministic (e.g., certain) data each with a single score value, there is a clear total ordering based on score from which a top-k ranking can be determined. This is readily apparent by analogy with the many occurrences of top-k lists in daily life, such as movies ranked by box-office receipts, athletes ranked by race times, researchers ranked by number of publications (or other metrics), etc. However, with uncertain data stored in the example probabilistic database110, there are two distinct orders to address: ordering by score and ordering by probability. The example expected ranking unit115operates to combine scores and score probabilities to order, or rank, the probabilistic data stored in the example probabilistic database110in a manner that satisfies the properties of exact-k, containment, unique ranking, value invariance and stability exhibited by ranking queries on deterministic data. More specifically, the exact-k (or exactness) property provides that the top-k list should contain exactly k items. The containment property provides that the top-(k+1) list should contain all items in the top-k. The unique-ranking property provides that within the top-k, each reported item should be assigned exactly one position, and that the same item should not be listed multiple times within the top-k. The value-invariance property provides that scores determine the relative relevance of the tuples and that changing the absolute value of a score without causing a reordering of the score relative to other scores should not change the top-k. The stability property provides that making an item in the top-k list more likely or more important should not remove it from the list.

The preceding properties are clearly satisfied for rankings of deterministic (e.g., certain) data, and capture intuitively how a ranking query should behave. It is desirable for rankings of probabilistic (e.g., uncertain) data stored in the example probabilistic database110to also exhibit these same properties. However, as discussed in greater detail below, most, if not all, of the existing techniques for implementing ranking queries for probabilistic data fail to satisfy at least one of these properties. In contrast, the example expected ranking unit115implements an expected ranking of probabilistic (e.g., uncertain) data stored in the example probabilistic database110that does exhibit all of these properties, at least for the example uncertainty models described below. Furthermore, the ability to satisfy the properties does not come at a price of higher computational costs. On the contrary, its is possible to construct efficient O(N log N) implementations to determine exactly the expected ranking of data represented using both the attribute-level uncertainty model and the tuple-level uncertainty model, whereas many of the existing techniques require O(N2) operations to determine exact rankings.

While an example manner of implementing the example probabilistic database server105included in the example environment of use100has been illustrated inFIG. 1, one or more of the elements, processes and/or devices illustrated inFIG. 1may be combined, divided, re-arranged, omitted, eliminated and/or implemented in any other way. Further, the example probabilistic database110, the example expected ranking unit115, the example data interface135, the example query interface145, the example score computation unit150, the example score probability computation unit155and/or, more generally, the example probabilistic database server105ofFIG. 1may be implemented by hardware, software, firmware and/or any combination of hardware, software and/or firmware. Thus, for example, any of the example probabilistic database110, the example expected ranking unit115, the example data interface135, the example query interface145, the example score computation unit150, the example score probability computation unit155and/or, more generally, the example probabilistic database server105could be implemented by one or more circuit(s), programmable processor(s), application specific integrated circuit(s) (ASIC(s)), programmable logic device(s) (PLD(s)) and/or field programmable logic device(s) (FPLD(s)), etc. When any of the appended claims are read to cover a purely software and/or firmware implementation, at least one of the example probabilistic database server105, the example probabilistic database110, the example expected ranking unit115, the example data interface135, the example query interface145, the example score computation unit150and/or the example score probability computation unit155are hereby expressly defined to include a tangible medium such as a memory, digital versatile disk (DVD), compact disk (CD), etc., storing such software and/or firmware. Further still, the example probabilistic database server105ofFIG. 1may include one or more elements, processes and/or devices in addition to, or instead of, those illustrated inFIG. 1, and/or may include more than one of any or all of the illustrated elements, processes and devices.

A block diagram of an example implementation of the probabilistic database110that may be implemented by the example probabilistic database server105ofFIG. 1is illustrated inFIG. 2. The example probabilistic database110ofFIG. 2includes example data tuple storage205to store data tuples representing uncertain data obtained from any number of sources, such as the example data source(s)130and/or the example data capture unit(s)125ofFIG. 1. The example data tuple storage205may be implemented by any type of data storage unit, memory, etc. The example probabilistic database110ofFIG. 2also includes an instantiation unit210capable of realizing possible data set instantiations using the data tuples stored in the example data tuple storage205. For example, each data set instantiation realized by the example instantiation unit210may represent a different possible outcome of the uncertain data represented by the data tuples stored in the example data tuple storage205.

Many models for representing uncertain data have been presented in the literature. Each model utilizes probability distributions to map the data tuples representing the uncertain data to possible worlds, with each world corresponding to a single data set instantiation. One approach is to expressly store each possible world and its associated probability in the example data tuple storage205. Such an approach is referred to as complete, because it can capture all possible outcomes and correlations among the uncertain data. However, complete models are very costly to describe and manipulate because there can be many combinations of data tuples each generating a distinct possible world.

Typically, it is possible to make certain independence assumptions concerning the uncertain data. For example, it is often assumed that unless correlations are expressly described, events are considered to be independent. Consequently, possible data set instantiations can be represented more compactly, with instantiation probabilities (e.g., likelihoods) computed using straight-forward probability calculations (e.g., such as multiplication of probabilities of independent events). A strong independence assumption leads to a basic model for storing data tuples in the example data tuple storage205in which each tuple has an associated probability of occurrence, and all tuples are assumed fully independent of each other. This is typically too strong an assumption, and so intermediate models allow for descriptions of simple correlations among tuples. Such descriptions extend the expressiveness of the models, while keeping probability computations tractable. Two such models for storing data tuples in the example data tuple storage205are the attribute-level uncertainty model and the tuple-level uncertainty model. Without loss of generality, in the following discussion the example probabilistic database110is assumed to employ only one uncertainty relation for use by the instantiation unit210to realize possible data set instantiations using the data tuples stored in the example data tuple storage205.

In the attribute-level uncertainty model, the example probabilistic database110stores uncertain data as a table of N data tuples in the example data tuple storage205. Each tuple includes one attribute whose value is uncertain, as well as potentially other attributes that are deterministic. The uncertain attribute has a discrete probability density function (pdf) describing its value distribution. Alternatively, the uncertain attribute could have a continuous pdf (e.g., such as a Gaussian pdf) describing its value distribution. In the latter case, the continuous pdf is converted to a discrete pdf having an appropriate level of granularity using, for example, a histogram.

When realizing a possible data set instantiation using attribute-level uncertain model, the example instantiation unit210selects a value for each tuple's uncertain attribute based on the associated discrete pdf, with the selection being independent among tuples. The attribute-level uncertainty model has many practical applications, such as sensor readings, spatial objects with fuzzy locations, etc. Additionally, conventional relational databases can be adapted to store uncertain data according to the attribute-level uncertainty.

For the purpose of processing ranking queries, it is assumed that the uncertain attribute represents the score for the tuple, and that the query requests a ranking based on this score attribute (otherwise, the ranking would be based on a single deterministic score for the tuple and conventional deterministic ranking techniques could be used). For example, let Xibe a random variable denoting a score of a tuple tiin the set of data tuples stored in the example probabilistic database110. It is assumed that Xiis characterized by a discrete pdf with bounded size, which is a realistic assumption for many practical applications, such as movie ratings, and string matching, etc. The general, continuous pdf case is discussed below. Ranking of the data tuples tiaccording to score the becomes equivalent to ranking the set of independent random variables X1, . . . , XN.

An example of an uncertainty relation300for storing data in the example data tuple storage205according to an attribute-level uncertainty model is illustrated inFIG. 3. In the example uncertainty relation300, data tuples305are stored in a tabular format, with each data tuple305(denoted ti) associated with a respective set of possible pairs310of scores (denoted vi,j) and score probabilities (denoted pi,j), for 1≦j≦si, the number of scores associated with the particular tuple ti. In the illustrated example, the scores vi,jfor each tuple tirepresent the possible values of the random variable Xirepresenting the score of the tuple ti. The score probabilities pi,jfor each tuple represent the discrete pdf characterizing the distribution of the scores vi,jfor the tuple ti. As such, a possible instantiation of the data tuple ticorresponds to a particular score vi,jand respective score probability pi,jfor the particular tuple ti.

In the tuple-level uncertainty model, the attributes of each tuple are fixed, but the entire tuple may or may not appear in a possible data set instantiation. In a basic tuple-level uncertainty model, each tuple t appears with probability p(t) independently. In more complex tuple-level uncertainty models, there are dependencies among the tuples, which can be specified by a set of exclusion rules, where each data tuple appears in a single exclusion rule τ and each tuple appears in at most one rule. In the examples that follow, an exclusion rule including a group of more than one data tuple is used to specify that only one tuple from the group may be selected for inclusion in a possible data set instantiation. Accordingly, the total probability for all tuples in one rule must be less or equal than one, so that selection can be interpreted as governed by a probability distribution. The tuple-level uncertainty model is useful in applications where it is important to capture the correlations between tuples.

An example of an uncertainty relation400for storing data in the example data tuple storage205according to a tuple-level uncertainty model is illustrated inFIG. 4. The example uncertainty relation400has N data tuples405(denoted ti) stored in a tabular format with associated scores410(denoted vi) and score probabilities415(denoted p(ti)). The score probability p(ti) for each tuple tirepresents how likely the tuple is selected by the example instantiation unit210for inclusion in a particular data set instantiation. The example uncertainty relation400also has M rules420(denoted τk). As described above, each data tuple appears in a single exclusion rule, each tuple appears in at most one rule and an exclusion rule including a group of data tuples is used to specify that only one tuple from the group may selected for inclusion in a possible data set instantiation. As such, a possible instantiation of the tuple ticorresponds to selecting the tuple tiwith score vifor inclusion in a possible data set instantiation based on the respective score probability p(ti) for the particular tuple tiand the exclusion rule that includes ti. For example, the second rule τ2in the example uncertainty relation400specifies that tuples t2and t4cannot appear together in any possible data set instantiation realized by the example instantiation unit210. The second the second rule τ2also specifies an implicit constraint that p(t2)+p(t4)≦1.

As mentioned above, the example instantiation unit210utilizes the uncertainty relation (denoted as D herein) to realize possible data set instantiations corresponding to possible worlds from the data tuples stored in the example data tuple storage205. In the attribute-level uncertainty model, the example instantiation unit210uses the uncertainty relation to instantiate a possible world by selecting a data tuple instantiation for each data tuple. For example, the instantiation unit210uses the uncertainty relation to select one value independently for each tuple's uncertain score attribute according to the score probabilities defining the distribution of scores for the tuple. For example, denote a possible data set instantiation corresponding to a possible world as W, and the selected value for ti's uncertain score attribute in W as wti. In the attribute-level uncertainty model, a data set instantiation probability representing how likely W is to occur is given by Equation 1, which is:

Pr[W]=∏j=1N⁢⁢pj,x,Equation⁢⁢1
where x satisfies vj,x=wtj. In other words, the data set instantiation probability representing how likely W occurs is determined by multiplying the individual score probabilities associated with particular score selected by the example instantiation unit210for each tuple. Because every tuple appears in every possible data set instantiation, the size of every possible data set instantiation in the attribute-level uncertainty model is N, the number of data tuples stored in the example data tuple storage205. In other words, for all WεS, |W|=N where S is the space of all possible worlds.

A particular example of using an attribute-level uncertainty relation to realize a set of possible data set instantiations corresponding to a set of possible worlds is illustrated inFIG. 5. In the illustrated example ofFIG. 5, an example uncertainty relation500is used to store three data tuples505and associated sets of score and score probability pairs510in the example data tuple storage205. The example uncertainty relation500is used by the example instantiation unit210to realize a set of possible data set instantiations515associated with a respective set of instantiation probabilities520. As illustrated inFIG. 5, each instantiation probability is determined by multiplying the score probabilities associated with the score values selected for each of the data tuples in the respective data set instantiation.

In the tuple-level uncertainty model, the example instantiation unit210uses the uncertainty relation D to instantiate a possible world by selecting data tuples for inclusion in the data set instantiation corresponding to the possible world, with selection based on the set of exclusion rules and the score probability associated with each selected tuple. In other words, the example instantiation unit210instantiates a possible world by selected data tuple instantiations for at least some of the set of data tuples, where a data tuple instantiation corresponds to selecting the data tuple with its associated score for inclusion in the possible world. Accordingly, a possible world W from the set of all possible worlds S is a subset of tuples stored in the example data tuple storage205selected according to the uncertainty relation D. The instantiation probability representing the likelihood a possible world W occurring is given by Equation 2, which is:

Pr[W]=∏j=1M⁢⁢pW⁡(τj),Equation⁢⁢2
where for any exclusion rule τεD, pW(τ) is defined by Equation 3, which is

pW⁡(τ)={p⁡(t),τ⋂W={t};1-∑ti∈τ⁢⁢p⁡(ti),τ⋂W=Ø;0,otherwise..Equation⁢⁢3
In other words, pW(τ) denotes the contribution to the instantiation probability made by the particular exclusion rule τ. A notable difference for the tuple-level uncertain model relative to the attribute-level uncertainty model is that not all data tuples appear in every possible data set instantiation. Therefore, the size of a possible world can range from 0 to N, the total number of data tuples stored in the example data tuple storage205.

A particular example of using a tuple-level uncertainty relation to realize a set of possible data set instantiations corresponding to a set of possible worlds is illustrated inFIG. 6. In the illustrated example ofFIG. 6, an example uncertainty relation600is used to store four data tuples605and associated scores610and score probabilities615in the example data tuple storage205. The example uncertainty relation600is also used to specify a set of three exclusion rules620. The example exclusion rules620specify that tuple t1can be selected for inclusion in any possible data set instantiation according to its score probability, tuple t3can be selected for inclusion in any possible data set instantiation according to its score probability, and tuples t2and t4cannot both be selected for inclusion in the same data set instantiation. The example uncertainty relation600is used by the example instantiation unit210to realize a set of possible data set instantiations625associated with a respective set of instantiation probabilities630. As illustrated inFIG. 6, each instantiation probability is determined by multiplying the contributions pW(τ) to the instantiation probability made by each particular exclusion rule τ, with the contribution pW(τ) for a particular rule τ determined according to Equation 3.

Both the attribute-level and tuple-level uncertainty data models provide succinct descriptions of a distribution of data set instantiations over a set of possible worlds S. Each possible world W corresponds to a fixed realization of the set of data tuples stored in the example probabilistic database110. As described below, the example expected ranking unit110operates to combine ranking results from all the possible worlds into a meaningful overall ranking without expressly realizing the many (possible exponentially many) possible worlds.

While an example manner of implementing the probabilistic database110ofFIG. 1has been illustrated inFIG. 2, one or more of the elements, processes and/or devices illustrated inFIG. 2may be combined, divided, re-arranged, omitted, eliminated and/or implemented in any other way. Further, the example data tuple storage205, the example instantiation unit210and/or, more generally, the example probabilistic database110ofFIG. 2may be implemented by hardware, software, firmware and/or any combination of hardware, software and/or firmware. Thus, for example, any of the example data tuple storage205, the example instantiation unit210and/or, more generally, the example probabilistic database110could be implemented by one or more circuit(s), programmable processor(s), application specific integrated circuit(s) (ASIC(s)), programmable logic device(s) (PLD(s)) and/or field programmable logic device(s) (FPLD(s)), etc. When any of the appended claims are read to cover a purely software and/or firmware implementation, at least one of the example probabilistic database110, the example data tuple storage205and/or the example instantiation unit210are hereby expressly defined to include a tangible medium such as a memory, digital versatile disk (DVD), compact disk (CD), etc., storing such software and/or firmware. Further still, the example probabilistic database110ofFIG. 2may include one or more elements, processes and/or devices in addition to, or instead of, those illustrated inFIG. 2, and/or may include more than one of any or all of the illustrated elements, processes and devices.

A first example implementation of the expected ranking unit115ofFIG. 1is illustrated inFIG. 7. Before proceeding with a description ofFIG. 7, several desirable properties of a ranking of uncertain data stored in the example probabilistic database110are described. Additionally, it is shown how various existing techniques that could be used for ranking uncertain data stored in the example probabilistic database110each fail to satisfy all of these desirable ranking properties. Subsequently, a description of the first example implementation of the expected ranking unit115is provided, including a discussion of how the expected ranking unit115satisfies all of the following desirable ranking properties.

As mentioned above, the desirable properties of a ranking of uncertain data stored in the example probabilistic database110include the properties of exact-k, containment, unique ranking, value invariance and stability exhibited by ranking queries on deterministic data. Taking each of these desirable ranking properties in turn, the exact-k property provides that the top-k list should contain exactly k items. Mathematically, the exact-k property provides that, given Rkas the set of tuples in the top-k query result, if the number of tuples stored according to the uncertainty relation D is at least k (i.e., if |D|≧k), then the size of the set of tuples in the top-k query result, Rk, is |Rk|=k.

The containment property provides that the top (k+1) list should contain all items in the top-k. In other words, the containment property captures the intuition that if an item is in the top-k, it should be in the top-k′ for any k′>k. Equivalently, the choice of k can be viewed as a slider that chooses how many results are to be returned to the user, and changing k should only change the number of results returned, not the underlying set of results. Mathematically, the containment property provides that, for any k, Rk⊂Rk+1. Replacing “⊂” withyields the weak containment property.

The unique-ranking property provides that within the top-k, each reported item should be assigned exactly one position, and that the same item should not be listed multiple times within the top-k. In other words, the rank assigned to each tuple in the top-k list should be unique. Mathematically, the unique-ranking property provides that, given rk(i) to be the identity of the tuple having rank i, then ∀i≠j, rk(i)≠rk(j).

The value-invariance property provides that scores determine only the relative behavior of the tuples and that changing the absolute value of a score without the relative ordering of the scores among the tuples should not change the top-k. In other words, the score function is assumed to yield a relative ordering, and is not an absolute measure of the value of a tuple. Mathematically, the value-invariance property is described as follows. Let D denote the uncertainty relation which includes score values v1≦v2≦ . . . . Let si′ be any set of score values satisfying v1′≦v′2≦ . . . , and define D′ to be D with all scores vireplaced with vi′. The value invariance property provides that Rk(D)=Rk(D′) for any k. For example, consider the example uncertainty relation600for the example tuple-level uncertainty model illustrated inFIG. 6. In the example uncertainty relation600, the example scores610are 70≦80≦92≦100, The value invariance property provides that the example scores610could be replaced with, for example, 1≦2≦3≦1000, and the result of the ranking would still be the same

The stability property provides that making an item in the top-k list more likely or more important should not remove it from the list. For the tuple-level uncertainty model, the stability property is described mathematically as, given a tuple ti=(vi, p(ti)) from D, if we replace tiwith ti↑=(vi↑, p(ti↑)) where vi↑≧vi,p(ti↑)≧p(ti), then tiεRk(D)ti↑εRk(D′), where D′ is obtained by replacing tiwith ti↑in D. For the attribute-level uncertainty model, the mathematical description of the stability property remains the same but with ti↑defined as follows. Given a tuple tiwhose score is a random variable Xi, ti↑is obtained by replacing Xiwith a random variable Xi↑that is stochastically greater or equal than Xi, denoted as Xi↑Xi. The stability property captures the intuition that if a tuple is already in the top-k, making it probabilistically larger should not eject it from the top-k. Stability also implies that making a non-top-k tuple probabilistically smaller should not bring it into the top-k.

Given these desirable properties associated with rankings of data, some further considerations regarding how to extend ranking queries to uncertain data are now discussed. In the attribute-level model, a tuple has a random score but it always exists in any possible data set instantiation corresponding to any possible world. In other words, every tuple participates in the ranking process in all possible worlds. In contrast, in the tuple-level model, a tuple has a fixed score but it may not always appear in a possible data set instantiation corresponding to a possible world. In other words, a tuple may not participate in the ranking process in some possible worlds. Even so, a ranking of uncertainty data represented by the tuple-level uncertainty model should still aim to produce a ranking over all tuples.

Considering the tuple-level uncertainty model, a difficulty of extending ranking queries to probabilistic data is that there are now two distinct orderings present in the data, and ordering based on score, and another ordering based on probabilities. These two types of ordering should be combined in some way to determine a top-k ranking. Various existing techniques for determining top-k rankings of uncertain data, and their shortcomings with respect to the desireable ranking properties, are now described.

Because a probabilistic relation can define exponentially many possible worlds, one existing approach to determine a top-k ranking finds the most likely top-k set that has the highest support over all possible worlds. Conceptually, such most likely top-k techniques extract the top-k tuples from each possible world, and compute the support (e.g., probability) of each distinct top-k set found. The U-Top k technique, described by Mohamed A. Soliman, Ihab F. Ilyas and K. C.-C. Chang in “Top-k Query Processing in Uncertain Databases,”ICDE2007, which is incorporated herein by reference in its entirety, reports the most likely top-k as the answer to the ranking query. This technique incorporates likelihood information, and satisfies the unique ranking, value invariance, and stability ranking properties. However, the U-Top k technique may not always return k tuples when the total number of tuples stored according to the uncertainty relation D is small, thus violating the exact-k property. Furthermore, the U-Top k technique violates the containment property, and there are simple examples where the top-k can be completely disjoint from the top-(k+1). For example, consider the example attribute-level uncertainty relation500ofFIG. 5. The top-1 result under the U-Top k definition is t1, since its probability of having the highest score in a random possible world is 0.24+0.16=0.4, which is larger than that of t2or t3. However, the top-2 result is (t2,t3) with a probability of being the top-2 of 0.36, which is larger than that of (t1,t2) or (t1,t3). Thus, the U-Top k technique determines a top-2 ranking that is completely disjoint from the top-1 ranking. Similarly one can verify that for the example tuple-level uncertainty relation600ofFIG. 6, the top-1 result is t1but the top-2 is (t2,t3) or (t3,t4). Regardless of what tie-breaking rule is used, the top-2 ranking determined by the U-Top k technique is completely disjoint from the top-1 ranking.

The U-Top k technique fails because it deals with top-k sets as immutable objects. Instead, the U-k Ranks technique, also described in “Top-k Query Processing in Uncertain Databases” mentioned above, considers the property of a certain tuple being ranked k th in a possible world. In particular, let Xi,jbe the event that tuple j is ranked i within a possible world. Computing the probability Pr[Xi,j] for all i,j pairs, the U-k Ranks technique reports the i th ranked tuple as argmaxjPr[Xi,j] or, in other words, as the tuple that is most likely to be ranked i th over all possible worlds. This technique overcomes the shortcomings of U-Top k and satisfies the exact-k and containment properties. However, the U-k Ranks technique fails to support unique ranking, as one tuple may dominate multiple ranks at the same time. A related issue is that some tuples may be quite likely, but never get reported. For example, in the example attribute-level uncertainty relation500ofFIG. 5, the top-3 under the U-k Ranks technique is t1,t3,t1, in which t1appears twice and t2never appears. As another example, in the example tuple-level uncertainty relation600ofFIG. 6, there is a tie for the third position, and there is no fourth placed tuple, even though N=4, Additionally, the U-k Ranks technique fails on stability, because when the score of a tuple becomes larger, it may leave its original rank but cannot take over any higher ranks as the dominating winner.

As an attempt to improve the U-k Ranks technique, the meaning of the kth ranked tuple can be changed from “tuple i is at rank k” to “tuple i is at rank k or better.” In other words, consider a definition of the top-k probability of a tuple as the probability that the tuple is in the top-k ranking over all possible worlds. The probabilistic threshold top-k query (abbreviated “PT-k”), described by M. Hua, J. Pei, W. Zhang and X. Lin in “Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach,”SIGMOD2008, which is incorporated herein by reference in its entirety, employs such a definition and returns the set of all tuples whose top-k probability exceeds a user-specified probability p. However, for a user specified p, the top-k list returned by PT-k may not contain k tuples, violating the exact-k property. Furthermore, if p is fixed and k is increased, the top-k lists does expand, but it satisfies only the weak containment property. For example consider the example tuple-level uncertainty relation600ofFIG. 6. If the user-specified probability p is set to p=0.4, then the top-1 list is (t1), but both the top-2 and top-3 lists contain the same set of tuples: t1,t2,t3. A further drawback of using PT-k for ranking is that user has to specify the threshold p, which can greatly affect the resulting ranking.

Similarly, the Global-Top k technique, described by X. Zhang and J. Chomicki in “On the Semantics and Evaluation of Top-k Queries in Probabilistic Databases,”DBRank2008, which is incorporated herein by reference in its entirety, also ranks the tuples by their top-k probability, and ensures that exactly k tuples are returned. However, the Global-Top k technique also fails to satisfy the containment property. For example, in the example attribute-level uncertainty relation500ofFIG. 5, the Global-Top k technique determines that the top-1 is t1, but the top-2 is (t2,t3). In the example tuple-level uncertainty relation600ofFIG. 6, the Global-Top k technique determines that the top-1 is t1, but the top-2 is (t3,t2).

The preceding existing techniques for ranking uncertain data all differ from traditional ranking queries in that they do not define a single ordering of the tuples from which the top-k is taken. In other words, these existing techniques do not resemble “top-k” in the literal interpretation of the term. An improvement over these existing techniques could be to compute the expected score of each tuple, rank the tuples according to this expected score, and then return the top-k tuples ranked according to the expected score. Such an approach would satisfy the exact-k, containment, unique ranking and stability properties. However, the expected score technique would be dependent on the values of the scores. For example, consider a tuple which has very low probability but a score that is orders of magnitude higher than the other tuples. Such a tuple could be propelled to the top of the ranking if it has the highest expected score, even though it is unlikely. However, if the score for this tuple was reduced to being just greater than the next highest score, the tuple would drop down in the ranking. As such, the expected ranking technique violates the value invariance property. Furthermore, in the tuple-level uncertainty model, simply using the expected score ignores the correlations among tuples described by the exclusion rules.

Having established the desirable properties of a ranking of uncertain data stored in the example probabilistic database110and the associated deficiencies of existing ranking techniques, as well as the expected score technique, a description of the example expected ranking unit115ofFIG. 7is now provided. Operation of the example expected ranking unit115is based on recognizing that a top-k ranking over deterministic data is achieved by determining a total ordering of the tuples, and then selecting the k highest tuples according to the ordering. Such an approach satisfies the containment and unique-ranking properties. Instead of using the expected score as the ranking metric due to its sensitivity to the score values, the example expected ranking unit115utilizes the expected rank of the tuple over the possible worlds as the metric for tuple ranking. In other words, the example expected ranking unit115operates to determine a rank for a tuple in each of the possible data set instantiations corresponding to the respective possible worlds, and then to combine the individual rankings weighted by the respective likelihoods of occurrence of the possible worlds to determine the expected rank for the tuple across all possible worlds.

Turning toFIG. 7, the expected ranking unit115of the illustrated example includes a data set instantiation unit705to determine the possible data set instantiations capable of being realized from the set of data tuples stored in, for example, the probabilistic database110and representing the uncertain data to be ranked. Using the mathematical terminology introduced above, the example data set instantiation unit705determines the possible data set instantiations corresponding to the respective possible worlds W included in the set of all possible worlds S realizable from the set of data tuples {t} stored according to an uncertainty relation D.

The example expected ranking unit115ofFIG. 7also includes a per-instantiation component ranking unit710to determine the ranks of data tuples in the possible data set instantiations determined by the example data set instantiation unit705. In particular, the example per-instantiation component ranking unit710determines a rank of a tuple tiin a possible world W as the number of other data tuples whose score is higher than the tuple ti. Accordingly, the tuple with the highest ranking according to score in the possible word W has a per-instantiation, or component, rank in W of zero (0), the tuple with the next highest ranking according to score has a per-instantiation, or component, rank in W of one (1), and so on. In other words, the determined per-instantiation, or component, rank for the tuple tiis a ranking value that, for convenience, is inversely related to the ranking of the tuple tiaccording to score such that tuples with higher rankings according to score in a particular world W have lower component rank values. Mathematically, the example per-instantiation component ranking unit710determines the per-instantiation rank in W of the tuple tiaccording to Equation 4, given by
rankW(ti)=|{tjεW|vj>vi}|.   Equation 4
For example, in the attribute-level uncertainty model, each possible world W is realized by selecting a score for each data tuple based on the tuple's score probabilities. Accordingly, the per-instantiation rank rankW(ti) of the tuple tiin the possible world W is determined by comparing the selected tuple scores in the possible world W according to Equation 4, However, in the tuple-level uncertainty model, a tuple timay not appear in one or more possible worlds. Thus, in the tuple-level uncertainty model, for a possible world W in which a particular tuple tidoes not appear, the per-instantiation rank rankW(ti) for the tuple is set to rankW(ti)=|W|, which is the number of tuples included in the possible world. Setting the per-instantiation rank of the non-existent tuple to |W| causes the non-existent tuple to be ranked lower than all the tuples that actually exist in the particular possible world W.

The example expected ranking unit115ofFIG. 7further includes an example instantiation probability determination unit715and an example expected rank combining unit720to determine expected ranks for the data tuples using the per-instantiation ranks determined by the example instantiation component ranking unit710for the possible worlds W. Mathematically, the example instantiation probability determination unit715and the example expected rank combining unit720determine an expected rank r(ti) for a particular tuple tiaccording to Equation 5, given by

r⁡(ti)=∑W∈S,ti∈W⁢⁢Pr[W]·rankW⁡(ti),Equation⁢⁢5
where Pr[W] is the instantiation probability for the possible world W and represents the likelihood of the possible world W occurring from among the set of all possible worlds S. In the illustrated example, the instantiation probability determination unit715determines the instantiation probability Pr[W] for the possible worlds W represented in Equation 5, For example, in the attribute-level uncertainty model, the instantiation probability determination unit715determines the instantiation probability Pr[W] for a possible world W by multiplying the score probabilities associated with the scores selected for each data tuple to realize the particular world W. In the tuple-level uncertainty model, the the instantiation probability determination unit715determines the instantiation probability Pr[W] for a possible world W by multiplying the probabilities of selecting those tuples existing in the particular world W with the probabilities of not selecting the tuples that are non-existent in the particular world W. The example expected rank combining unit720then combines the per-instantiation, or component, ranks rankW(ti) determined for the possible worlds W after weighting by the instantiation probabilities Pr[W] according to Equation 5, In the tuple-level uncertainty mode, the expected rank r(ti) of Equation 5 can be alternatively be determined using Equation 6, given by

r⁡(ti)=⁢∑W∈S,ti∈W⁢⁢Pr[W]·rankW⁡(ti)=∑ti∈W⁢⁢Pr[W]⁢rankW⁡(ti)+∑ti∉W⁢⁢Pr[W]·W,Equation⁢⁢6
where, as discussed above, rankW(ti) is defined to be |W| if ti∉ W.

As an illustrative example, for example attribute-level uncertainty relation500ofFIG. 5, the expected rank for tuple t2is r(t2)=0.24×1+0.16×2+0.36×0+0.24×1=0.8. Similarly, the expected rank for tuple t1is r(t1)=1.2, and the expected rank for t3is r(t3)=1. Thus, the final top-3 ranking in this example is (t2,t3,t1). As another illustrative example, for the example tuple-level uncertainty relation600ofFIG. 6, the expected rank for tuple t2is r(t2)=0.2×1+0.2×3+0.3×0+0.3×2=1.4, Note here that the tuple t2does not appear in the second and the fourth possible worlds, so its ranks in these worlds are taken to be 3 and 2, respectively. Similarly e expected rank for tuple t1is r(t1)=1.2, the expected rank for t3is r(t3)=0.9, and the expected rank for t4is r(t4)=1.9, Thus, the final top-4 ranking is (t3,t1,t2,t4).

Top-k rankings based on expected rank as determined by the example expected ranking unit115satisfy all of the desirable ranking properties of exact-k, containment, unique ranking, value invariance and stability as shown below. For simplicity, it is assumed that the expected ranks determined by the example expected ranking unit115are unique for each tuple, such that the expected ranking forms a total ordering of the tuples. In practice, expected ranking ties can be broken arbitrarily, such as by choosing the tuple having a lexicographically smaller identifier. The same tie-breaking issues also affect the ranking of deterministic data, and are not discussed further herein.

Satisfaction of the properties of exact-k, containment, unique ranking by the top-k rankings determined by the example expected ranking unit115follows immediately from the fact that expected rank is used to give a complete ordering of the data tuples. Value invariance follows by observing that changing absolute score values associated with tuples, without changing the relative scope values among tuples, will not change the rankings in possible worlds, and therefore does not change the expected ranks of the tuples.

For the stability property, it is sufficient to show that when a tuple tiis changed to ti↑as defined above, the tuple's expected rank will not increase and the expected rank of any other tuple will not decrease. To show that the top-k rankings determined by the example expected ranking unit115satisfy the stability property, let r′ be the expected rank in the uncertainty relation D′ after changing tito ti↑. It suffices to show that r(ti)≧r′(ti↑) and r(ti′)≦r′(ti′) for any i′≠i.

For the case of data tuples stored according to the attribute-level uncertainty model, it can be shown that the expected rank r(ti) of Equation 5 for a particular tuple tiis equivalent to Equation 7, which is given by

r⁡(ti)=⁢∑W∈S,ti∈W⁢⁢Pr[W]·rankW⁡(ti)=∑j≠i⁢⁢Pr⁡[Xi<Xj]Equation⁢⁢7
Then, as shown in Equation 8, after changing tito ti↑, r(ti)≧r′(ti↑):

For the case of data tuples stored according to the tuple-level uncertainty model, if ti↑has a larger score than ti, but the same probability, then r(ti)≧r′(ti↑) follows directly from Equation 6 because rankW(ti) can only get smaller while the second term of Equation 6 remains unchanged. For similar reasons, r(ti′)≦r′(ti′) for any i′≠i. If ti↑has the same score as ti, but a larger probability, rankW(ti) stays the same for any possible world W, but Pr[W] may change. The possible worlds for which ti↑has the same score as ti, but a larger probability, can be divided into three categories: (a) those containing ti; (b) those containing one of the tuples in the exclusion rule of ti(other than ti); and (c) all other possible worlds. Note that Pr[W] does not change for any W in category (b), so the focus is on categories (a) and (c). Observe that there is a one-to-one mapping between the possible worlds in category (a) and (c): W→W∪{ti}. For each such pair, its contribution to r(ti) is Pr[W]·|W|+Pr[W∪{ti}]·rankW(ti). Suppose the tuples in the exclusion rule of tiare ti,1, . . . , ti,s. Note that W and W∪{ti} differ only in the inclusion of ti, so we can write

Next, for any i′≠i, the contribution of each pair is Pr[W]·rankW(ti′)+Pr[W∪{ti}]·rankW∪{ti}(ti′). When p(ti) increases to p(ti↑), the preceding expression increases by π(p(ti)−p(ti↑))(rankW(ti′)−rankW∪{ti}(ti′))≧0, The same holds for each pair of possible worlds in categories (a) and (c). Therefore, r′(ti′)≧r(ti′). Thus, top-k rankings determined by the example expected ranking unit115for data tuples stored according to a tuple-level uncertainty model also satisfy the stability property.

Table 1 summarizes which desirable ranking properties are supported by the existing ranking techniques, the expected score technique and also the expected rank technique implemented the example expected ranking unit115ofFIG. 7.

While an example manner of implementing the expected ranking unit115ofFIG. 1has been illustrated inFIG. 7, one or more of the elements, processes and/or devices illustrated inFIG. 7may be combined, divided, re-arranged, omitted, eliminated and/or implemented in any other way. Further, the example data set instantiation unit705, the example per-instantiation component ranking unit710, the example instantiation probability determination unit715, the example expected rank combining unit720and/or, more generally, the expected ranking unit115ofFIG. 7may be implemented by hardware, software, firmware and/or any combination of hardware, software and/or firmware. Thus, for example, any of the example data set instantiation unit705, the example per-instantiation component ranking unit710, the example instantiation probability determination unit715, the example expected rank combining unit720and/or, more generally, the expected ranking unit115could be implemented by one or more circuit(s), programmable processor(s), application specific integrated circuit(s) (ASIC(s)), programmable logic device(s) (PLD(s)) and/or field programmable logic device(s) (FPLD(s)), etc. When any of the appended claims are read to cover a purely software and/or firmware implementation, at least one of the expected ranking unit115, the example data set instantiation unit705, the example per-instantiation component ranking unit710, the example instantiation probability determination unit715and/or the example expected rank combining unit720are hereby expressly defined to include a tangible medium such as a memory, digital versatile disk (DVD), compact disk (CD), etc., storing such software and/or firmware. Further still, the expected ranking unit115ofFIG. 7may include one or more elements, processes and/or devices in addition to, or instead of, those illustrated inFIG. 7, and/or may include more than one of any or all of the illustrated elements, processes and devices.

A second example implementation of the expected ranking unit115ofFIG. 1is illustrated inFIG. 8. The expected ranking unit115ofFIG. 8is tailored to take advantage of the uncertainty relation used by the probabilistic database to store and process the data tuples. In particular, the example expected ranking unit115ofFIG. 8includes an expected rank type specifier805to specify a particular processing element for use in determining the expected ranks of data tuples stored in a probabilistic database, such as the example probabilistic database110, depending upon the type of uncertainty relation employed by the probabilistic database. Furthermore, the expected rank type specifier805can be used to specify whether to invoke processing elements further tailored to support data pruning to reduce the number of data tuples that need to be accessed to determine expected ranks based on a particular specified uncertainty relation in response to top-k queries.

In the illustrated example ofFIG. 8, the expected rank type specifier805can invoke an attribute-level exact expected ranking unit810to determine exact expected ranks in conjunction with probabilistic databases employing an attribute-level uncertainty relation that associates sets of scores and respective score probabilities with each data tuple and then realizes a possible data set instantiation by selecting a score for each data tuple according to its score probability. The expected rank type specifier805can also invoke an attribute-level pruned expected ranking unit815to determine expected ranks in conjunction with probabilistic databases employing the attribute-level uncertainty relation, with pruning techniques being used to potentially reduce the number of tuples that need to be accessed. The expected rank type specifier805can further invoke a tuple-level exact expected ranking unit820to determine exact expected ranks in conjunction with probabilistic databases employing a tuple-level uncertainty relation that associate each data tuple with a score and a score probability and then realizes a possible data set instantiation by determining whether to include each data tuple in the data set instantiation based on its score probability and a set of exclusion rules. The expected rank type specifier805can also invoke a tuple-level pruned expected ranking unit825to determine expected ranks in conjunction with probabilistic databases employing the tuple-level uncertainty relation, with pruning techniques being used to potentially reduce the number of tuples that need to be accessed. Example implementations of the attribute-level exact expected ranking unit810, the attribute-level pruned expected ranking unit815, the tuple-level exact expected ranking unit820and the tuple-level pruned expected ranking unit825are illustrated inFIGS. 9-12and discussed in greater detail below.

While an example manner of implementing the expected ranking unit115ofFIG. 1has been illustrated inFIG. 8, one or more of the elements, processes and/or devices illustrated inFIG. 8may be combined, divided, re-arranged, omitted, eliminated and/or implemented in any other way. Further, the example expected rank type specifier805, the example attribute-level exact expected ranking unit810, the example attribute-level pruned expected ranking unit815, the example tuple-level exact expected ranking unit820, the example tuple-level pruned expected ranking unit825and/or, more generally, the expected ranking unit115ofFIG. 8may be implemented by hardware, software, firmware and/or any combination of hardware, software and/or firmware. Thus, for example, any of the example expected rank type specifier805, the example attribute-level exact expected ranking unit810, the example attribute-level pruned expected ranking unit815, the example tuple-level exact expected ranking unit820, the example tuple-level pruned expected ranking unit825and/or, more generally, the expected ranking unit115could be implemented by one or more circuit(s), programmable processor(s), application specific integrated circuit(s) (ASIC(s)), programmable logic device(s) (PLD(s)) and/or field programmable logic device(s) (FPLD(s)), etc. When any of the appended claims are read to cover a purely software and/or firmware implementation, at least one of the expected ranking unit115, the example expected rank type specifier805, the example attribute-level exact expected ranking unit810, the example attribute-level pruned expected ranking unit815, the example tuple-level exact expected ranking unit820and/or the example tuple-level pruned expected ranking unit825are hereby expressly defined to include a tangible medium such as a memory, digital versatile disk (DVD), compact disk (CD), etc., storing such software and/or firmware. Further still, the expected ranking unit115ofFIG. 8may include one or more elements, processes and/or devices in addition to, or instead of, those illustrated inFIG. 8, and/or may include more than one of any or all of the illustrated elements, processes and devices.

An example implementation of the attribute-level exact expected ranking unit810that may be used to implement the example expected ranking unit115ofFIG. 8is illustrated inFIG. 9. The example attribute-level exact expected ranking unit810implements an efficient technique for calculating the expected rank of data tuples in an uncertainty relation D storing N tuples according the attribute-level uncertain model. As discussed below, the example attribute-level exact expected ranking unit810determines exact expected ranks of all tuples in D with an O(N log N) processing cost. A technique for determining approximate expected ranks but that can terminate the search without accessing all tuples as soon as the top-k tuples with the k smallest expected ranks are found is discussed below in conjunction withFIG. 10.

The efficient expected ranking technique implemented by the example attribute-level exact expected ranking unit810is derived from the brute force technique of Equation 5 as implemented by the example expected ranking unit115ofFIG. 7. The brute-force approach of Equation 5 as implemented by the example expected ranking unit115ofFIG. 7requires O(N) operations to compute the expected rank r(ti) for one tuple and O(N2) operations to compute the ranks of all tuples. This quadratic dependence on N can be prohibitive when N is large. However, the efficient expected ranking technique implemented by the example attribute-level exact expected ranking unit810requires only O(N log N) operations and is derived from the brute force approach of Equation 5 as follows.

As discussed above, for the case of data tuples stored according to the attribute-level uncertainty model, it can be shown that the expected rank r(ti) of Equation 5 for a particular tuple tiis equivalent to Equation 10, which is given by

r⁡(ti)=∑i≠j⁢⁢Pr⁡[Xj>Xi].Equation⁢⁢10
where, as described above, Xiis a random variable denoting the score of a tuple ti. Equation 10 can be rewritten as

r⁡(ti)=⁢∑i≠j⁢⁢∑l=1si⁢⁢pi,ℓ⁢Pr⁡[Xj>vi,l]=∑l=1si⁢⁢pi,ℓ⁢∑j≠i⁢⁢Pr⁡[Xj>vi,l]=⁢∑l=1si⁢⁢pi,l(∑j⁢⁢Pr⁡[Xj>vi,l]-Pr⁡[Xi>vi,l])=⁢∑l=1si⁢⁢pi,l⁡(q⁡(vi,l)-Pr⁡[Xi>vi,l])Equation⁢⁢11
where q(v) is defined to be

q⁡(v)=∑j⁢Pr⁡[Xj>v].
In other words, q(v) for a particular score v represents a sum of comparison probabilities Pr[Xj>v], with each comparison probability Pr[Xj>v] representing how likely the respective score v is exceeded by the data tuple tjhaving the respective score random variable Xj. Referring toFIG. 3, the comparison probability Pr[Xj>v] for the data tuple tjcan be determined by summing the data tuple's score probabilities pj,lthat are associated with scores vj,lof the data tuple tjthat are greater than the particular score v.

Let U be the universe of all possible score values of the score random variables Xi, i=1, . . . , N. Because each pdf associated with the random variables Xihas constant size bounded by s (seeFIG. 3), the number of all possible score values is bounded by |U|≦|sN|. When s is a constant, this bound becomes |U|=O(N). After sorting the combined set of scores, U, associated with all data tuples, which has a cost of O(N log N), the sum of comparison probabilities, q(v), can be precomputed for all vεU with a linear pass over the sorted combined score set U. In the illustrated example ofFIG. 9, the attribute-level exact expected ranking unit810includes an example score sorting unit905to sort the combined set of scores, U, that includes all possible scores of all data tuples. The example attribute-level exact expected ranking unit810also includes an example comparison probability determination unit910to determine the comparison probability Pr[Xj>v] for each score v in the sorted combined score set U and each data tuple tjthat represents how likely the respective score v is exceeded by the data tuple tj. The example attribute-level exact expected ranking unit810further includes an example comparison probability summation unit915to determine the sum of comparison probabilities,

q⁡(v)=∑j⁢Pr⁡[Xj>v],
for each score v in the sorted combined score set U.

Exact computation of the expected rank for each data tuple can be performed using Equation 11 in constant time given q(v) for all vεU. Accordingly, the attribute-level exact expected ranking unit810ofFIG. 9includes a summed comparison probability combination unit920to implement Equation 11, In particular, the example summed comparison probability combination unit920determines the expected rank r(ti) for the data tuple tiby combining the summed comparison probabilities q(v) corresponding to only the set of scores vi,lassociated with the data tuple ti, where the summed comparison probabilities q(vi,l) for a particular score vi,lis weighted by the corresponding score probability pi,laccording to Equation 11, To support a top-k query, the summed comparison probability combination unit920of the illustrated example also maintains a priority queue of size k that dynamically stores the k tuples with smallest expected ranks. When all tuples have been processed, the contents of the size k priority queue are returned as the response to the top-k query.

The processing cost exhibited by the example attribute-level exact expected ranking unit810ofFIG. 9is determined as follows. Computing q(v) takes O(N log N) operations. Determining expected ranks of all tuples while maintaining the priority queue takes O(N log k) operations. Thus, the overall cost of this approach is O(N log N) operations. For brevity, in the discussions that follow the expected ranking technique implemented by the example attribute-level exact expected ranking unit810ofFIG. 9is referred to as “A-ERank” and a pseudocode summary of the A-ERank technique is provided in Table 2.

TABLE 2A-ERank Expected Ranking Technique1Create U containing values from t1.X1,...,tN.XN, in order;2Compute q(v) for all v ∈ U by one pass over U ;3Initialize a priority queue A sorted by expected rank;4for i = 1,...,N do4aCompute r(ti) using q(v)'s and Xiusing Equation 114bInsert (ti,r(ti)) into A;4cif | A |> k then Drop element with largest expected rankfrom A5return A;

While an example manner of implementing the example attribute-level exact expected ranking unit810ofFIG. 8has been illustrated inFIG. 9, one or more of the elements, processes and/or devices illustrated inFIG. 9may be combined, divided, re-arranged, omitted, eliminated and/or implemented in any other way. Further, the example score sorting unit905, the example comparison probability determination unit910, the example comparison probability summation unit915, the example summed comparison probability combination unit920and/or, more generally, the example attribute-level exact expected ranking unit810ofFIG. 9may be implemented by hardware, software, firmware and/or any combination of hardware, software and/or firmware. Thus, for example, any of the example score sorting unit905, the example comparison probability determination unit910, the example comparison probability summation unit915, the example summed comparison probability combination unit920and/or, more generally, the example attribute-level exact expected ranking unit810could be implemented by one or more circuit(s), programmable processor(s), application specific integrated circuit(s) (ASIC(s)), programmable logic device(s) (PLD(s)) and/or field programmable logic device(s) (FPLD(s)), etc. When any of the appended claims are read to cover a purely software and/or firmware implementation, at least one of the example attribute-level exact expected ranking unit810, the example score sorting unit905, the example comparison probability determination unit910, the example comparison probability summation unit915and/or the example summed comparison probability combination unit920are hereby expressly defined to include a tangible medium such as a memory, digital versatile disk (DVD), compact disk (CD), etc., storing such software and/or firmware. Further still, the example attribute-level exact expected ranking unit810ofFIG. 9may include one or more elements, processes and/or devices in addition to, or instead of, those illustrated inFIG. 9, and/or may include more than one of any or all of the illustrated elements, processes and devices.

An example implementation of the attribute-level pruned expected ranking unit815that may be used to implement the example expected ranking unit115ofFIG. 8is illustrated inFIG. 10. The A-ERank expected ranking technique implemented by the example attribute-level exact expected ranking unit810ofFIG. 9is efficient even for large numbers of data tuples, N. However, in certain scenarios accessing a tuple is considerably expensive, such as where accessing tuples requires significant input/output (I/O) resources. In those scenarios, it may be desirable to reduce the number of tuples that need to be accessed to find answer a top-k ranking query. The example attribute-level pruned expected ranking unit815ofFIG. 10is able to reduce the number of tuples that need to be accessed to find a set of k or more tuples guaranteed to include the tuples having the actual top-k expected ranks. The example attribute-level pruned expected ranking unit815achieves this reduction in number of tuples accessed by employing pruning based on tail bounds of the score distribution.

In particular, if the data tuples tuples are sorted in decreasing order of their expected scores, E[Xi], the example attribute-level pruned expected ranking unit815can terminate the search for the top-k tuples early before determining the expected ranks for all tuples. Accordingly, the example attribute-level pruned expected ranking unit815ofFIG. 10includes an expected score sorting unit1005to sort the expected scores, E[Xi], determined by an expected score determination unit1010for each data tuple ti. In the illustrated example, the expected score determination unit1010determines the expected score E[Xi] by summing the possible scores vi,lfor the data tuple ti, with each score weighted by the respective score probability pi,l(seeFIG. 3). Alternatively, if the scores and score probabilities are modeled as a continuous pdf (instead of the discrete values vi,land pi,l), the expected score E[Xi] can be determined by computing the expected value of the continuous pdf. The example expected score sorting unit1005sorts expected scores for the data tuples in decreasing order such that, if i<j , then E[Xi]≧E[Xj] for all 1≦i,j≦N. The example attribute-level pruned expected ranking unit815ofFIG. 10also includes a sorted tuple selection unit1015that implements an interface which selects and provides data tuples in decreasing order of expected rank E[Xi]. The example attribute-level pruned expected ranking unit815scans the data tuples in decreasing order of expected rank E[Xi] using the example sorted tuple selection unit1015and maintains an upper bound on the expected rank r(ti) for each data tuple tiselected so far, with the upper bound denoted r+(ti). The example attribute-level pruned expected ranking unit815also maintains a lower bound on r(tu) for any unseen tuple tu, with the lower bound denoted r−. In the illustrated example, the example attribute-level pruned expected ranking unit815stops selecting data tuples for determining a top-k ranking when there are at least k selected data tuples having upper bound r+(Xi)'s that are smaller than the current lower bound r−.

The example attribute-level pruned expected ranking unit815ofFIG. 10includes an upper bound determination unit1020to determine an upper bound r+(ti) on the expected rank r(ti) for each selected data tuple tias follows. Suppose n tuples t1, . . . ,tnhave been selected by the example sorted tuple selection unit1015. From Equation 10, the expected rank r(ti) of the selected data tuple ti, ∀iε[1,n], is given by Equation 12, which is:

r⁡(ti)=⁢∑j≤n,j≠i⁢⁢Pr⁡[Xj>Xi]+∑n<j≤N⁢⁢Pr⁡[Xj>Xi]=⁢∑j≤n,j≠i⁢⁢Pr⁡[Xj>Xi]+∑n<j≤N⁢∑l=1si⁢⁢pi,l⁢Pr⁡[Xj>vi,l]≤⁢∑j≤n,j≠i⁢⁢Pr⁡[Xj>Xi]+∑n<j≤N⁢∑l=1si⁢⁢pi,l⁢E⁡[Xj]vi,lEquation⁢⁢12
The last line of Equation 12 results from the Markov inequality, and can be further bounded by Equation 13, which is:

The example attribute-level pruned expected ranking unit815ofFIG. 10includes a lower bound determination unit1025to maintain the lower bound r−on the expected rank r(tu) for all unselected tuples tuas follows. Suppose n tuples t1, . . . ,tnhave been selected by the example sorted tuple selection unit1015. For any unselected tuple tu, u>n, the expected rank r(tu) of the unselected data tuple tuis given by Equation 14, which is:

r⁡(tu)≥∑j≤n⁢⁢Pr⁡[Xj>Xu]=n-∑j≤n⁢⁢Pr⁡[Xu≥Xj]=n-∑j≤n⁢⁢∑l=1sj⁢⁢pj,l⁢Pr⁡[Xu>vj,l].Equation⁢⁢14
Using the Markov inequality on the last term of Equation 14, the expected rank r(tu) of the unselected data tuple tucan be further bounded by Equation 15, given by:

r⁢(tu)≥n-∑j≤n⁢⁢∑l=1sj⁢⁢pj,l⁢E⁡[Xn]vj,l=r-.Equation⁢⁢15
Thus, the example lower bound determination unit1025implements Equation 15 to determine the lower bound r−on the expected rank r(tu) for all unselected tuples tu. In particular, the first term in Equation 15 is the size n of the subset of tuples currently selected. The second term in Equation 15 can be computed using the expected score E[Xn] for the most recently selected tuple tn(which is the smallest expected score from among all the selected data tuples because the tuples are selected in decreasing order of expected score), and the possible scores vi,land respective score probabilities pi,lfor the data tuples ticurrently selected. Thus, the example lower bound determination unit1025uses Equation 15 to maintain a lower bound r−on the expected rank r(tu) for all unselected tuples tuusing only the selected data tuples ti, i=1, . . . ,n, with the lower bound r−being updated for every newly scanned tuple tn.

To process a top-k query, the example attribute-level pruned expected ranking unit815ofFIG. 10uses the upper bounds r+(ti) on the expected ranks for all tuples t1, . . . ,tndetermined by the upper bound determination unit1020and the lower bound r−on the expected ranks of all unselected tuples determined by the lower bound determination unit1025to determine a subset of data tuples tithat must include the top-k tuples. In particular, for each new tuple tnselected in decreasing order of expected score, the upper bound determination unit1020and the lower bound determination unit1025update the upper bounds r+(ti) and the lower bound r−. The example attribute-level pruned expected ranking unit815then finds the k th largest upper bound r+(ti) value, and compares this to the lower bound r. If the k th largest upper bound is less than the lower bound, then the example attribute-level pruned expected ranking unit815determines that the top-k tuples having smallest expected ranks across all the data tuples are among the first n selected tuples and, thus, the example attribute-level pruned expected ranking unit815can stop selecting additional tuples for processing. Otherwise, the example attribute-level pruned expected ranking unit815uses the sorted tuple selection unit1015to select the next next tuple in decreasing order of expected score. For brevity, in the discussions that follow the expected ranking technique implemented by the example attribute-level pruned expected ranking unit815ofFIG. 10is referred to as“A-ERank-Prune.”

A remaining challenge is how to find the particular k tuples having the smallest expected ranks among the n selected tuples using only the n selected tuples. It is not possible to obtain a precise order of actual expected ranks of the n selected tuples without inspecting all N data tuples in the uncertainty relation D. Instead, the example attribute-level pruned expected ranking unit815determines approximate expected ranks for the only the n selected tuples using a curtailed database D′={t1, . . . ,tn} implemented by a curtailed dataset determination unit1030. The example curtailed dataset determination unit1030prunes the original uncertainty relation D to include only the n selected tuples of the N data tuples in the uncertainty relation D, but not any of the unselected tuples. The example attribute-level pruned expected ranking unit815further includes an implementation of the example attribute-level exact expected ranking unit810ofFIGS. 8or9to determine the expected rank r′(ti) for every tuple ti, iε[1,n], in the curtailed database D′. The expected rank r′(ti) determined using only the n selected tuples in the curtailed data set can be an accurate approximation of the actual r(ti) that would require all N data tuples.

The processing cost exhibited by the A-ERrank-Prune technique implemented by the example attribute-level pruned expected ranking unit815ofFIG. 10is determined as follows. After selecting the next data tuple tn, the bounds in both Equation 13 and Equation 15 can be updated in constant time by retaining

∑l=1sj⁢⁢pi,lvi,l
for each seen tuple. Updating the first term in Equation 13 for all i≦n requires linear time for adding Pr[Xn>Xi] to the already computed

∑j≤n-1,j≠i⁢Pr⁡[Xj>Xi]
for all selected tuples as well as computing

∑i≤n-1⁢Pr⁡[Xi>Xn]).
This results in a total of O(n2) operations for the A-ERrank-Prune technique. Using a similar approach in the A-ERank technique implemented by the example attribute-level exact expected ranking unit810ofFIG. 9, the A-ERank technique could utilize the value universe U′ of only the selected tuples and maintain prefix sums of the q(v) values, which would drive down the cost of this technique to O(n log n) operations.

While an example manner of implementing the attribute-level pruned expected ranking unit815ofFIG. 8has been illustrated inFIG. 10, one or more of the elements, processes and/or devices illustrated inFIG. 10may be combined, divided, re-arranged, omitted, eliminated and/or implemented in any other way. Further, the example expected score sorting unit1005, the example expected score determination unit1010, the example sorted tuple selection unit1015, the example upper bound determination unit1020, the example lower bound determination unit1025, the example curtailed dataset determination unit1030, the example attribute-level exact expected ranking unit810and/or, more generally, the example attribute-level pruned expected ranking unit815ofFIG. 10may be implemented by hardware, software, firmware and/or any combination of hardware, software and/or firmware. Thus, for example, any of the example expected score sorting unit1005, the example expected score determination unit1010, the example sorted tuple selection unit1015, the example upper bound determination unit1020, the example lower bound determination unit1025, the example curtailed dataset determination unit1030, the example attribute-level exact expected ranking unit810and/or, more generally, the example attribute-level pruned expected ranking unit815could be implemented by one or more circuit(s), programmable processor(s), application specific integrated circuit(s) (ASIC(s)), programmable logic device(s) (PLD(s)) and/or field programmable logic device(s) (FPLD(s)), etc. When any of the appended claims are read to cover a purely software and/or firmware implementation, at least one of the example attribute-level pruned expected ranking unit815, the example expected score sorting unit1005, the example expected score determination unit1010, the example sorted tuple selection unit1015, the example upper bound determination unit1020, the example lower bound determination unit1025, the example curtailed dataset determination unit1030and/or the example attribute-level exact expected ranking unit810are hereby expressly defined to include a tangible medium such as a memory, digital versatile disk (DVD), compact disk (CD), etc., storing such software and/or firmware. Further still, the example attribute-level pruned expected ranking unit815ofFIG. 10may include one or more elements, processes and/or devices in addition to, or instead of, those illustrated inFIG. 10, and/or may include more than one of any or all of the illustrated elements, processes and devices.

An example implementation of the tuple-level exact expected ranking unit820that may be used to implement the example expected ranking unit115ofFIG. 8is illustrated inFIG. 11. The example tuple-level exact expected ranking unit820implements an efficient technique for calculating the expected rank of an uncertainty relation D for storing N tuples according the tuple-level uncertain model. For a tuple-level uncertainty relation D with N tuples and M exclusion rules (see e.g.FIG. 4), the example tuple-level exact expected ranking unit820determines the k tuples with the smallest expected ranks in response to a top-k query. Recall that each exclusion rule τjis a set of tuples, where the score probabilities for the tuples included in the exclusion rule sum to a value not exceeding 1

(e.g.,∑ti∈τj⁢p⁡(ti)≤1).
Without loss of generality, in the following description it is assumed that an example tuple sorting unit1105sorts the tuples t1, . . . ,tnby their score attribute and t1is, therefore, the tuple with the highest score. Additionally, the notation ti⋄tjis used to indicate that the tuples tiand tjare in the same exclusion rule and that they are different from each other (e.g., ti≠tj). Furthermore, the notation ti⋄tjis used to indicate that the tuples tiand tjare not in the same exclusion rule. As discussed below, the example tuple-level exact expected ranking unit820determines exact expected ranks of all tuples in D with a O(N log N) processing cost that accesses every tuple. A technique for determining the expected ranks that accesses only the first n tuples and that has a processing cost of O(n log n) operations is discussed below in conjunction withFIG. 12. This latter technique is based on an assumption that an expected number of tuples included in the possible data instantiations of the tuple-level uncertainty relation D is known, as described below.

The efficient expected ranking technique implemented by the example tuple-level exact expected ranking unit820is derived from the brute force approach of Equation 5 as follows. Assuming that the data tuples tiare sorted according to their respective score attributes vi, the expected rank r(ti) of Equation 5, which is equivalent to Equation 6 for the tuple-level uncertainty model, becomes Equation 16, given by:

r⁡(ti)=p⁡(ti).∑tj⁢◇_⁢ti,j<i⁢⁢p⁡(tj)+(1-p⁡(ti)).(∑tj⁢◇ti⁢p⁡(tj)⁢1-p⁡(ti)+∑tj⁢◇_⁢ti⁢p⁡(tj))Equation⁢⁢16
The first term in Equation 16 computes the portion of tuple ti's expected rank for possible data set instantiations corresponding to random worlds W in which the tuple tiappears. The second term in Equation 16 computes the expected size (e.g., the number of data tuples in the possible data set instantiation) of a random world W in which tidoes not appear in W. In particular, the term

∑tj⁢◇ti⁢p⁡(tj)⁢1-p⁡(ti)
is the expected number of appearing tuples in the same rule as ti, conditioned on tinot appearing, while the term

∑tj⁢◇_⁢ti⁢p⁡(tj)
accounts for the rest of the tuples.

qi=∑j<i⁢p⁡(tj)
be the sum of the score probabilities p(tj) for all data tuples tjordered (e.g., by the example tuple sorting unit1105) before the data tuple tiin decreasing order of score. The example tuple-level exact expected ranking unit820includes a score probability summation unit1110to determine the score probability summation qifor all tuples tiin O(N) operations. The example tuple-level exact expected ranking unit820also includes an expected instantiation size determination unit1115to sum the respective score probabilities associated with all data tuples to determine the quantity

E⁡[W]=∑j=1N⁢⁢p⁡(tj),
which is the expected number of tuples averaged over all possible worlds S (which is also referred to as the expected data set instantiation size over all possible worlds S). Using the score probability summation qidetermined by the example score probability summation unit1110and the expected number of tuples E[|W|] determined by the example expected instantiation size determination unit1115, Equation 17 can be rewritten as Equation 18, given by:

Referring to Equation 18, the example tuple-level exact expected ranking unit820includes an exclusion rule evaluation unit1120to determine the first auxiliary information term

∑tj⁢◇⁢_⁢ti,j<i⁢p⁡(tj),
which is the sum of probabilities of tuples tjin the same rule as tithat have score values higher than ti, and the second auxiliary information term

∑tj⁢⁢◇⁢⁢ti⁢p⁡(tj),
which is the sum of probabilities of tuples tjthat are in the same rule as ti, for each tuple tiin the tuple-level uncertainty relation D. The example tuple-level exact expected ranking unit820further includes a score probability combination unit1125to determine the expected rank r(ti) for tuple tiin O(1) operations by combining the auxiliary terms determined by the exclusion rule evaluation unit1120with the score probability summation qidetermined by the example score probability summation unit1110and the expected number of tuples E[|W|] determined by the example expected instantiation size determination unit1115according to Equation 18, Additionally, to support a top-k query, the score probability combination unit1125of the illustrated example maintains a priority queue of size k that keeps the k tuples with the smallest expected ranks r(ti), thereby allowing selection of the top-k tuples in O(N log k) operations. Note that both auxiliary terms

∑tj⁢◇⁢⁢ti,j<i⁢p⁡(tj)⁢⁢and⁢⁢∑tj⁢◇⁢⁢ti⁢p⁡(tj)
can be calculated inexpensively by initially accessing all the exclusion rules in a single scan of the uncertainty relation D in O(N) operations. However, when the tuples tiin D are not presorted by score attribute, the processing cost exhibited by the example tuple-level exact expected ranking unit820is dominated by the sorting performed by the example tuple sorting unit1105, which requires O(N log N) operations.

For brevity, in the discussions that follow the expected ranking technique implemented by the example tuple-level exact expected ranking unit820ofFIG. 11is referred to as “T-ERrank” and a pseudocode summary of the T-ERrank technique is provided in Table 3

TABLE 3T-ERrank Expected Ranking Technique1Sort D by score attribute such that if ti.vi≧tj.vj, then i ≦ jfor all i, j ∈ [1, N];2Compute qifor all i ∈ [1, N] and E[|W |] by one pass over D;3Initialize a priority queue A sorted by expected rank;4for i = 1,...,N do4aCompute r(ti) using Equation 18;4bif | A |> k then drop the element with largest expected rankfrom A;5return A;

While an example manner of implementing the example tuple-level exact expected ranking unit820ofFIG. 8has been illustrated inFIG. 11, one or more of the elements, processes and/or devices illustrated inFIG. 11may be combined, divided, re-arranged, omitted, eliminated and/or implemented in any other way. Further, the example tuple sorting unit1105, the example score probability summation unit1110, the example expected instantiation size determination unit1115, the example exclusion rule evaluation unit1120, the example score probability combination unit1125and/or, more generally, the example tuple-level exact expected ranking unit820ofFIG. 11may be implemented by hardware, software, firmware and/or any combination of hardware, software and/or firmware. Thus, for example, any of the example tuple sorting unit1105, the example score probability summation unit1110, the example expected instantiation size determination unit1115, the example exclusion rule evaluation unit1120, the example score probability combination unit1125and/or, more generally, the example tuple-level exact expected ranking unit820could be implemented by one or more circuit(s), programmable processor(s), application specific integrated circuit(s) (ASIC(s)), programmable logic device(s) (PLD(s)) and/or field programmable logic device(s) (FPLD(s)), etc. When any of the appended claims are read to cover a purely software and/or firmware implementation, at least one of the example tuple-level exact expected ranking unit820, the example tuple sorting unit1105, the example score probability summation unit1110, the example expected instantiation size determination unit1115, the example exclusion rule evaluation unit1120and/or the example score probability combination unit1125are hereby expressly defined to include a tangible medium such as a memory, digital versatile disk (DVD), compact disk (CD), etc., storing such software and/or firmware. Further still, the example tuple-level exact expected ranking unit820ofFIG. 11may include one or more elements, processes and/or devices in addition to, or instead of, those illustrated inFIG. 11, and/or may include more than one of any or all of the illustrated elements, processes and devices.

An example implementation of the tuple-level pruned expected ranking unit825that may be used to implement the example expected ranking unit115ofFIG. 8is illustrated inFIG. 12. Provided that the expected number of tuples E[|W|] is known, the example tuple-level pruned expected ranking unit825ofFIG. 12can answer top-k queries efficiently using pruning techniques without accessing all tuples. For example, E[|W|] can be known and efficiently maintained in O(1) operations when the tuple-level uncertainty relation D is updated by the deletion or insertion of tuples. Because E[|W|] is simply the sum of the score probabilities for all tuples included in the tuple-level uncertainty relation D, and does not depend on the exclusion rules, it is reasonable to assume that E[|W|] is always available. Additionally, in the illustrated example ofFIG. 12, it is assumed that the tuple-level uncertainty relation D stores tuples in decreasing order of their score attributes (e.g., from the highest to the lowest). If the tuple-level uncertainty relation D does not store tuples in decreasing order of score, the tuple-level pruned expected ranking unit825ofFIG. 12can be adapted to include the example tuple sorting unit1105ofFIG. 11to perform such sorting.

Turning toFIG. 12, the example tuple-level pruned expected ranking unit825includes the example score probability summation unit1110, the example exclusion rule evaluation unit1120and the example score probability combination unit1125to determine the expected ranks r(ti) for tuples tiaccording to Equation 18 as described above. (The example tuple-level pruned expected ranking unit825does not include the example expected instantiation size determination unit1115ofFIG. 11because the expected number of tuples E[|W|] is assumed to be known. However, the example expected instantiation size determination unit1115could be included in the example ofFIG. 12if determination of the expected number of tuples E[|W|] is required). The example tuple-level pruned expected ranking unit825ofFIG. 12also includes a sorted tuple selection unit1205to select tuples tiin decreasing order or score. After selecting tn, the example tuple-level pruned expected ranking unit825further uses the score probability combination unit1125to determine the expected rank r(tn) for tuple tnin O(1) operations by combining the auxiliary terms determined by the exclusion rule evaluation unit1120with the score probability summation qndetermined by the example score probability summation unit1110and the expected number of tuples E[|W|] (assumed to be available) according to Equation 18, The example score probability combination unit1125also maintains r(k), the k-th smallest expected rank r(ti) among all the tuples currently selected by the example sorted tuple selection unit1205. Maintaining the k-th smallest expected rank r(k)can be performed with a priority queue in O(log k) operations per tuple.

The example tuple-level pruned expected ranking unit825ofFIG. 12further includes a lower bound determination unit1210to determine a lower bound on the expected ranks r(tl) for all unselected tuples tl, l>n. The lower bound on r(tl) is derived as follows. Beginning with Equation 17, the expression for the lower bound r(tl) can be rewritten to be Equation 19, which is:

r⁡(ti)=⁢p⁡(ti)·∑tj⁢◇_⁢ti,j<i⁢⁢p⁡(tj)+∑tj⁢◇⁢⁢ti⁢p⁡(tj)+(1-p⁡(ti))·∑tj⁢◇_⁢ti⁢p⁡(tj)=⁢p⁡(tl)·∑tj⁢◇_⁢tl,j<l⁢⁢p⁡(tj)+E⁡[W]-p⁡(tl)-p⁡(tl)·∑tj⁢◇_⁢tl⁢⁢p⁡(tj)=⁢E⁡[W]-p⁡(tl)-p⁡(tl)·(∑tj⁢◇_⁢tl⁢⁢p⁡(tj)⁢-∑tj⁢◇_⁢tl,j<l⁢⁢p⁡(tj))=⁢E⁡[W]-p⁡(tl)-p⁡(tl)·∑tj⁢◇_⁢tl,j<ℓ⁢⁢p⁡(tj).Equation⁢⁢19
The fact that

∑tj⁢◇⁢⁢tl⁢p⁡(tj)+∑tj⁢◇_⁢tl⁢p⁡(tj)=E⁡[W]-p⁡(tl)
was used to obtain the second line from the first line in Equation 19, As defined above,

ql=∑j<l⁢p⁡(tj)
is the sum of the score probabilities p(tj) for all data tuples tjordered before the data tuple tl. It can be shown that:

E⁡[W]-ql=∑j>ℓ⁢⁢p⁡(tj)+p⁡(tl)≥∑tj⁢◇_⁢tl,j<l⁢⁢p⁡(tj).Equation⁢⁢20
Substituting Equation 20 into Equation 19 yields the following lower bound on r(tl):

r⁡(tl)≥⁢E⁡[W]-p⁡(tl)-p⁡(tl)·(E⁡[W]-ql)≥ql-1≥qn-1.Equation⁢⁢21
The last line of Equation 21 is uses the monotonicity of qi(e.g., qn≦qlif n≦l) which results from the data tuples being scanned in order. The last line of Equation 21 is the lower bound on r(tl) determined by the example lower bound determination unit1210.

Thus, when r(k)≦qn−1, there are at least k tuples among the first selected n tuples with expected ranks smaller than all unseen tuples. Accordingly, the example tuple-level pruned expected ranking unit825ofFIG. 12includes an expected rank selection unit1215to determine when r(k)≦qn−1 and then stops the selection of subsequent tuples by the example sorted tuple selection unit1205. Additionally, because the expected ranks are calculated by the example tuple-level pruned expected ranking unit825for all the selected tuples, the expected rank selection unit1215can simply select the top-k ranked tuples from among the n selected tuples in response to a top-k query. The processing cost exhibited by the example tuple-level pruned expected ranking unit825ofFIG. 12is O(n log k) where n is potentially much smaller than N. For brevity, in the discussions that follow the expected ranking technique implemented by the example tuple-level pruned expected ranking unit825ofFIG. 12is referred to as “T-ERrank-Prune.”

While an example manner of implementing the example tuple-level pruned expected ranking unit825ofFIG. 8has been illustrated inFIG. 12, one or more of the elements, processes and/or devices illustrated inFIG. 12may be combined, divided, re-arranged, omitted, eliminated and/or implemented in any other way. Further, the example score probability summation unit1110, the example exclusion rule evaluation unit1120, the example score probability combination unit1125, the example sorted tuple selection unit1205, the example lower bound determination unit1210, the example expected rank selection unit1215and/or, more generally, the example tuple-level pruned expected ranking unit825ofFIG. 12may be implemented by hardware, software, firmware and/or any combination of hardware, software and/or firmware. Thus, for example, any of t the example score probability summation unit1110, the example exclusion rule evaluation unit1120, the example score probability combination unit1125, the example sorted tuple selection unit1205, the example lower bound determination unit1210, the example expected rank selection unit1215and/or, more generally, the example tuple-level pruned expected ranking unit825could be implemented by one or more circuit(s), programmable processor(s), application specific integrated circuit(s) (ASIC(s)), programmable logic device(s) (PLD(s)) and/or field programmable logic device(s) (FPLD(s)), etc. When any of the appended claims are read to cover a purely software and/or firmware implementation, at least one of the example tuple-level pruned expected ranking unit825, the example score probability summation unit1110, the example exclusion rule evaluation unit1120, the example score probability combination unit1125, the example sorted tuple selection unit1205, the example lower bound determination unit1210and/or the example expected rank selection unit1215are hereby expressly defined to include a tangible medium such as a memory, digital versatile disk (DVD), compact disk (CD), etc., storing such software and/or firmware. Further still, the example tuple-level pruned expected ranking unit825ofFIG. 12may include one or more elements, processes and/or devices in addition to, or instead of, those illustrated inFIG. 12, and/or may include more than one of any or all of the illustrated elements, processes and devices.

Flowcharts representative of example machine readable instructions that may be executed to implement the example probabilistic database server105, the example probabilistic database110, the example expected ranking unit115, the example data interface135, the example query interface145, the example score computation unit150, the example score probability computation unit155, the example data tuple storage205, the example instantiation unit210, the example data set instantiation unit705, the example per-instantiation component ranking unit710, the example instantiation probability determination unit715, the example expected rank combining unit720, the example expected rank type specifier805, the example attribute-level exact expected ranking unit810, the example attribute-level pruned expected ranking unit815, the example tuple-level exact expected ranking unit820, the example tuple-level pruned expected ranking unit825, the example score sorting unit905, the example comparison probability determination unit910, the example comparison probability summation unit915, the example summed comparison probability combination unit920, the example expected score sorting unit1005, the example expected score determination unit1010, the example sorted tuple selection unit1015, the example upper bound determination unit1020, the example lower bound determination unit1025, the example curtailed dataset determination unit1030, the example tuple sorting unit1105, the example score probability summation unit1110, the example expected instantiation size determination unit1115, the example exclusion rule evaluation unit1120, the example score probability combination unit1125, the example sorted tuple selection unit1205, the example lower bound determination unit1210and/or the example expected rank selection unit1215are shown inFIGS. 13-18. In these examples, the machine readable instructions represented by each flowchart may comprise one or more programs for execution by: (a) a processor, such as the processor2612shown in the example computer2600discussed below in connection withFIG. 26, (b) a controller, and/or (c) any other suitable device. The one or more programs may be embodied in software stored on a tangible medium such as, for example, a flash memory, a CD-ROM, a floppy disk, a hard drive, a DVD, or a memory associated with the processor2612, but the entire program or programs and/or portions thereof could alternatively be executed by a device other than the processor2612and/or embodied in firmware or dedicated hardware (e.g., implemented by an application specific integrated circuit (ASIC), a programmable logic device (PLD), a field programmable logic device (FPLD), discrete logic, etc.). For example, any or all of the example probabilistic database server105, the example probabilistic database110, the example expected ranking unit115, the example data interface135, the example query interface145, the example score computation unit150, the example score probability computation unit155, the example data tuple storage205, the example instantiation unit210, the example data set instantiation unit705, the example per-instantiation component ranking unit710, the example instantiation probability determination unit715, the example expected rank combining unit720, the example expected rank type specifier805, the example attribute-level exact expected ranking unit810, the example attribute-level pruned expected ranking unit815, the example tuple-level exact expected ranking unit820, the example tuple-level pruned expected ranking unit825, the example score sorting unit905, the example comparison probability determination unit910, the example comparison probability summation unit915, the example summed comparison probability combination unit920, the example expected score sorting unit1005, the example expected score determination unit1010, the example sorted tuple selection unit1015, the example upper bound determination unit1020, the example lower bound determination unit1025, the example curtailed dataset determination unit1030, the example tuple sorting unit1105, the example score probability summation unit1110, the example expected instantiation size determination unit1115, the example exclusion rule evaluation unit1120, the example score probability combination unit1125, the example sorted tuple selection unit1205, the example lower bound determination unit1210and/or the example expected rank selection unit1215could be implemented by any combination of software, hardware, and/or firmware. Also, some or all of the machine readable instructions represented by the flowchart ofFIGS. 13-18may be implemented manually. Further, although the example machine readable instructions are described with reference to the flowcharts illustrated inFIGS. 13-18, many other techniques for implementing the example methods and apparatus described herein may alternatively be used. For example, with reference to the flowcharts illustrated in FIGS.13-18, the order of execution of the blocks may be changed, and/or some of the blocks described may be changed, eliminated, combined and/or subdivided into multiple blocks.

Example machine readable instructions1300that may be executed to implement the example expected ranking unit115ofFIGS. 1and/or7are represented by the flowchart shown inFIG. 13. The example machine readable instructions1300may be executed at predetermined intervals, based on an occurrence of a predetermined event, etc., or any combination thereof. With reference to the first example implementation of the expected ranking unit115ofFIG. 7, the example machine readable instructions1300begin execution at block1305ofFIG. 13at which the example data set instantiation unit705included in the example expected ranking unit115obtains the set of data tuples {t} stored in the example probabilistic database110. Then, at block1310the example data set instantiation unit705begins determining each possible data set instantiation corresponding to each possible world W included in the set of all possible worlds S capable of being realized from the set of data tuples {t} obtained at block1305.

Next, control proceeds to block1315at which the example per-instantiation component ranking unit710begins selecting each tuple tifrom a possible data set instantiation W determined by the example data set instantiation unit705at block1310. Then, at block1320the example per-instantiation component ranking unit710determines a per-instantiation, or component, rank rankW(ti) of the currently selected tuple tiin the possible data set instantiation W according to Equation 4 as described above. The determined rank rankW(ti) is the number of data tuples whose score in the possible data set instantiation W is higher than the tuple ti. Next, at block1325, if all the data tuples tiin the possible data set instantiation W determined at block1310have not been processed, control returns to block1315and blocks subsequent thereto at which the example per-instantiation component ranking unit710determines the per-instantiation, or component, rank rankW(ti+1) for the next selected tuple ti+1in the possible data set instantiation W. However, if all data tuples tiin the possible data set instantiation W determined at block1310have been processed (block1325), control proceeds to block1330.

At block1330, the example instantiation probability determination unit715included in the example expected ranking unit115determines the instantiation probability Pr[W] for the possible data set instantiation W determined at block1310as described above in connection withFIG. 7. The instantiation probability Pr[W] determined at block1330represents the likelihood of the possible world W occurring among the set of all possible worlds S. Next, at block1335, if all possible data set instantiations determined by the example data set instantiation unit705have not been processed, control returns to block1310and blocks subsequent thereto at which the example data set instantiation unit705determines a next possible data set instantiation for processing. However, if all possible data set instantiations determined by the example data set instantiation unit705have been processed (block1335), control proceeds to block1340.

At block1340, the example expected rank combining unit720included in the example expected ranking unit115begins selecting each tuple tiin the set of data tuples {t} obtained at block1305. Then, at block1345the example expected rank combining unit720combines the per-instantiation, or component, ranks rankW(ti) determined at block1320for the current selected tuple tiin all the possible worlds W after weighting by the respective instantiation probabilities Pr[W] determined at block1335. The example expected rank combining unit720performs such combination of the component ranks rankW(ti) and instantiation probabilities Pr[W] according to Equation 5 or Equation 6 as described above in connection withFIG. 7. Next, at block1350, if all the data tuples tiin the set of data tuples {t} obtained at block1305have not been processed, control returns block1340and blocks subsequent thereto at which the example expected rank combining unit720combines the component ranks rankW(ti+1) and instantiation probabilities Pr[W] for the next selected tuple ti+1in the set of data tuples {t} obtained at block1305. However, if all the data tuples tiin the set of data tuples {t} obtained at block1305have been processed (block1350), execution of the example machine readable instructions1300ends.

Example machine readable instructions1400that may be executed to implement the example expected ranking unit115ofFIGS. 1and/or8are represented by the flowchart shown inFIG. 14. The example machine readable instructions1400may be executed at predetermined intervals, based on an occurrence of a predetermined event, etc., or any combination thereof. With reference to the second example implementation of the example expected ranking unit115ofFIG. 8, the example machine readable instructions1400begin execution at block1405ofFIG. 14at which the example expected ranking unit115obtains the set of data tuples {t} stored in the example probabilistic database110. Then, at block the example expected ranking unit115obtains a top-k query via, for example, the query interface140of the example probabilistic database server105ofFIG. 1. The top-k query specifies the number of tuples, k, to be returned in response to the top-k query

Next, at block1410the expected rank type specifier805included in the example expected ranking unit115obtains a type of expected rank to be determined for the tuples tiin the set of data tuples {t} obtained at block1405. The expected ranks determined for the tuples tiare used to select the k top-ranked tuples in response to the top-k query received at block1410. In the illustrated example, the type of expected rank can be pre-determined, specified by a user via the example interface terminal140and/or determined automatically based on the uncertainty relation used to store the set of data tuples {t} in the probabilistic database110and whether pruning is to be employed to reduce the number of tuples that need to be accessed to determine the expected ranks and select the k top-ranked tuples.

In the illustrated example, control proceeds to block1420at which the expected rank type specifier805evaluates the expected rank type obtained at block1415. If the expected rank type corresponds to an attribute-level exact expected rank (block1420), control proceeds to block1425at which the example expected rank type specifier805invokes the example attribute-level exact expected ranking unit810included in the example expected ranking unit115to perform an attribute-level exact expected ranking procedure implementing the A-ERrank technique described above in connection withFIG. 9. Example machine readable instructions that may be used to implement the processing at block1425are illustrated inFIG. 15and described in greater detail below. If, however, the expected rank type corresponds to an attribute-level pruned expected rank (block1420), control proceeds to block1430at which the example expected rank type specifier805invokes the example attribute-level pruned expected ranking unit815to perform an attribute-level pruned expected ranking procedure implementing the A-ERank-Prune technique described above in connection withFIG. 10. Example machine readable instructions that may be used to implement the processing at block1430are illustrated inFIG. 16and described in greater detail below.

However, if the expected rank type corresponds to a tuple-level exact expected rank (block1420), control proceeds to block1435at which the example expected rank type specifier805invokes the example tuple-level pruned expected ranking unit820included in the example expected ranking unit115to perform a tuple-level exact expected ranking procedure implementing the T-ERrank technique described above in connection withFIG. 11. Example machine readable instructions that may be used to implement the processing at block1435are illustrated inFIG. 17and described in greater detail below. If, however, the expected rank type corresponds to a tuple-level pruned expected rank (block1420), control proceeds to block1440at which the example expected rank type specifier805invokes the example tuple-level pruned expected ranking unit825to perform a tuple-level pruned expected ranking procedure implementing the T-ERrank-Prune technique described above in connection withFIG. 12. Example machine readable instructions that may be used to implement the processing at block1440are illustrated inFIG. 18and described in greater detail below. Execution of the example machine readable instructions1400then ends.

Example machine readable instructions1425that may be executed to implement the example attribute-level exact expected ranking unit810ofFIGS. 8and/or9, and/or that may be used to implement the processing performed at block1425ofFIG. 14are represented by the flowchart shown inFIG. 15. With reference to the example attribute-level exact expected ranking unit810ofFIG. 9, the example machine readable instructions1425begin execution at block1505ofFIG. 15at which the example score sorting unit905included in the example attribute-level exact expected ranking unit810sorts the universe of all possible score values v of all data tuples t to determine a sorted combined score set U.

Next, control proceeds to block1510at which the example comparison probability determination unit910included in the example attribute-level exact expected ranking unit810begins selecting each score in the sorted combined score set U. Then, at block1515the example comparison probability determination unit910begins selecting each tuple tjin the set of data tuples. Control then proceeds to block1520at which the example comparison probability determination unit910determines a comparison probability Pr[Xj>v] for the score v currently selected at block1510and the data tuple tjcurrently selected at block1515. The comparison probability Pr[Xj>v] determined at block1520represents how likely the respective score v is exceeded by the data tuple tj. Next, at block1525, if all of the data tuples tjhave not been processed, control returns to block1515and blocks subsequent thereto at which the example comparison probability determination unit910determines a comparison probability Pr[Xj+1>v] for the score v currently selected at block1510and the next data tuple tj+1. However, if all of the data tuples tjhave been processed (block1525), control proceeds to block1530.

At block1530, the example comparison probability summation unit915included in the example attribute-level exact expected ranking unit810determines the sum of comparison probabilities, q(v), for a score v currently selected from the sorted combined score set U at block1510. Then, at block1535, if all of the scores v currently in the sorted combined score set U have not been processed, control returns to block1510and blocks subsequent thereto at which the example comparison probability determination unit910selects a next score v from the sorted combined score set U for processing. If, however, all of the scores v currently in the sorted combined score set U have not been processed (block1535), control proceeds to block1540.

At block1540, the example summed comparison probability combination unit920included in the included in the example attribute-level exact expected ranking unit810begins selecting each tuple tjin the set of data tuples. Next, control proceeds to block1545at which the example summed comparison probability combination unit920determines the expected rank r(ti) for the data tuple tiselected at block1545by combining the summed comparison probabilities q(v) corresponding to only the set of scores vi,lassociated with the selected data tuple ti, with the summed comparison probabilities q(vi,l) for a particular score vi,lbeing weighted by the corresponding score probability pi,laccording to Equation 11 as discussed above. Then, at block1550, if all data tuples have not been processed, control returns to block1540and blocks subsequent thereto at which the example summed comparison probability combination unit920determines the expected rank r(ti+1) for the next selected data tuple ti+1. However, if all data tuples have been processed (block1550), control proceeds to block1555. at which the example summed comparison probability combination unit920selects the k tuples with smallest expected rank determined at block1545as the k top-ranked tuples to return in response to a top-k query. Execution of the example machine readable instructions1425then ends.

Example machine readable instructions1430that may be executed to implement the example attribute-level pruned expected ranking unit815ofFIGS. 8and/or10, and/or that may be used to implement the processing performed at block1430ofFIG. 14are represented by the flowchart shown inFIG. 16. With reference to the example attribute-level pruned expected ranking unit815ofFIG. 10, the example machine readable instructions1430begin execution at block1605ofFIG. 16at which the example expected score determination unit1010included in the example attribute-level pruned expected ranking unit815selects a data tuple tifrom the set of data tuples. Control then proceeds to block1610at which the example expected score determination unit1010determines an expected score E[Xi] for the tuple tiselected at block1606by summing the possible scores vi,lfor the data tuple ti, with each score weighted by the respective score probability pi,las described above in connection withFIG. 10. Then, at block1615, if all data tuples have not been processed, control returns to block1605and blocks subsequent thereto at which the the example expected score determination unit1010selects a next tuple ti+1for which an expected score E[Xi+1]. However, if all data tuples have been processed (block1615), control proceeds to block1620.

At block1620, the example expected score sorting unit1005included in the example attribute-level pruned expected ranking unit815sorts the sorts expected scores for the data tuples in decreasing order such that, if i<j, then E[Xi]≧E[Xj] for all 1≦i,j≦N. Then, control proceeds to block1625at which the example sorted tuple selection unit1015included in the example attribute-level pruned expected ranking unit815begins selecting data tuples in decreasing order of expected rank E[Xi] as sorted at block1620. Next, at blocks1630through1645, the example attribute-level pruned expected ranking unit815maintains an upper bound r+(ti) for each data tuple tiselected so far at block1630and a lower bound denoted r on the expected ranks for all currently unselected data tuples. In particular, at block1635, the example upper bound determination unit1020included in the example attribute-level pruned expected ranking unit815determine an upper bound r+(ti) on the expected rank r(ti) for each selected data tuple tiusing Equation 13 as described above in connection withFIG. 10. At block1640, the example lower bound determination unit1025included in the example attribute-level pruned expected ranking unit815determines the lower bound r−on the expected rank r(tu) for all unselected tuples tuusing Equation 15.

After the upper bound r+(ti) for each data tuple tiselected so far at block1630and the lower bound denoted r−on the expected ranks for all currently unselected data tuples are determined at blocks1630-1645, control proceeds to block1650. At block1650, the example attribute-level pruned expected ranking unit815determines whether k th largest upper bound r+(ti) for the expected ranks of the currently selected tuples is less than the lower bound r−on the expected ranks for the unselected tuples. If the k th largest upper bound is not less than the lower bound (block1650), control returns to block1625and blocks subsequent thereto at which the example sorted tuple selection unit1015selects the next data tuple in decreasing order of expected rank and updates the upper bounds on the expected ranks for the currently selectd tuples and the lower bound on the expected ranks for the unselected tuples.

However, if the k th largest upper bound is less than the lower bound (block1650), control proceeds to block1425. At block1425, the example attribute-level pruned expected ranking unit815performs the attribute-level exact ranking procedure described above in connection withFIG. 15, but for only a curtailed dataset. The curtailed dataset includes only the data tuples which were selected during the iterative processing at block1625. In the illustrated example, the processing at block1425returns the k top ranked data tuples in response to a top-k query. Execution of the example machine readable instructions1430then ends.

Example machine readable instructions1435that may be executed to implement the example tuple-level exact expected ranking unit820ofFIGS. 8and/or11, and/or that may be used to implement the processing performed at block1435ofFIG. 14are represented by the flowchart shown inFIG. 17. With reference to the example tuple-level exact expected ranking unit820ofFIG. 11, the example machine readable instructions1435begin execution at block1705ofFIG. 17at which the example tuple sorting unit1105included in the example tuple-level exact expected ranking unit820sorts the data tuples tiin decreasing order of their score attributes vito determine a sorted set of data tuples.

Next, control proceeds to block1710at which the example score probability summation unit1110included in the example tuple-level exact expected ranking unit820selects each data tuple tiin the set of data tuples. Then, at block1715the example score probability summation unit1110determines

qi=∑j<i⁢p⁡(tj),
which is the sum of the score probabilities p(tj) for all data tuples tjordered before the data tuple tiin the sorted score set determined at block1705. At block1720, if all data tuples have not been processed, control returns to block1710and blocks subsequent thereto at which the example score probability summation unit1110selects the next data tuple for which a score probability summation qi+1is to be determined. However, if all data tuples have been processed (block1720), control proceeds to block1730.

At block1730, the example instantiation size determination unit1115included in the example tuple-level exact expected ranking unit820sums the score probabilities determined at block1715to determine the quantity

E⁡[W]=∑j=1N⁢⁢p⁡(tj),
which is the expected number of tuples averaged over all possible worlds S. Control then proceeds to blocks1730through1745at which the example tuple-level exact expected ranking unit820uses the score probability summation qidetermined at block1715and the expected number of tuples E[|W|] determined at block1725to determine the expected rank r(ti) for each data tuple ti. In particular, at block1735the example exclusion rule evaluation unit1120included in the example tuple-level exact expected ranking unit820selects score probabilities for data tuples included in an exclusion rule τ with a currently selectd tuple tifor which the expected rank r(ti) is to be determined. At block1740, the example score probability combination unit1125included in the example tuple-level exact expected ranking unit820combines the score probability summation qidetermined at block1715, the expected number of tuples E[|W|] determined at block1725and the score probabilities selected at block1735according to Equation 18 as described above to determine the expected rank r(ti) for the currently selected tuple ti.

After the expected ranks for all tuples are determined at blocks1730-1745, control proceeds to block1750at which the example tuple-level exact expected ranking unit820selects the k tuples with the smallest expected ranks r(ti) to return in response to a top-k query. Execution of the example machine readable instructions1435then ends.

Example machine readable instructions1440that may be executed to implement the example tuple-level pruned expected ranking unit825ofFIGS. 8and/or12, and/or that may be used to implement the processing performed at block1440ofFIG. 14are represented by the flowchart shown inFIG. 18. With reference to the example tuple-level pruned expected ranking unit825ofFIG. 12, the example machine readable instructions1440begin execution at block1805ofFIG. 18at which the example tuple-level pruned expected ranking unit825determines the sorted set of data tuples and the score probability summations qifor the set of tuples tias in blocks1705-1725ofFIG. 17, which are described above in greater detail. Additionally, block1810represents the assumption that the expected number of tuples E[|W|] is known and available and, therefore, no processing is required at block1810.

Then, given the preceding preliminary information, control proceeds to block1815at which the example sorted tuple selection unit1205included in the example tuple-level pruned expected ranking unit825selects a next data tuple tnin decreasing order of score from the sorted set of tuples. Control then proceeds to block1820at which the example exclusion rule evaluation unit1120included in the example tuple-level pruned expected ranking unit825selects score probabilities for data tuples included in an exclusion rule τ with a currently selectd tuple tnfor which the expected rank r(tn) is to be determined. Next, at block1825, the example score probability combination unit1125included in the example tuple-level pruned expected ranking unit825combines the score probability summation qnfor the selected tuple tn, the expected number of tuples E[|W|] and the score probabilities selected at block1820according to Equation 18 as described above to determine the expected rank r(tn) for the currently selected tuple tn.

Control next proceeds to block1830at which the example lower bound determination unit1210included in the example tuple-level pruned expected ranking unit825determines a lower bound on the expected ranks r(tl) for all unselected tuples tl, l>n. For example, at block1830the example lower bound determination unit1210determines the lower bound on the expected ranks r(tl) for all unselected tuples based on the score probability summation qnfor the selected tuple tnaccording to Equation 21 as described above. Next, control proceeds to block1835at which the example tuple-level pruned expected ranking unit825determines whether the lower bound determined at block1830exceeds the k th largest expected rank determined for the currently selected tuples. If the lower bound does not exceed the k th largest expected rank (block1835), control returns to block1815and blocks subsequent thereto at which the example sorted tuple selection unit1205selects a next data tuple tn+1in decreasing order of score from the sorted set of tuples. However, if the lower bound does exceed the k th largest expected rank (block1835), control proceeds to block1840at which the example tuple-level pruned expected ranking unit825selects the k tuples with the smallest expected ranks r(ti) to return in response to a top-k query. Execution of the example machine readable instructions1440then ends.

Example performance results for the first and second example implementations of the expected ranking unit115illustrated inFIGS. 7-12are illustrated inFIGS. 19-25. To generate these example performance results, examples of the expected rank techniques described herein were implemented in GNU C++ and executed on a Linux machine having a central processing unit (CPU) operating at 2 GHz and main memory of 2 GB. Several data generators were implemented to generate synthetic data sets for both the attribute-level and tuple-level uncertainty models. Each generator controlled the distributions of score values and score probabilities for the data tuples representing the uncertain data. For both models, these distributions represent the universe of score values and score probabilities when the union of all tuples in D is taken. The distributions examined include uniform, Zipfian and correlated bivariate distributions, abbreviated herein as “u,” “zipf” and “cor,” respectively. For each tuple, a score and probability value was drawin independently from the score distribution and probability distribution respectively. In the following, the result of drawing from these two distributions is referred to by the concatenation of the abbreviation for the score distribution followed by the abbreviation for the score probability distribution. For example, uu indicates a data set with uniform distributions for both score values and score probabilities, whereas zipfu indicates a Zipfian distribution of score values and a uniform distribution on the score probabilities. In the illustrated examples, the default skewness parameter for the Zipfian distribution was 1.2, and the default value of k was k=100.

FIGS. 19-21illustrate performance results for determining expected ranks for uncertain data represented using an attribute-level uncertainty model.FIG. 19illustrates the performance of the example attribute-level exact expected ranking unit810implementing the A-ERank technique described above in connection withFIG. 9relative to the brute-force search (BFS) technique for determining expected ranks represented by Equation 5 and implemented by the example expected ranking unit115ofFIG. 7as discussed above. The score probability distribution does not affect the performance of either technique because both the A-ERank and BFS techniques determine the expected ranks of all tuples. However, while score value distribution does not affect BFS, it does affect A-ERank. For example, the uniform score distribution results in the worst performance given a fixed number of tupless because it results in a large set of possible values, U, that needs to be processed by the A-ERank technique. Therefore, a uu data set was used to generate a performance graph1900illustrated inFIG. 19, with each tuple having five (s=5) score (vi,j) and score probability (pi,j) pairs.

The example performance graph1900ofFIG. 19depicts the total running time of example implementations of the A-ERank and BFS techniques as the number of tuples, N, in the attribute-level uncertainty relation D in a range from about 10,000 tuples up to 100,000 tuples. As illustrated by the example performance graph1900, the A-ERank technique outperforms BFS technique by up to six orders of magnitude, with the improvement increasing steadily as N gets larger. For example, A-ERank takes only about 10 ms to determine expected ranks for all tuples when the number of tuples is N=100,000, whereas the BFS technique takes approximately ten minutes. Similar results were observed for data tuples having other numbers (s) of score and score probability pairs.

FIG. 20illustrates the benefits of pruning associated with the A-ERank-Prune technique implemented by the example attribute-level pruned expected ranking unit815described above in connection withFIG. 10. For example, the performance graph2000ofFIG. 20illustrates the number of tuples that are pruned (e.g., not accessed) to determine expected ranks in response to a top-k query when the number of tuples, N, in the attribute-level uncertainty relation D is 100,000 tuples and each tuple has s=5 score and score probability pairs. In the example performance graph2000, the size of the top-k query, k, is varied from 10 to 100, The example performance graph2000depicts that often only a small number of tuples in D (ordered by expected score) need to be accessed to determine the tuples having the top-k expected ranks. Additionally, the example performance graph2000illustrates that a skewed distribution for either score values or score probabilities improve the pruning benefits exhibited by the A-ERank-Prune technique. For example, when both the score and score probabilities both distributions are skewed (e.g., corresponding to the zipfzipf case), the A-ERank-Prune determined the top-k expected ranks after accessing less than 20% of the tuples in the uncertainty relation D. However, the example performance graph2000demonstrates that pruning benefits were seen even for uniform distributions of scores and score probabilities.

As discussed above in connection withFIG. 10, the A-ERank-Prune technique implemented by the example attribute-level pruned expected ranking unit815returns an approximate ranking of top-k tuples according to expected rank. The example performance graph2100ofFIG. 21depicts the approximation quality of the A-ERank-Prune technique for various data sets using standard precision and recall metrics. Because A-ERank-Prune always returns k tuples, its recall and precision metrics are the same. The example performance graph2100ofFIG. 21illustrates that A-ERank-Prune achieves high approximation quality. For example, recall and precision are both in the 90th percentile when the score values are uniformly distributed (corresponding to the uu and uzipf cases). The worst case occurs when the data is skewed in both the score and score probability dimensions (corresponding to the zipfzipf case), where the potential for pruning is greatest. The reason for the illustrated decrease in recall and precision for this scenario is that, as more tuples are pruned, the pruned (e.g., unselected) tuples have a greater chance to affect the expected ranks of the observed tuples. Even though the pruned tuples all have low expected scores, they could still be associated with one or more values having a high probability to be ranked above one or more of the selected tuples, because of the heavy tail associated with a skewed distribution. However, even in the illustrated worst case, the recall and precision of A-ERank-Prune is about 80% as illustrated in the example performance graph2100ofFIG. 21.

FIGS. 22-25illustrate performance results for determining expected ranks for uncertain data represented using a tuple-level uncertainty model. In the illustrated examples, the tuple-level uncertainty models employed exclusion rules in which approximately 30% of tuples were included in rules with other tuples. Although not shown, experiments with a greater or lesser degree of exclusion among tuples yielded similar results. Additionally, similar to the results inFIG. 19for the attribute-level model, the example tuple-level exact expected ranking unit820implementing the T-ERank technique described above in connection withFIG. 11exhibited better running time performance relative to the BFS technique for determining expected ranks represented by Equation 5 and implemented by the example expected ranking unit115ofFIG. 7as discussed above. For brevity, these results are not included herein.

As discussed above in connection withFIG. 12, unlike the attribute-level pruning technique, the tuple-level pruning technique T-ERank-Prune implemented by the example tuple-level pruned expected ranking unit825determines the exact, rather than an approximate, top-k tuples according to expected rank provided that E[|W|], the expected number of tuples of D, is known. The example performance graph2200inFIG. 22illustrates the total running time for the T-ERank and T-ERank-Prune techniques using uu data. The example performance graph2200showns that both techniques are extremely efficient. For example, for 100,000 tuples, the T-ERank techniques takes about 10 milliseconds to compute the expected ranks for all tuples. Applying pruning, the T-ERank-Prune technique finds the same k smallest ranks in just 1 millisecond. Even so, T-ERank is still highly efficient, especially in scenarios when E[|W|] is unavailable.

The example performance graph2300ofFIG. 23illustrated the pruning capabilities of the T-ERank-Prune for different data sets. In the illustrated example, the number of data tuples was set to N=100,000 and the number of top-k tuples to return was varied. As expected, a skewed distribution on either dimension (e.g., corresponding to the uu, uzipf and zipfu cases) increased the pruning capability of T-ERank-Prune. Additionally, even in the worst case of processing the uu data set, T-ERank-Prune was able to prune more than 90% of tuples

FIGS. 24 and 25illustrated the impact of correlations between a tuple's score value and score probability. As used herein, a score value and a respective score probability are positively correlated for a particular tuple when the tuple has a high score value and also a high probability. Similarly, a score value and a respective score probability are negatively correlated when the tuple has a high score but a low probability, or vice versa. Such correlations do not impact the performance of the T-ERank technique because it computes the expected ranks for all tuples. However, correlation does have an effect on the pruning capability of the T-ERrank-Prune technique. For exampe, the performance graph2400ofFIG. 24depicts the pruning capability of the T-ERank-Prune technique for correlated bivariate data sets of N=100,000 data tuples having different correlation degrees. The example performance graph2400illustrates that a strongly positively correlated data set with a +0.8 correlation degree allows a significantly better amount of pruning than a strongly negatively correlated data set with a −0.8 correlation degree. However, even for the strongly negatively correlated data set, T-ERank-Prune still pruned more than 75% of tuples as shown in the example performance graph2400. The performance graph2500ofFIG. 25illustrates the running time for the example ofFIG. 24and shows that the T-ERank-Prune technique requires between 0.1 and 5 milliseconds to process 100,000 uncertain tuples.

FIG. 26is a block diagram of an example computer2600capable of implementing the apparatus and methods disclosed herein. The computer2600can be, for example, a server, a personal computer, a personal digital assistant (PDA), an Internet appliance, a DVD player, a CD player, a digital video recorder, a personal video recorder, a set top box, or any other type of computing device.

The system2600of the instant example includes a processor2612such as a general purpose programmable processor. The processor2612includes a local memory2614, and executes coded instructions2616present in the local memory2614and/or in another memory device. The processor2612may execute, among other things, the machine readable instructions represented inFIGS. 13-18. The processor2612may be any type of processing unit, such as one or more microprocessors from the Intel® Centrino® family of microprocessors, the Intel® Pentium® family of microprocessors, the Intel® Itanium® family of microprocessors, and/or the Intel XScale® family of processors. Of course, other processors from other families are also appropriate.

The processor2612is in communication with a main memory including a volatile memory2618and a non-volatile memory2620via a bus2622. The volatile memory2618may be implemented by Static Random Access Memory (SRAM), Synchronous Dynamic Random Access Memory (SDRAM), Dynamic Random Access Memory (DRAM), RAMBUS Dynamic Random Access Memory (RDRAM) and/or any other type of random access memory device. The non-volatile memory2620may be implemented by flash memory and/or any other desired type of memory device. Access to the main memory2618,2620is typically controlled by a memory controller (not shown).

The computer2600also includes an interface circuit2624. The interface circuit2624may be implemented by any type of interface standard, such as an Ethernet interface, a universal serial bus (USB), and/or a third generation input/output (3GIO) interface.

One or more input devices2626are connected to the interface circuit2624. The input device(s)2626permit a user to enter data and commands into the processor2612. The input device(s) can be implemented by, for example, a keyboard, a mouse, a touchscreen, a track-pad, a trackball, an isopoint and/or a voice recognition system.

One or more output devices2628are also connected to the interface circuit2624. The output devices2628can be implemented, for example, by display devices (e.g., a liquid crystal display, a cathode ray tube display (CRT)), by a printer and/or by speakers. The interface circuit2624, thus, typically includes a graphics driver card.

The interface circuit2624also includes a communication device such as a modem or network interface card to facilitate exchange of data with external computers via a network (e.g., an Ethernet connection, a digital subscriber line (DSL), a telephone line, coaxial cable, a cellular telephone system, etc.).

The computer2600also includes one or more mass storage devices2630for storing software and data. Examples of such mass storage devices2630include floppy disk drives, hard drive disks, compact disk drives and digital versatile disk (DVD) drives. The mass storage device2630may implement the example data tuple storage205. Alternatively, the volatile memory2618may implement the example data tuple storage205.

At least some of the above described example methods and/or apparatus are implemented by one or more software and/or firmware programs running on a computer processor. However, dedicated hardware implementations including, but not limited to, application specific integrated circuits, programmable logic arrays and other hardware devices can likewise be constructed to implement some or all of the example methods and/or apparatus described herein, either in whole or in part. Furthermore, alternative software implementations including, but not limited to, distributed processing or component/object distributed processing, parallel processing, or virtual machine processing can also be constructed to implement the example methods and/or apparatus described herein.

It should also be noted that the example software and/or firmware implementations described herein are optionally stored on a tangible storage medium, such as: a magnetic medium (e.g., a magnetic disk or tape); a magneto-optical or optical medium such as an optical disk; or a solid state medium such as a memory card or other package that houses one or more read-only (non-volatile) memories, random access memories, or other re-writable (volatile) memories; or a signal containing computer instructions. A digital file attached to e-mail or other information archive or set of archives is considered a distribution medium equivalent to a tangible storage medium. Accordingly, the example software and/or firmware described herein can be stored on a tangible storage medium or distribution medium such as those described above or successor storage media.

To the extent the above specification describes example components and functions with reference to particular standards and protocols, it is understood that the scope of this patent is not limited to such standards and protocols. For instance, each of the standards for Internet and other packet switched network transmission (e.g., Transmission Control Protocol (TCP)/Internet Protocol (IP), User Datagram Protocol (UDP)/IP, HyperText Markup Language (HTML), HyperText Transfer Protocol (HTTP)) represent examples of the current state of the art. Such standards are periodically superseded by faster or more efficient equivalents having the same general functionality. Accordingly, replacement standards and protocols having the same functions are equivalents which are contemplated by this patent and are intended to be included within the scope of the accompanying claims.

Additionally, although this patent discloses example systems including software or firmware executed on hardware, it should be noted that such systems are merely illustrative and should not be considered as limiting. For example, it is contemplated that any or all of these hardware and software components could be embodied exclusively in hardware, exclusively in software, exclusively in firmware or in some combination of hardware, firmware and/or software. Accordingly, while the above specification described example systems, methods and articles of manufacture, persons of ordinary skill in the art will readily appreciate that the examples are not the only way to implement such systems, methods and articles of manufacture. Therefore, although certain example methods, apparatus and articles of manufacture have been described herein, the scope of coverage of this patent is not limited thereto. On the contrary, this patent covers all methods, apparatus and articles of manufacture fairly falling within the scope of the appended claims either literally or under the doctrine of equivalents.