Query answering

In the academic world the derivation of a formula froin fundamentals is regarded as most important. In practice, this formula matters more rather than its origin. But for those who wish to know more of the reasoning and the background, care is taken that such subjects are also covered. The author hopes that readers will be satisfied to have most of their queries answered. 

The query answering model is different. Instead of necessarily finding all answers to a given query, our goal is typically to find the top-fc answers and rank these answers most effectively. 

Because of the uncertainty about which mapping is correct, we consider all of these mappings in query answering. 

We define query answering under both interpretations. The first interpretation is referred to as the by-table semantics, and the second one is referred to as the by-tuple semantics of probabilistic mappings. Note that one cannot argue for one interpretation over the other the needs of the application should dictate the appropriate semantics. Furthermore, the complexity results for query answering, which will show advantages to by-table semantics, should not be taken as an argument in the favor of by-table semantics. 

To extend the by-table query-answering strategy to by-tuple semantics, we would need to compute the certain answers for every mapping sequence generated by pM. However, the number of such mapping sequences is exponential in the size of the input data. The following example shows that for certain queries, this exponential time complexity is inevitable. 

The main challenge in designing the algorithm for returning top-A query answers is to only perform the necessary reformulations at every step and halt when the top-A answers are found. We focus on top-A query answering for by-table semantics, and the algorithm can be modified for by-tuple semantics. 

Recall that in by-table query answering, the probability of an answer is the sum of the probabilities of the reformulated queries that generate the answer. Our goal is to reduce the number of reformulated queries we execute. The algorithm we describe next proceeds in a greedy fashion it executes queries in descending order of probabilities. For each tuple t, it maintains the upper bound / max(f) and lower bound / min (0 of its probability. This process halts when it finds A tuples whose pm n values... 

In by-table query answering, we can enumerate all answers and compute their probabilities in polynomial time thus, query answering is in PTIME for all semantics. 

We can prove that under the expected-value semantics, the answer for the SUM operator under by-table and by-tuple semantics is the same thus, query answering for SUM under the by-tuple and expected-value semantics is in PTIME. 

For the COUNT operator, even query answering under the by-tuple semantics is PTIME for the distribution semantics and thus also for other semantics. We next illustrate this using an example. 

For the rest of the combinations, we conjecture that query answering cannot be finished in polynomial time and the complexity of query answering remains open. 

In this section, we describe several practical extensions to the basic mapping language. The query answering techniques and complexity results we have described carry over to these techniques. 

Fig. 4.5 The motivating example (a) p-mapping for Si and M3, (b) p-mapping for Si and M4, and (c) query answers w.r.t. M and pM. Here we denote phone, hPhone by hPPhone, phone, oPhone by oPPhone, address, hAddr by hAAddr, and address, oAddr by oAAddr...

Semantics of queries Next, we define the semantics of query answering with respect to a p-med-schema and a set of p-mappings for each mediated schema in the p-med-schema. Answering queries with respect to p-mappings returns a set of... 

We now extend this notion for query answering that takes p-med-schema into consideration. Intuitively, we compute query answers by first answering the query with respect to each possible mediated schema and then for each answer tuple by taking the sum of its probabilities weighted by the probabilities of the mediated schemas. 

We say that query answers A and A2 are equal (denoted A = A2) if A and A2 contain exactly the same set of tuples with the same probability assignments. 

Expressive power A natural question to ask at this point is whether probabilistic mediated schemas provide any added expressive power compared to deterministic ones. Theorem 8 shows that if we consider one-to-many schema mappings, where one source attribute can be mapped to multiple mediated attributes, then any combination of a p-med-schema and p-mappings can be equivalently represented using a deterministic mediated schema with p-mappings, but may not be represented using a p-med-schema with deterministic schema mappings. Note that we can easily extend the definition of query answers to one-to-many mappings, as one mediated attribute can correspond to no more than one source attribute. 

The main reason to consolidate the probabilistic mediated schema into a single one is that the user expects to see a single schema. In addition, consolidating to a single schema has the advantage of more efficient query answering queries now need to be rewritten and answered based on only one mediated schema. We note that in some contexts, it may be more appropriate to show the application builder a set of mediated schemas and let her select one of them (possibly improving on it later on). 

Section 5 provides an overview of the complexity results and algorithms developed for query answering over schema mappings ... 

In Fagin et al. [2005a], the semantics of query answering has been defined by considering the universal solutions. Indeed, it is important to ascertain whether certain answers of a query can be computed by query evaluation on the good target instance that has been chosen for materialization. In Sect. 2, we have already... 

---