Data exchange, the problem of transferring data from a source schema to a target schema, has been studied for several years. The semantics of answering positive queries over the target schema has been defined in early work, but little attention has been paid to more general queries. A few proposals of semantics for more general queries exist but they either do not properly extend the standard semantics under positive queries, giving rise to counterintuitive answers, or they make query answering undecidable even for the most important data exchange settings, for example, with weakly-acyclic dependencies.The goal of this paper is to provide a new semantics for data exchange that is able to deal with general queries. At the same time, we want our semantics to coincide with the classical one when focusing on positive queries, and to not trade-off too much in terms of complexity of query answering. We show that query answering is undecidable in general under the new semantics, but it is coNP-complete when the dependencies are weakly-acyclic. Moreover, in the latter case, we show that exact answers under our semantics can be computed by means of logic programs with choice, thus exploiting existing efficient systems. For more efficient computations, we also show that our semantics allows for the construction of a representative target instance, similar in spirit to a universal solution, that can be exploited for computing approximate answers in polynomial time.
Querying Data Exchange Settings Beyond Positive Queries / M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna. - In: THEORY AND PRACTICE OF LOGIC PROGRAMMING. - ISSN 1471-0684. - 24:2(2024 Mar), pp. 250-278. [10.1017/S1471068423000339]
Querying Data Exchange Settings Beyond Positive Queries
M. Calautti
Primo
;
2024
Abstract
Data exchange, the problem of transferring data from a source schema to a target schema, has been studied for several years. The semantics of answering positive queries over the target schema has been defined in early work, but little attention has been paid to more general queries. A few proposals of semantics for more general queries exist but they either do not properly extend the standard semantics under positive queries, giving rise to counterintuitive answers, or they make query answering undecidable even for the most important data exchange settings, for example, with weakly-acyclic dependencies.The goal of this paper is to provide a new semantics for data exchange that is able to deal with general queries. At the same time, we want our semantics to coincide with the classical one when focusing on positive queries, and to not trade-off too much in terms of complexity of query answering. We show that query answering is undecidable in general under the new semantics, but it is coNP-complete when the dependencies are weakly-acyclic. Moreover, in the latter case, we show that exact answers under our semantics can be computed by means of logic programs with choice, thus exploiting existing efficient systems. For more efficient computations, we also show that our semantics allows for the construction of a representative target instance, similar in spirit to a universal solution, that can be exploited for computing approximate answers in polynomial time.File | Dimensione | Formato | |
---|---|---|---|
querying-data-exchange-settings-beyond-positive-queries.pdf
accesso aperto
Descrizione: Article, online first
Tipologia:
Publisher's version/PDF
Dimensione
391.96 kB
Formato
Adobe PDF
|
391.96 kB | Adobe PDF | Visualizza/Apri |
querying-data-exchange-settings-beyond-positive-queries(1).pdf
accesso aperto
Tipologia:
Publisher's version/PDF
Dimensione
311.93 kB
Formato
Adobe PDF
|
311.93 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.