Querying Incomplete Data : Complexity and Tractability via Datalog and First-Order Rewritings

Amélie Gheerbrant, Leonid Libkin, Alexandra Rogova +1

To answer database queries over incomplete data the gold standard is finding certain answers: those that are true regardless of how incomplete data is interpreted. Such answers can…