Abstract | ||
---|---|---|
In recent years, data examples have been at the core of several different approaches to schema-mapping design. In particular, Gottlob and Senellart introduced a framework for schema-mapping discovery from a single data example, in which the derivation of a schema mapping is cast as an optimization problem. Our goal is to refine and study this framework in more depth. Among other results, we design a polynomial-time log(n)-approximation algorithm for computing optimal schema mappings from a given set of data examples (where n is the combined size of the given data examples) for a restricted class of schema mappings; moreover, we show that this approximation ratio cannot be improved. In addition to the complexity-theoretic results, we implemented the aforementioned log(n)-approximation algorithm and carried out an experimental evaluation in a real-world mapping scenario. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1145/3044712 | ACM Trans. Database Syst. |
Keywords | DocType | Volume |
Approximation algorithms,schema mappings,data examples | Journal | 42 |
Issue | ISSN | Citations |
2 | 0362-5915 | 4 |
PageRank | References | Authors |
0.40 | 18 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Balder Ten Cate | 1 | 630 | 51.21 |
Phokion G. Kolaitis | 2 | 2733 | 514.37 |
Kun Qian | 3 | 4 | 1.08 |
WC Tan | 4 | 2529 | 198.85 |