Hierarchical Knowledge Bases and Efficient Disjunction Reasoning

Reasoning with incomplete information, including disjunctions, is expensive at best and intractable at worst. We introduce class hierarchies to extend the expressive power of relation- based data bases without exacting an unduly large computational price. We then show that concept hierarchies can be used to guide well-motivated approximations which substantially improve the computational complexity of reasoning with certain forms of disjunctive information.