{'fraction_non_alphanumeric': 0.0213903743315508, 'fraction_numerical': 0.0053475935828877, 'mean_word_length': 5.51304347826087, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Efficient Datalog Abduction through Bounded Treewidth

Abductive diagnosis is an important method for identifying possible causes which explain a given set of observations. Unfortunately, abduction suffers from the fact that most of the algorithmic problems in this area are intractable. We have recently obtained very promising results for a strongly related problem in the database area. Specifically, the PRIMALITY problem becomes efficiently solvable and highly parallelizable if the underlying 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 further generalization of these results.