Efficient datalog abduction through bounded treewidth
Georg Gottlob, Reinhard Pichler, Fang Wei · 2007
Abductive diagnosis is an important method for identi-fying possible causes which explain a given set of obser-vations. Unfortunately, abduction suffers from the fact that most of the algorithmic problems in this area are in-tractable. We have recently obtained very promising re-sults for a strongly related problem in the database area. Specifically, the PRIMALITY problem becomes effi-ciently solvable and highly parallelizable if the under-lying functional dependencies have bounded treewidth (Gottlob, Pichler, & Wei 2006b). In the current paper, we show that these favorable results can be carried over to logic-based abduction. In fact, we even show a fur-ther generalization of these results.