Approximation Algorithms for Schema-Mapping Discovery from Data Examples

作者：Ten Cate Balder^*; Kolaitis Phokion G; Qian Kun; Tan Wang Chiew

来源：ACM Transactions on Database Systems, 2017, 42(2): 12.

DOI：10.1145/3044712

• Approximation algorithms
• schema mappings
• data examples

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 nis 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.

• 出版日期2017-6
• 单位IBM