Browsing by Author "Fagin, Ronald"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    COMPOSITION WITH TARGET CONSTRAINTS
    (2011) Arenas, Marcelo; Fagin, Ronald; Nash, Alan
    It 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.
  • Thumbnail Image
    Item
    Solutions and query rewriting in data exchange
    (2013) Arenas Saavedra, Marcelo Alejandro; Barceló Baeza, Pablo; Fagin, Ronald; Libkin, Leonid