View determinacy for preserving selected information in data transformations

When transforming data one often wants certain information in the data source to be preserved, i.e.,  we identify parts of the source data and require these parts to be transformed without loss of information. We characterize the preservation of selected information in terms of the notions of invertibility and query preservation, in a setting when transformations are specified as a view VV (a set of queries), and source information is selected by a query Q  . We investigate the problem for determining whether transformations VV preserve the information selected by Q. (1) We show that the notion of invertibility coincides with view determinacy studied for query rewriting. (2) We establish the undecidability of the problem when either Q   or VV is in DATALOG or first-order logic, for invertibility and query preservation. (3) When Q   and VV are conjunctive queries (CQCQ), the problem is as hard as view determinacy for CQCQ queries and CQCQ views, an open problem. Nevertheless, we provide complexity bounds of the problem, either in ptime or np-complete, when VV ranges over subclasses of CQCQ (i.e.,  SPSP, SC, PCPC), and when Q   is assumed to be a minimal CQCQ query or not. (4) We show that CQCQ is complete for L-to-CQL-to-CQ rewriting when LL is SPSP, SC or PCPC, i.e.,  every CQCQ query can be rewritten in terms of SPSP, SC or PCPC views using a query in CQCQ.

► We model the notions of query preservation and invertability to specify the preservation of selected information in data transformations.
► Connections are established between view determinacy and invertability and between selected information preservation and query rewriting using views.
► Complexity results are provided for view determinacy and query preservation and tractable cases are identified.