| A transitive relation is a relation such as "taller," where a pair of relations can imply a third relation. For example, if Alan is taller than Britta, and Britta is taller than Chuck, then Alan is taller than Chuck. This kind of relation differs from, say, "owes a favor to," which is not transitive. If Alan owes Britta and Britta owes Chuck, Alan may or may not owe Chuck. The "owes a favor to" relation is not transitive. A common transitive relation is "in." If A is in B and B is in C, then A is in C. This is true, for example, of boxes and geographical places. It is tempting to write, for transitive relations, a rule such as the following: in(A, C) :- in(A, B), in(B, C); // wrong If this rule is in a program, a query such as in(box1, X) will loop. When the rule tries to prove the first structure in its body, in(A = box1, B) , this structure finds the rule again. Because B is unbound at this point, the rule tries to prove itself again in the same way, and the program loops indefinitely. One way to model transitive relations is to distinguish between something being "directly in" and something being "transitively in" something else. For example, Figure 13.10 models the relations of a few geographic areas. This program uses the functor in to signify that one place is directly in another, and uses within to model that one place is either directly or indirectly in another place. Figure 13.10. The in program. The idea of "in" is a transitive relation, so if Menzingen is in Zug and Zug is in Switzerland, then Menzingen must be in Switzerland. The query here finds every known place that contains no other place.  With this program in place, a query of within(X, us) produces these results: X = colorado X = maine X = texas X = kentucky X = virginia X = englewood X = fortCollins X = westbrook X = yarmouth X = austin X = lexington X = richmond no This query finds both cities and states in the United States. The query in Figure 13.10 finds only the towns or cities in the program. The query uses the leaf rule, which finds elements that are in other elements and screens out elements that contain some other element. 13.11.1 Symmetric Relations A symmetric relation is one in which a relation of a to b implies that the same relation holds from b to a . For example, if a is married to b , then b must be married to a . You might have a fact about marriage such as: married(george, jane); Given only this fact, the query married(jane, george) will fail because there is no fact for this query to match. It is tempting to write the rule: married(A, B) :- married(B, A); // wrong This rule satisfies the query married(jane ," george) , but it loops for other types of queries, such a query for two names that do not appear in a married fact. For example, the query married(george, astro) finds the married rule and tries to prove married(astro , george) . When this structure tries to prove itself, it finds the married rule again and tries to prove married(george , astro) . This proof will go on happily ever after. The solution is to introduce another relation to query: couple(A, B) :- married(A, B); couple(A, B) :- married(B, A); A query to the couple rules cannot loop because both rules refer to married facts. For example, if a program contains the couple rules and the single fact that george is married to jane , then a request for the rest of the proofs of couple(jane, X) displays X = george no The query couple(george, astro) displays simply no |
