Approximate Queries on Big Heterogeneous Data

The fundamental assumption for query rewriting in heterogeneous environments is that the mappings used for the rewriting are complete, i.e., Every relation and attribute mentioned in the query is associated, through mappings, to relations and attributes in the schema of the source that the query is rewritten. In reality, it is rarely the case that such complete sets of mappings exist between sources, and the presence of partial mappings is the norm rather than the exception. So, practically, existing query answering algorithms fail to generate any rewriting in the majority of cases. This becomes an insurmountable problem in the new era of Big Data, where we need query answers from various heterogeneous data sources. The question is then whether we can somehow approximate queries that cannot be rewritten as such (due to insufficient mappings), and whether we can identify the interesting query approximations, given the mappings at hand. In this paper, we present ongoing work on the proposal of techniques to compute query approximations of an input query that can be rewritten and evaluated in an environment of collaborating autonomous and heterogeneous big data sources. We are extending traditional techniques for query rewriting, and we propose heuristic algorithms to compute and evaluate these approximations.