Multi-Adjoint Logic Programming and FLOPER

We will introduce the elements of multi-adjoint logic programming (MALP). MALP will serve as semantic foundation of our proposal. Moreover, MALP will be used for the implementation of our language. The section will describe the theoretical basis of MALP: multi-adjoint lattices and fuzzy operators defined on them. In addition, it will be described an instance of MALP which considers a multi-adjoint lattice of trees with truth values, and operators defined for such lattice. Finally, we will describe the rule-based implementation of our fuzzy XPath by using MALP rules.

Multi-Adjoint Logic Programming
In multi-adjoint logic programming [MOV04,JMP09], we work with a first order language, L, containing variables, function symbols, predicate symbols, constants, quantifiers (∀ and ∃), and several arbitrary connectives such as implications (←₁, ←₂, …, ←_m), conjunctions (&₁, &₂, …, &_k ), disjunctions (∨₁, ∨₂, …, ∨_l), and general hybrid operators ("aggregators" @₁, @₂, …,@_n), used for combining/propagating truth values through the rules, and thus increasing the language expressiveness. Additionally, our language L contains the values of a multi-adjoint lattice in the form 〈 L, ≼, ←₁, &₁, …, ←_n, &_n 〉, equipped with a collection of adjoint pairs 〈 ←_i, &_i 〉 where each &_i is a conjunctor intended to the evaluation of modus ponens. A rule is a formula “A ←_i B with α”, where A is an atomic formula (usually called the head), B (which is called the body) is a formula built from atomic formulas B₁, …, B_n (n ≥ 0 ), truth values of L and conjunctions, disjunctions and general aggregations, and finally α ∈ L is the “weight” or truth degree of the rule. The set of truth values L may be the carrier of any complete bounded lattice, as for instance occurs with the set of real numbers in the interval [0,1] with their corresponding ordering ≤. Consider, for instance, the following program P composed by three rules with associated multi-adjoint lattice 〈 [0,1], ≤, ←_P,&_P 〉, where label P mean for Product logic with the following connective definitions: "←_P(x,y) = min(1,x/y)", "&_P(x,y)= x * y" and "|_P(x,y)= x+y−x * y". 

In order to describe the procedural semantics of the multi–adjoint logic language, in the following we denote by C[A] a formula where A is a sub-expression (usually an atom) which occurs in the –possibly empty– one hole context C[] whereas C[A/A′] means the replacement of A by A′ in context C[], and mgu(E) is the most general unifier of an equation set E. The pair 〈 Q; σ 〉 composed by a goal and a substitution is called a state. So, given a program P, an admissible computation is formalized as a state transition system, whose transition relation  ↝ ^AS   is the smallest relation satisfying the following admissible rules:

1) 〈 Q[A];σ 〉  ↝ ^AS   〈 (Q[A/v&_iB])θ;σθ 〉 if A is the selected atom in goal Q, 〈 A′←_iB;v 〉 in P, where B is not empty, and θ = mgu({A′= A}).

2) 〈 Q[A];σ 〉  ↝ ^AS   〈 (Q[A/v])θ;σθ 〉 if 〈 A′←_i;v 〉 in P and θ = mgu({A′= A}).

The following derivation illustrates our definition (note that the exact program rule used -after being renamed- in the corresponding step is annotated as a super–index of the  ↝ ^AS   symbol, whereas exploited atoms appear underlined):  

〈p(X);{}〉	1
〈0.8 &P (q(X1,Y 1) |P r(Y 1));{X∕X1}〉	2
〈0.8 &P (0.9 |P r(Y 2));{X∕a,X1∕a,Y 1∕Y 2}〉	3
〈0.8 &P (0.9 |P 0.7);{X∕a,X1∕a,Y 1∕b,Y 2∕b}〉

The final formula can be directly interpreted in the lattice L to obtain the fuzzy computed answer or f.c.a., in brief. So, since 0.8 &_P (0.9 |_P 0.7) = 0.8 * (0.9 + 0.7 - (0.9 * 0.7)) = 0.776, we say that goal p(X) is true at a 77.6 % when X is a.

MALP and Fuzzy XPath
MALP can be used as basis of our proposed flexible extension of XPath as follows. The idea is to consider MALP as semantic background for fuzzy queries expressed in XPath. With this aim we have to accommodate MALP truth values and connectives to XML documents, RSVs, fuzzy operators and structural/thresholding constraints.

TV trees
Firstly, we have to consider a suitable multi-adjoint lattice. The elements of the multi-adjoint lattice represent the truth values. In the context of XPath, truth values are trees of truth values, which we call TV trees. They represent the RSV associated to each node of the XML tree. From a theoretical point of view, the evaluation of a given goal w.r.t. a MALP program, will return a TV tree as the result of the computation.

A TV tree is an ordered tree of real numbers in the interval [0,1]. Let T the set of TV trees, and ≼_N the order of real numbers; we can define the following order between TV trees; t₁ ≼_T t₂ iff root(t₁) ≼_N root(t₂) and for each s ∈ descendants(t₂) there exists v ∈ descendants(t₁) such that s ≼_T v, where root(t) (resp. descendants(t)) denotes the root (resp. the descendants) of the tree t. Since TV trees are ordered trees, descendants of a given node are ordered, that is, descendants(s) is actually a sequence.

Now, we can define the following operations in the set T. The operation &_O^T(t₁,t₂), O ∈ {P,G,L} is defined as the tree with root &_O(root(t₁),root(t₂)) and descendants the elements of descendants(t₁) ⊕ descendants(t₂), where &_O is the corresponding operator over real numbers, and ⊕ is the concatenation of sequences. The operation ←_O^T(t₁,t₂), O ∈ {P,G,L} is defined as the tree with root equal to ←_O(root(t₁),root(t₂)) and descendants the elements of {x ∈ descendants(t₁) | x ≼_T u, ∀u ∈ descendants(t₂) }, where ←_O is the corresponding operator over real numbers.

Our goal now is to prove that TV trees conforms a multi-adjoint lattice defined as follows.

Definition 1.

Let (L,≼) be a lattice. A multi-adjoint lattice is a tuple:

〈 L, ≼, ←₁, &₁, …, ←_n, &_n 〉

such that:

• (L,≼) is complete, namely, ∀S ⊂ L, ∃ inf(S), sup(S). Then, it is a bounded lattice, i.e. it has bottom and top elements, denoted by T and ⊥, respectively.
• (&_i, ←_i) is an adjoint pair in (L,≼), i.e.:
  • &_i is increasing in both arguments, for all i, i=1,...,n
  • ←_i is increasing in the first argument and decreasing in the second, for all i.
  • x ≼ (y ←_i z) if and only if (x &_i z) ≼ y, for any x,y,z ∈ L (adjoint property).
• T&_i v = v &_i T = v for all v ∈ L, i=1,...,n, where T = sup(L).

TV trees are a multi-adjoint lattice based on truth values over [0,1]. The following theorem proves this result. We will use the following proposition.

Proposition 1. 〈[0,1], ≼_N, ←_P,&_P,←_G,&_G,←_L,&_L 〉 is a multi-adjoint lattice.

Theorem 1. 〈T, ≼_T, ←_P^T,&_P^T,←_G^T,&_G^T,←_L^T,&_L^T 〉 is a multi-adjoint lattice.

• Let S ⊂ T, then inf(S) is the tv tree with root inf(V) where V={v | v=root(s), s ∈ S} (inf(V) exists by proposition 1) and descendants ⊕_{s ∈ S}descendant(s). Now, inf(S) ≼_T s, for all s ∈ S: for all v ∈ descendant(s), there exists v ∈ ⊕_{s ∈ S}descendant(s), v ≼_T v, and root(inf(S))≼_T root(s). Analogously, sup(S) is the tv tree with root sup(V) where V={v | v=root(s), s ∈ S} (sup(V) exists by proposition 1) and descendants ∅. Now, s ≼_T sup(S), for all s ∈ S given that root(s)≼_T root(sup(S)).
  The top element of T is the tree with one node of value 1 without descendants, and the bottom is the tree with root of value 0 and descendants the set T.
• • &_O^T, O ∈ {P,G,L} is increasing by proposition 1: whenever and v ≼_T s, v′≼_T s′ then root(v) &_O root(v′) ≼_N root(s) &_O root(s′), and for all t ∈ descendants(s) and t′ ∈ descendants(s′) there exists k ∈ descendants(v) and k′ ∈ descendants(v′) such that k ≼_T t and k′≼_T t′. Therefore v &_O^T v′≼_Ts &_O^T s′
  • ←_O^T, O ∈ {P,G,L} is increasing in the first argument and decreasing in the second; let us see the first case: increasing in the first argument; let v ≼_T s be then by proposition 1 root(v) ←_O root(t) ≼_N root(s) ←_O root(t) for all t; in addition, for each x ∈ descendants(s) there exists k ∈ descendants(v) such that k ≼_T x; thus, when x ∈ descendants(s) and x ≼_T u, ∀u ∈ descendants(t) then k ≼_T x ≼_T u, ∀u ∈ descendants(t); and therefore v ←_O^T t ≼_T s ←_O^T t. Let us see the second case: decreasing in the second argument; let s ≼_T v be then by proposition 1 root(t) ←_O root(v) ≼_N root(t) ←_O root(s) for all t; in addition, for each x ∈ descendants(v) there exists k ∈ descendants(s) such that k ≼_T x; thus, when b ∈ descendants(t) and b ≼_T u, ∀u ∈ descendants(s) then b ≼_T k ≼_T x; and this happens for each x ∈ descendants(v), thus t ←_O^T v ≼_T t ←_O^T s.
  • x ≼_T (y ←_O^T z) if and only if (x &_O^T z) ≼_T y:
    (⇒):
    By proposition 1 we have that if root(x) ≼_N (root(y) ←_O root(z)) then (root(x) &_O root(z)) ≼_N root(y); let a in descendants(y), then we have two cases: there exists u ∈ descendants(z) such that u ≼_T a; and the case in which none of the u ∈ descendants(z) satisfies u ≼_T a, and thus, by hypothesis, there exists b ∈ descendants(x) such that b ≼_T a, and thus in both cases (x &_O^T z) ≼_T y.
    (⇐):
    By proposition 1 we have that if (root(x) &_O root(z)) ≼_N root(y) then root(x) ≼_N (root(y) ←_O root(z)); let a in descendants(y ←_O^T z) then a ∈ descendants(y) and a ≼_T u for all u ∈ descendants(z); therefore, by hypothesis, there exists u ∈ descendants(x) such that x ≼_T a; and therefore x ≼_T (y ←_O^T z).
• T&_O^T v = v &_O^T T = v taking as T = Sup(T) the tv tree with node 1 and without descendants.

Fuzzy XPath will be grounded in multi-adjoint logic programming with TV trees as truth values, Product, ukasiewicz and Gödel operators, and two extra hybrid operators, particularly, @avg and @fuse.
MALP rules with TV trees
Now, we would like to show how TV trees are used for representing computations of results in our fuzzy variant of XPath, and how MALP rules are used for computing results from XPath expressions.

• XML documents are represented with MALP terms, which are identical to Prolog terms. MALP represents XML trees with a term of the form:
  element(tag,attributes,descendantnodes)

  
  
  where tag is the root of the tree, attributes is a list of attribute values, and descendantnodes is a list of descendant nodes (i.e. XML terms in MALP). For instance, the example of Figure 2 is represented with the MALP term of Figure 4.

  
  Figure 4: Example represented in MALP
• XPath expressions are also represented as MALP terms, particularly, with a MALP list. For example, /hotel/services/pool is represented by [hotel,services,pool], where some elements of the list can be also either a list (for nested XPath expressions), or an attribute name, or a fuzzy expression. Such expressions are represented by a MALP term of the form btree(op,xpath,xpath).
• TV trees are represented as MALP terms of the form:
  
  tv(truthvalue,[nodecontent,siblingtv,descendanttv])

  where truthvalue is the truth value of the current node, nodecontent is the content of the node when it is include in the answer of the query, siblingtv is the TV tree of the first sibling node, and descendanttv is the TV tree of the first descendant node. We have to remark the following consideration: TV trees are trees of truth values, according to the definition of previous section, however TV trees in MALP include the content of the selected nodes in order to make easier the implementation. Moreover, TV trees in MALP are represented as binary trees. Figure 5 shows an example of TV tree computed by the fuzzyXPath predicate for the query: <</hotel[[DEEP=0.5;DOWN=0.9]//close_to/text()="Gran Via"]/@name>>.

  Figure 5: Example of a tv structure in MALP

  tv(1.0,[[tv(1.0, []), [Melia]], [], tv(1.0,[[tv(0.5, []), [NH]], [], tv(1.0,[[tv(0.5, []), [Hilton]], [], tv(1.0,[[tv(0.25, []), [Tryp]], [], tv(1.0,[[tv(0.45, []), [Sheraton]], [], []])])])])])

   
• Now, a MALP predicate called fuzzyXPath that takes as input (a) an XML tree represented by a MALP term, (b) an XPath expression represented by a list, and (c) DEEP and DOWN values as TV trees (by default they are tv(1,[]). It returns the TV tree associated to the query. The definition of the predicate distinguishes cases with regard to the XPath expression to be evaluated. Such MALP predicate basically traverses the XML tree represented by the MALP term, and recursively computes for each node the associated RSV.
  For instance, Figure 6 shows the case in which the current root matches with the current path. We can see that &_P^T is used as fuzzy operator, to compute DEEP and DOWN values for each recursive call. In addition, ←_P^T is used as implication connective, and @fuse is an hybrid operator used for re-building the answer. The weight of the MALP rules is always tv(1,[]).
  Figure 6: Example of MALP rule

  fuzzyXPath ([Label - LabelRest], [element(Label,_,Children) - Siblings],Deep, Down) ←PT                   @fuse (                      tv(1,[element(Label, Attr, Children), [], []]),                      &PT(Deep, fuzzyXPath(LabelRest, Children, Deep, Down)),                      &PT(Down, fuzzyXPath([Label - LabelRest], Siblings, Deep, Down))                    ) with tv(1,[])

  Figure 7 shows the case of MALP rules for evaluating avg, where fuzzy conditions are handled by a predicate called execute_fcond. A call to this predicate returns a truth-value (i.e., a tv tree) like the one depicted in Figure 5.

  Figure 7: Examples of MALP rules for evaluating conditions

  fuzzyXPath([Label,btree(A,B,C)],[element(Label,Attr,Children) - Siblings], Deep, Down) ←PT                   @fuse(                   execute_fcond(Label, btree(A,B,C), element(Label,Attr,Children)),                   &PT(Down, fuzzyXPath([Label, btree(A,B,C)], Siblings, Deep, Down))                  ) with tv(1,[]) execute_fcond(Label, btree(avg, T1, T2), element(Label,Attr,Children)) ←PT                       @avg(                       execute_fcond(Label, T1, element(Label,Attr,Children)),                       execute_fcond(Label, T2, element(Label,Attr,Children))                     ) with tv(1,[])