COMPOSITION WITH TARGET CONSTRAINTS

Simple item page
dc.contributor.authorArenas, Marcelo
dc.contributor.authorFagin, Ronald
dc.contributor.authorNash, Alan
dc.date.accessioned2025-01-20T23:58:56Z
dc.date.available2025-01-20T23:58:56Z
dc.date.issued2011
dc.description.abstractIt is known that the composition of schema mappings, each specified by source-to-target tgds (st-tgds), can be specified by a second-order tgd (SO tgd). We consider the question of what happens when target constraints are allowed. Specifically, we consider the question of specifying the composition of standard schema mappings (those specified by st-tgds, target egds, and a weakly acyclic set of target tgds). We show that SO tgds, even with the assistance of arbitrary source constraints and target constraints, cannot specify in general the composition of two standard schema mappings. Therefore, we introduce source-to-target second-order dependencies (st-SO dependencies), which are similar to SO tgds, but allow equations hi the conclusion. We, show that st-SO dependencies (along with target egds and target tgds) are sufficient to express the composition of every finite sequence of standard schema mappings, and further, every at SO dependency specifies such a composition. In addition to this expressive power, we show that st-SO dependencies enjoy other desirable properties. In particular, they have a polynomial-time chase that generates a universal solution. This universal solution can be used to find the certain answers to unions of conjunctive queries in polynomial time.
dc.description.abstractIt is easy to show that the composition of an arbitrary number of standard schema mappings is equivalent to the composition of only two standard schema mappings. We show that surprisingly, the analogous result holds also for schema mappings specified by just st-tgds (no target constraints). That,flat is, the composition of an arbitrary number of such schema mappings is equivalent to the composition of only two such schema mappings. This is proven by showing that every SO tgd is equivalent to an unnested SO tgd (one where there is no nesting of function symbols). The language of unnested SO tgds is quite natural, and we show that unnested SO tgds are capable of specifying the composition of an arbitrary number of schema mappings, each specified by st-tgds. Similarly, we prove unnesting results for st-SO dependencies, with the same types of consequences.
dc.description.funderFONDECYT
dc.fuente.origenWOS
dc.identifier.doi10.2168/LMCS-7(3:13)2011
dc.identifier.issn1860-5974
dc.identifier.urihttps://doi.org/10.2168/LMCS-7(3:13)2011
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/95271
dc.identifier.wosidWOS:000301228300011
dc.issue.numero3
dc.language.isoen
dc.revistaLogical methods in computer science
dc.rightsacceso restringido
dc.subjectMetadata management
dc.subjectschema mapping
dc.subjectdata exchange
dc.subjectcomposition
dc.subjecttarget constraint
dc.titleCOMPOSITION WITH TARGET CONSTRAINTS
dc.typeartículo
dc.volumen7
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Collections
Artículos de revistas