5 Assumption handling
Evaluating any clause yields an assumption tag corresponding to each bindings dictionary, which together encapsulate the conditions under which the clause is definitely true. In practice, most clauses yield the tag representing true. Tags are combined when complex clauses are evaluated. For example, if evaluating clause c1 yields tag t1 and evaluating c2 yields t2, then evaluating and c1 c2 yields the tag t1 AND t2 (reduced to a canonical form).
When a clause is asserted to a database as a consequent of a rule, the assumption tag t1 determined by evaluating the antecedents is stored with the clause on the database. If the same clause has already been asserted to the database with tag t2, the combined tag t1 OR t2 replaces t2 on the database (unless the combined tag is the same as t2, in which case the assertion has no effect and dependents of the rule are not triggered). When a clause is retrieved from a database by an antecedent of a rule, the assumption tag is also retrieved and used to construct the assumption tag asserted with the rule's consequents. Thus, further deductions that can be made on the basis of assumptions are also made, but are tagged in case the assumptions turn out to be false.
Sometimes whether the subclause of an assumable clause is true may also be dependent on assumptions; i.e. evaluating the subclause may succeed with an assumption tag other than true. When evaluating an assumable clause with keyword notKnown, the disjunction of the assumption tags found by evaluating the subclause represents the conditions under which the assumable clause is false; this disjunction is known as a conflict tag. If the conflict tag is not true, then the assumable clause may be true so an assumption is generated and the conflict tag is remembered for later use.
Evaluating the subclause of an assumable clause with keyword total may yield many different values and corresponding assumption tags. The correct total will depend upon which assumption tags turn out to be true, so it is necessary to generate assumptions corresponding to every combination of assumption tags which may turn out to be true. If there are many different combinations then the mechanism is obviously inefficient, but this rarely occurs in practice.
The space overheads incurred by tagging every clause on a database are fairly small due to the use of a compact representation, and since tags are often true. Every database retrieval or assertion entails an "AND " or "OR " operation, but these operations are carried out relatively quickly.*2 The overheads of assumptions are far more significant when many deductions are made on the basis of false assumptions (see Section 5.4).
Generated with CERN WebMaker