Complexity grows steeply in queries with multiple heads and transitivity
Answering Conjunctive Queries over Linear Existential Rules with Transitivity
Databases
Summary
This paper looks at a type of logical question called conjunctive queries, which are used to get information from databases with certain rules. The authors study what happens when these rules include transitivity (like if A relates to B and B to C, then A relates to C) combined with linear rules that can have multiple outputs. While simpler versions of the problem are manageable, they found that adding multiple outputs makes the problem extremely hard to solve, even harder than some well-known tough problems. This means that building efficient systems for these queries with such rules will be challenging.
What this means in practice
- •For database system designers: Recognize limits in query optimizers when supporting linear rules with multiple heads and transitivity, helping avoid designs that lead to infeasible query processing times.
- •For knowledge graph engineers: Assess the feasibility of implementing complex inferencing rules in knowledge graphs involving linear dependencies with transitivity before deployment.
A theory result. No direct application yet.
Authors
Cristina Feier, Tomasz Gogacz, Filip Murlak
Abstract
We study Conjunctive Query Entailment Problem over ontologies con- sisting of Linear Tuple Generating Dependencies and transitivity asser- tions. A special case of this problem has been shown to be decidable in [1]. In particular, it covers the case of linear single head TGDs with bi- nary signature. In This paper we show that The problem for linear multi head TGDs with binary signature is Ackermanian hard