Dependency Calculus Reasoning in a General Point Relation Algebra

1 The Dependency Calculus

Reasoning about complex dependencies between events is a crucial task. However, qualitative reasoning has so far concentrated on spatial and temporal issues. In contrast, we present a calculus [Ragni and Scivos, 2005], a proper generalization of the nonlinear relation algebra, created for speci�c questions of reasoning about consequences.

This algebra, called dependency calculus (DC), meets all requirements to describe dependencies in networks. There are two aspects: dependencies of points are described by the point algebra PAdc, and of intervals by the associated interval algebra IAdc. For these we analyze questions concerning the satisfaction problems, and show the correspondence to other relation algebras. For this, we use an isomorphism preserving the tractability of subclasses. This method promises to structure the �eld of relation algebras and to transfer algebraic aspects and complexity results from one algebra to another.

If we observe pollution in an ecosystem of �owing water, we can draw conclusions about pollution at other points (cf. Fig. 1). If pollution is found at D, F is polluted as well. It

might be caused from a source at A, but not B, C, or E. If C is polluted, D probably is also polluted. Does the same hold true for B and D? No: they have no common point upstream. DC directly represents such differences. For pairs like (C,D) or (D,E), we have the new �fork� relation (⋏). The relations

�fork�, �before�, �equal�, and �after� are called �dependent�. The other case, like (A,B), is called �independent� (≍). A medical problem is given in Fig. 2.

Figure 2: A virus transmittance scheme. Arrows indicate direction of assured, dashed of unassured donorship, dotted lines mean that both persons carry the same virus. No lines means that we do not have prior knowledge. The situation on the left must be incomplete. The existence of a fourth person D accounts for this. PAdc concludes that indeed there was indirect transmittance from D to A.

If x, y are points in a partial order 〈T,≤〉, then we de�ne these relations in terms of the partial order as follows:

x ≺ y iff x ≤ y and not y ≤ x. x = y iff x ≤ y and y ≤ x. x ≻ y iff y ≤ x and not x ≤ y. x⋏y iff ∃z z ≤ y∧z ≤ x and neither x ≤ y nor y ≤ x. x ≍ y iff neither ∃z z ≤ y∧z ≤ x nor x ≤ y nor y ≤ x .

All relations between nodes in Fig. 1 can be described by these �ve basic relations.

2 Computational Complexity

Assume that a set of constraints between some points is given. One question is whether this set is consistent. Is it possible to construct a network in which all constraints are satis�ed? This problem is called PAdc-SAT. What is the computational effort to construct such a network?

De�nition 1. For two relation algebras Γ,Γ′ a homomorphism is a function γ from Γ to Γ′ such that γ preserves all operations of the boolean algebra and for all relations R, S:

• (converse): γ (R-1) = γ (R)-1
• (composition): γ(R◦S)= γ(R)◦γ(S)

De�nition 2. For two relation algebras Γ,Γ′ a tractabilitypreserving-homomorphism (tph) is a homomorphism γ from Γ to Γ′ such that each subset β⊆Γ is tractable iff γ(β) ⊆Γ′ is tractable. An isomorphic tph is called tpi.

Lemma 1. A tpi γ from PAdc to RCC-5 (Fig. 3) is given by:

The relations including {=} are contained in τ28, τ20, τ14 iff R\{=} is in τ28 (τ20,τ14). All relations including {=} are in τ17.

With [Renz and Nebel, 1999] and Lemma 1, we get:

Theorem 1. PAdc-SAT is NP-complete.

Theorem 2. The four classes τ28,τ20,τ17,τ14 (cf. Tab. 1) are the only maximal subclasses of PAdc.

3 The Associated Interval Algebra

There are applications in which it is not suf�cient to compare single points in a network. For instance, pollution in a pipe network is not restricted to single points but extends to whole sections, and automated planning and project management deal with tasks that span over time intervals.

De�nition 3. An interval I = [sI , eI ] is a pair of points satisfying sI ≺ eI . The interval algebra IAdc is the relation algebra generated by quadruples of relations as basic relations

closed under ∩, ∪,- , ◦,-1 . For I = [s, e] and I ′ = [s′ ,e′ ], being in relation I R I ′ means sRss s′ , sRse e′ , eRes s′ , and eRee e′ .

IApo is analogically de�ned, based on {≺,=,≻,{≍,⋏}}.

If Rss =Rse = Res =Ree =: R′ , we write (R′ ). Fig. 4 and Fig. 5 show advantages of the new, �ner interval calculus: More situations can be distinguished and more conclusions are possible. The situation given in Fig. 4 is described by: A (≺) A1, A1 (≺)C, A2 (≺)C, B (≺)C,

By specifying the latter relation, e.g. to A1 ( ≍ ≺ ≺ =) A2 , new conclusions can be drawn, in this case, A (≺) A2 becomes impossible. This means, if B is an obstacle on the path from A to C via A1, then there is no alternative route via A2.

For a set of IAdc constraints, we de�ne IAdc-SAT analogically to PAdc-SAT. How hard is it to decide the satis�ability?

Theorem 3. IAdc-SAT is NP-hard.

De�nition 4. For a subset S ⊆ PAdc, a relation R is called S-pointizable if it belongs to the class

A gadget for an IAdc relation R is a set of points p1, . . . , pm (m ≥ 4) with PAdc relations that are satis�able iff [p1, p2]R[p3, p4] is satis�able. For S ⊆ PAdc, an IAdc relation R is called S-gadgetable (R ∈ GS) if all PAdc relations between the endpoints extended with additional points are relations of S . G is an abbreviation for GPAdc and P for PPAdc .

Theorem 4. G,P are intractable subclasses of IAdc.

Not all gadgetable relations are pointizable. For instance, (≺)∪(≻) is gadgetable. Hence, B ⊊P ⊊G ⊊ IAdc. If S is tractable (in PAdc), then PS is tractable in IAdc. What about the larger class GS? Is it still tractable?

Theorem 5. If R is a class of S-gadgetable IAdc relations and the satis�ability problem over S is tractable, then the satis�ability problem over R is tractable.

Corollary 1. B,Gτ28 ,Gτ20 ,Gτ17 ,Gτ14 ⊊ IAdc are tractable. Corollary 2. IAdc-SAT is NP-complete.

4 Conclusion

We presented and investigated a new algebra for reasoning about causal relations. Both PAdc and IAdc are NP-complete, and we identi�ed tractable subclasses. Promising ideas for future work are introducing probabilities to this calculus to model reasoning in Bayesian networks and the temporalization of DC for modeling dependencies that vary over time.