The complexity of reverse engineering problems for conjunctive queries

Abstract

Reverse engineering problems for conjunctive queries (CQs), such as query by example (QBE) ordefinability, take a set of user examples and convert them into an explanatory CQ. Despite theirimportance, the complexity of these problems is prohibitively high (coNEXPTIME-complete).We isolate their two main sources of complexity and propose relaxations of them that reduce thecomplexity while having meaningful theoretical interpretations. The first relaxation is based onthe idea of using existential pebble games for approximating homomorphism tests. We show thatthis characterizes QBE/definability for CQs up to treewidthk, while reducing the complexity toEXPTIME. As a side result, we obtain that the complexity of the QBE/definability problemsfor CQs of treewidthkis EXPTIME-complete for eachk≥1. The second relaxation is based onthe idea of “desynchronizing” direct products, which characterizes QBE/definability for unionsof CQs and reduces the complexity to coNP. The combination of these two relaxations yieldstractability for QBE and characterizes it in terms of unions of CQs of treewidth at mostk.We also study the complexity of these problems for conjunctive regular path queries over graphdatabases, showing them to be no more difficult than for CQs.