| Interactive rule-based expert systems, which work by “interviewing” their users, have found applications in fields ranging from aerospace to help desks. Although they have been shown to be useful, people find them difficult to query in flexible ways. This limits the reusability of the knowledge they contain. Databases and noninteractive rule systems such as logic programs, on the other hand, are queryable but they do not offer an interview capability. This thesis is the first investigation that we know of into query-processing for interactive expert systems.; In our query paradigm, the user describes a hypothetical condition and then the system reports which of its conclusions are reachable, and which are inevitable, under that condition. For instance, if the input value for bloodSugar exceeds 100, units, is the conclusion diabetes then inevitable? Reachability problems have been studied in other settings, e.g., the halting problem, but not for interactive expert systems.; We first give a theoretical framework for query-processing that covers a wide class of interactive expert systems. Then we present a query algorithm for a specific language of expert systems. This language is a restriction of production systems to an acyclic form that generalizes decision trees and classical spreadsheets. The algorithm effects a reduction from the reachability and inevitability queries into datalog rules with constraints. When preconditions are conjunctive, the data complexity is tractable. Next, we optimize for queries to production systems that contain regions which are decision trees. When general-purpose datalog methods are applied to the rules that result from our queries, the number of constraints that must be solved is O( n2), where n is the size of the trees. We lower the complexity to O(n2). Finally, we have built a query tool for a useful subset of the acyclic production systems. To our knowledge, these are the first interactive expert systems that can be queried about the reachability and inevitability of their conclusions. |
