Consistency and Certain Answers in Relational to RDF Data Exchange with\n Shape Constraints

We investigate the data exchange from relational databases to RDF graphs\ninspired by R2RML with the addition of target shape schemas. We study the\nproblems of consistency i.e., checking that every source instance admits a\nsolution, and certain query answering i.e., finding answers present in every\nsolution. We identify the class of constructive relational to RDF data exchange\nthat uses IRI constructors and full tgds (with no existential variables) in its\nsource to target dependencies. We show that the consistency problem is\ncoNP-complete. We introduce the notion of universal simulation solution that\nallows to compute certain query answers to any class of queries that is robust\nunder simulation. One such class are nested regular expressions (NREs) that are\nforward i.e., do not use the inverse operation. Using universal simulation\nsolution renders tractable the computation of certain answers to forward NREs\n(data-complexity). Finally, we present a number of results that show that\nrelaxing the restrictions of the proposed framework leads to an increase in\ncomplexity.\n

Paper

Similar papers

© 2026 NYSGPT2525 LLC