Optimal Tuple Merge is NP-Complete

Abstract In this paper, we prove that Optimal Tuple Merge (OTM) is NP-Complete. OTM arises withinthe context of relational query language extensions to query and manipulate metadata as well as data. Such extensions include the ability to create dynamic output schemas from the inputdata. This flexibility is necessary for truly schema independent restructuring, however many null values may be introduced into the resultant data. Many of these "artifical " null values canbe subsequently merged away. We prove that the optimal merging case, in which the resulting relation contains as few tuples as possible, results in an NP-Complete problem. Fortunately,we can characterize when an optimal (and unique) merge is easy to obtain, and identify at least one class of practically relevant relations where OTM is efficiently solvable. 1 Introduction Recent frameworks for relational interoperability provide flexible methods for querying and re-structuring both metadata and data in canonical relations. This flexibility is necessary to satisfy the demands for schema independent queries that arise when combining semantically similar data frommultiple, distinct sources. Applications of relational interoperability are widespread, and include support for Federated Information Systems (FIS), encompassing the ability to create and managemediators, global schemas, and metadata dictionaries. Furthermore, recent extension to the relational query languages SQL and the RA enable real-time interoperability in a large federation ofrelational databases [3]. However, the added flexibility provided by frameworks for relational interoperability comeswith a price. One required capability is the ability to promote a column of data to relational attributes (column headings). In order that this "transpose-like " operation on relations has a con-sistent semantics for any relational table, many null values may be introduced into the result. We would ideally like to merge these "artificial " null values as much as possible to obtain a relationwith as few tuples as possible