Functional dependencies (FDs) are an integral part of database theory since they are used in integrity enforcement and in database design. Recently, functional dependencies satis¯ed by XML data (XFDs) have been introduced. In this work approximate functional dependencies that are XFDs approximately satis¯ed by a considerable part of the XML database are de¯ned and the problem of inferring such XFDs is addressed.
Traditionally, in order to guarantee data consistency, integrity constraints are essential [1, 14]. Among them, it is widely recognized that functional dependencies (FDs) are the most important and common semantic constraints encountered in databases.
In classical approach FDs are considered to be provided from database designers, but in several areas as data cleaning, data integration and data analysis, they may also be retrieved from the extensional data. The problem of extracting functional dependencies has been deeply addressed for relational databases [4, 11, 13] and recently investigated also with a data mining point of view [12]. Another important goal in the context of using FDs as knowledge to mine from data is to extract FDs that are not satis¯ed by all the database entries but from the majority of them [9, 10]. This allows the discovery of erroneous or exceptional elements in the data, that is very useful for data cleaning and data integration. Furthermore, this kind of FDs let us to identify constraints very frequent in the database that are meaningful for data analysis, even if they are not valid in the whole database.
Recently integrity constraints have been introduced also for XML data [2, 5{ 8, 15, 16]. In particular, in [2, 15] two de¯nitions of XML functional dependencies (XFDs) are given. Both these de¯nitions treat the equality between two XML elements as equality between their identi¯ers and they do not use the subtrees equivalence. Even if this approach can be useful for a database designer and for normalizing an XML database, it does not ¯t well when the FDs are unknown, and the goal is to extract them from the database. To this aim, in [16] a novel 3name 5book 1c3redits15year p17rofessor20semester 4"DSyasttaeb7"moaFfsso"eDu6antitdtalabetaiosness1"0 9auth8aourtho11ar21ust1h"4o3"r 16"2005"1"91R8noabmineson"2"1Spring" "Abiteboul""Hull" 1 ROOT faculty
60course 6n1ame 6b3ook 6c9redits71year 7p3rofessor76semester 6"2Programming"6t4itle 6a6uthors 7"05" 7"22007" 7n4ame 7"7Spring" 6"5C++ Primer" 6a7uthor 7"5Brown"
6"8Lippman" 4c0ourse
Fig. 1: UnivInfo XML Tree de¯nition for XML functional dependency, using subtree equivalence as element equivalence, is proposed and the problem of inferring XFDs from XML data is addressed. Nevertheless, authors do not deal with the problem to discover approximate XFDs.
The complex structure of XML data adds an interesting facet about the satisfaction of XFDs. In fact, whereas the satisfaction of an FD in a relational database is checked comparing values contained in the tuple of the database, the satisfaction of an XFD implies the tree comparison since each \tuple" of an XML database is composed by trees. Since tree structure is complicated and it can contain several subtrees, it can happen that two trees describe the same object, but their shape and content are slightly di®erent. In these cases, these trees invalidate the satisfaction of an XFD because their are not perfectly equal. Instead, it is very interesting and useful to evaluate how much trees are similar by means of a proper measure and then, if they are judged \enough" similar, the XFD is to be considered approximately satis¯ed. For example, consider the XML tree shown in Figure 1. Obviously, trees rooted at \book" elements 5 and 25 identify the same book, but they are not perfectly the same. In this case, checking the satisfaction of the XFD claiming that the name of a course implies the text book yields a negative answer using the approach proposed in [16], but in fact the XFD is satis¯ed.
Furthermore, in many cases, extracting functional dependencies that do not hold in the whole database, but in the majority of it, is very useful, as stated previously. For example, consider the XML tree in Figure 1 and the XFD claiming that the course name implies the number of credits. Such an XFD does not hold in the whole database, since for the course \Database Systems", the number of credits is \3" in \2005" and \4" in \2006". Therefore, using approach proposed in [16], such an XFD is not inferred, but, since the XFD almost always holds in the database, it is interesting and then should be extracted.
Finally, if no approximation is employed in checking XFD satisfaction, it could happen that some XFDs that in fact do not hold are extracted. For example, consider the XML tree shown in Figure 1 and the XFD claiming that professor implies the semester. Since all the professors are slightly di®erent from one another, this XFD holds if approach proposed in [16] is considered. Nevertheless, professor rooted at 17 is much similar to professor rooted at 35, and professor rooted at 55 is similar to professor rooted at 73, but since semesters are di®erent the XFD does not hold and it should not be extracted.
The aim of this work is the discovery of approximate functional dependencies on XML documents, namely the set of XFDs that are approximately satis¯ed by a given collection of XML data. We introduce a notion of approximate satisfaction of an XFD (¾-approximation) based on the dissimilarity measure between trees and we use this new concept for discovering XFDs ¾-approximately satis¯ed by a percentage of \tuples" of the XML database speci¯ed in advance. To the best of our knowledge this is the ¯rst work dealing with the discovery of approximate XFDs.
The rest of the paper is planned as follows. Section 2 provides some preliminary de¯nitions and the notation used in the paper. Section 3 presents the de¯nition of approximate XFDs. Section 4 addresses the inference problem. Finally, Section 5 draws the conclusions. 2
Let L be a countably in¯nite set of labels, S be a countably in¯nite set of strings and let ² 2= S denote the empty string.
De¯nition 1 (XML Tree). An XML tree is a quadruple T = hr; N ; V; ¸i, where N denotes the set of nodes, r 2 N denotes the root of T , V µ N £ N denotes the set of edges and ¸ : N ! L [ S is a function s.t. 8 ni 2 N , { ¸(ni) 2 L, if 9 (ni; n) 2 V; { ¸(ni) 2 S, otherwise
(ni is called element node) (ni is called text node)
In the rest of the paper, we assume that the XML tree is not recursive, that is there are no two nodes having the same label s.t. one of them is descendant of the other one.
De¯nition 2 (Path). A path is an expression of the form =l1= : : : =lk, where k ¸ 1 and { li 2 L, i 2 [1::k ¡ 1]; { lk 2 L [ f#textg De¯nition 3 (Path Pre¯x). Given two paths p = =l1= : : : =lk and p0 = =l10= : : : =lh0, p is a pre¯x of p0 i® k · h ^ li = li0 8i 2 [1; : : : ; k].
De¯nition 4 (Path Instance). Given a path p = =l1= : : : =lk and an XML tree T = fr; N ; V; ¸g, p matches on T i® there exists fn1; : : : ; nkg µ N s.t. the following conditions hold:
{ ¸(ni) = li; 8i 2 [1::k ¡ 1] { (¸(nk) = lk if lk 2 L
if lk = #text ¸(nk) 2 S { (ni; ni+1) 2 V; 8i 2 [1::k ¡ 1] In such a case, we say that ¼ = =n1= : : : =nk is a path instance of p in T , and nk is the ending node of ¼ in T .
For instance, considering Figure 1, =f aculty=course, =prof essor=name are paths, =f aculty=course=prof essor is a pre¯x of =f aculty=course=prof essor=name, and f=1=2=15g is a path instance of =f aculty=course=year, whereas f=1=2=15=16g is a path instance of =f aculty=course=year=#text.
De¯nition 5 (Ending Nodes Set). Let T be an XML tree, p = =l1= : : : =lk be a path, and ¦ = f¼1; : : : ; ¼hg be the set of all the path instances of p in T . The ending nodes set EN (p) = fm1; : : : ; mhg is the set of nodes of T s.t. each mi is the ending node of ¼i in T .
For example, consider the path p = =f aculty=course=name the ending nodes set of p is EN (p) = f3; 23; 41; 61g.
De¯nition 6 (Repeated Path). Let p and p0 be two paths. p0 is said to be a repeated path for p if p is a pre¯x of p0 and there exists at least one node n 2 EN (p) that is ancestor of at least two ending nodes of p0.
For example, =f aculty=course=book=authors=author is a repeated path for =f aculty=course=book=authors since there exists node 8 2 EN (=f aculty=course =book=authors) and there exist node 9 and 11, belonging to EN (=f aculty=course =book=authors=author), both descendants of 8.
De¯nition 7 (Root Path). Given an XML tree T = hr; N ; V; ¸i and a path p = =l1= : : : =lh, p is a root path w.r.t. T , i® l1 = ¸(r).
In the sequel of the paper, whenever we refer to paths we mean root paths.
In order to handle missing elements (nulls), the completion of XML trees is needed. Intuitively, given an XML tree T and a set of paths, an XML extended tree of T w.r.t. the set of paths is an XML tree completed with nulls so that each path of the set is matched.
Before de¯ning the extended tree, we give our notion of XML tree containment.
De¯nition 8 (Tree containment). Given an XML tree T = hr; N ; V; ¸i, an XML tree T 0 = hr; N [ ¨; V0; ¸0i contains T (T v T 0), if the following conditions hold: { ¨ = f?1; : : : ; ?kg is a set of marked nulls. { V0 ¶ V { ¸0(n) = ¸(n); 8n 2 N { ¸0(m) 2 L [ f²g; 8m 2 ¨ Last condition indicates that if a marked null represents an element then its label must belong to L, otherwise its label must be empty.
De¯nition 9 (Extended Tree). Let T be an XML tree and P the set of all paths of T . An XML tree T 0 = »(T ) is an extended tree of T if the following conditions hold: { T v T 0 { for each path p 2 P if there exists a path instance ¼ = =n1= : : : =nm of q in T 0, where q is a pre¯x of p and q 6= p, then there exists a path instance ¼0 = =n01= : : : =n0n of p in T 0 s.t. ni = n0i; i 2 [1::m].
T 0 = hr; N [ ¨ 0; V0; ¸0i is said to be minimal if there not exist an extended tree T 00 = hr; N [ ¨ 00; V00; ¸00i of T such that j¨ 00j < j¨ 0j. 3
In order to de¯ne approximate XFDs, two kinds of approximations are taken in account. The ¯rst one (¾-approximation) concerns the structural and content similarity between \tuples" (trees) involved in the satisfaction of XFDs, whereas the second one concerns the percentage of the whole database that ¾-approximately satis¯es the functional dependencies. Therefore, approximate XFDs are XFDs ¾-approximately satis¯ed by a large part of a given XML document. Intuitively, if two di®erent instances of the left part of an XFD are quite similar, then they can be considered as describing the same real-world entity. Thus, the correspondent instances of the right part have to represent the same entity, and then they must be similar, too.
The approach followed in this work needs neither a DTD nor an XML schema de¯ned on the document. Then, in order to single out \tuples" on which FDs have to be veri¯ed, an approach similar to that proposed in [15] is exploited. 3.1
Firstly, the formal de¯nition of XFD is given.
De¯nition 10 (XML Functional Dependency). Given an XML tree T , and two sets of paths fp1; : : : ; pmg and fq1; : : : ; qng of T , an XML functional dependency (XFD) is an expression of the form p1; : : : ; pm ! q1; : : : ; qn. The set fp1; : : : ; pmg (resp. fq1; : : : ; qng) is called left part (resp. right part) of the XFD. Since p1; : : : ; pm ! q1; : : : ; qn is equivalent to the set of XFDs
fp1; : : : ; pm ! q1; : : : ; p1; : : : ; pm ! qng w.l.o.g., in the following, we deal with XFDs whose right part contains only one path.
In order to establish which nodes have to be considered belonging to the same \instance" of an XFD, we recall the de¯nition of closest node as proposed in [15]. Note that the de¯nition is in a little di®erent form to match the setting of this work. De¯nition 11 (Closest Node). Given two paths p0 and p00, let p be the longest common pre¯x of p0 and p00. Let n0 and n00 be two nodes s.t. n0 2 E N (p0) and n00 2 E N (p00). n0 is a closest node of n00 (n0 k n00) i® there exists a node n 2 E N (p) s.t. n is an ancestor of both n0 and n00.
It follows that the above relation is symmetric, re°exive and intransitive. Note that, in general, for each node can exist more than one closest node for the same path.
Example 1. Consider the U nivInf o XML database in Figure 1 and paths p0 = =f aculty=course=name and p00 = =f aculty=course=prof essor=name. The longest common pre¯x between p0 and p00 is p = =f aculty=course. Consider nodes n0 = 3 2 E N (p0) and n00 = 18 2 E N (p00). n0 is a closest node of n00 since there exists a node n = 2 2 E N (p) that is a common ancestor of both 3 and 18. Let's now consider node n000 = 36 2 E N (p00). n0 is not a closest node of n000 since there not exists a node in E N (p) that is a common ancestor of both 3 and 36.
In order to group nodes representing an \instance" of an XFD we introduce the matching node set, that is formed by an ending node for each path contained in the XFD. Each node in the set is closest of all other nodes in the set. De¯nition 12 (Matching Node Set). Given an XML tree T and a set of paths P = p1; : : : ; pm, a matching node set of P in T is a set Mns (P ) = fz1; : : : ; zmg of nodes of »(T ) s.t. for each i; j 2 [1::m], zi 2 E N (pi) ^ zi k zj .
Note that, in the above de¯nition, the extended tree of T is employed. This is needed in order that each ending node of any path in P belongs to at least one matching node set. Indeed, if an incomplete tree were used, it could happen that for an ending node n of a path p 2 P there not exists an ending node n0 of an other path p0 2 P s.t. n k n0. Thus, n would not belong to any matching node set.
Given a set of paths P, a matching node set M of P and a path p 2 P, we denote as M p the node of M belonging to E N (p).
In order to deal with approximate XFDs, we need a way to evaluate when two distinct \instances" of an XFD have to be considered similar. Since the ending nodes are trees, we employ the tree edit distance [3] as similarity measure. Roughly, this kind of distance between two trees is based on the computation of sequences of edit operations needed to transform a tree in the other. The edit operations are node insertions, node deletions and node renamings. Each operation is associated with a cost and the cost of a sequence of edit operations is the sum of the costs of each operation composing the sequence. The tree edit distance is de¯ned as the cost of the sequence having minimum cost. De¯nition 13 (Tree Distance). Let T and T 0 be two XML trees and ' be a cost function. An edit script S between T and T 0 is a sequence of edit operations turning T into T 0. The cost of S is the sum of the costs of the operations in S employing '. The tree distance between T and T 0 is jT j + ins(T ; T 0) where S¤ is the edit script having minimum cost, cost indicates the cost of the edit script and ins denotes the number of node insertions necessary to transform T in T 0.
Note that the edit distance between two trees T and T 0 is normalized w.r.t. the sum of the size of T and the number of node insertions necessary to transform the former tree in the latter one.
Now, we employ the above concepts for measuring the distance between matching node sets.
De¯nition 14 (Mns Distance). Let P and P0 µ P be two sets of paths, and let M and Q be two matching node sets of P. The distance between M and Q w.r.t. P0 is
¹P 0 (M; Q) = maxp2P0 (±(M p; Qp)) 3.2
Now, XFDs approximately satis¯ed by an XML tree can be formally de¯ned.
De¯nition 15 (¾-approximation). Let f : P ! q be an XFD, T be an XML
tree, R be a set of matching node sets of (P [ fqg) in T and ¾ be a dissimilarity
threshold. R ¾-approximately satis¯es f (R j=¾ f ) if, for every two distinct
matching node sets M1; M2 2 R, it holds that
¹P (M1; M2) · ¾ ) ¹fqg(M1; M2) · ¾
(
In the following a set of matching node sets that ¾-approximately satis¯es an XFD is called solving set of the XFD.
Example 2. Consider the XML tree in Figure 1, the XFD f : =f aculty=course=name ! =f aculty=course=book and ¾ = 0:3. Consider the set of matching node sets of f=f aculty=course=name; =f aculty=course=bookg
R = ff3; 5g; f23; 25g; f41; 43g; f61; 63gg
The pairs judged to be similar on the left part of the XFD are (f3; 5g; f23; 25g),
(f3; 5g; f41; 43g). Since these pairs also satisfy the right side of implication (
Let's now consider f 0 : =f aculty=course=prof essor ! =f aculty=course=semester and the set of matching node sets of P = f=f aculty=course=prof essor; =f aculty =course=semesterg
R = ff17; 20g; f35; 38g; f55; 58g; f73; 76gg
The pair (f17,20g,f35,38g) satis¯es the left side of implication (
Given an XFD f , several solving sets can be extracted from a document and some of these, called maximal solving sets, have maximum cardinality. More formally, a solving set R is said maximal if there not exists another solving set R0 s.t. jRj < jR0j. Note that can exist more than one maximal solving set. The value of the cardinality of a maximal solving set is exploited to compute the percentage of the whole database that satis¯es f .
Now, the formal de¯nition of approximate XFD satisfaction can be given. De¯nition 16 (Approximate Satisfaction of an XFD). Let f : P ! q be an XFD, T be an XML tree, ¾ be a dissimilarity threshold and µ be a satisfaction threshold. Let R be the set of all the matching node sets of P [ fqg in T and R0 be a maximal solving set. T (¾; µ)-approximately satis¯es f (T j=µ¾ f ) if Example 3. Consider XML tree in Figure 1 again, suppose ¾ = 0:3 and µ = 0:7 and consider the XFD
f : =f aculty=course=name ! =f aculty=course=credits The matching node sets of f=f aculty=course=nameg[f=f aculty=course=creditsg are
M1 = f3; 13g; M2 = f23; 31g; M3 = f41; 51g; M4 = f61; 69g Let R = fM1; M2; M3; M4g be the set of all the matching node sets. In order to valuate the con¯dence of f we have to compute the solving sets. It can be easily seen that the subsets R0 = fM2; M3; M4g and R00 = fM1; M4g are solving sets since they satisfy f . Note that, for example, M1 and M2 can not belong to the same solving set since their distance w.r.t. =f aculty=course=name is 0 < ¾ but their distance w.r.t. =f aculty=course=credits is 1 > ¾, and then they violate f . The maximal solving set is R0. Since jR0j=jRj = 3=4 = 0:75, then T (¾; µ)-approximately satis¯es f . 4
In this section, we formally de¯ne the problem of inferring approximate XFDs from an XML document.
Not all the XFDs approximately satis¯ed by an XML document need to be inferred, since some of them are deducible from others without any computations and some others are not interesting.
Consider, for example, the XML tree T in Figure 1, ¾ = 0:3, µ = 0:7, and the following subset of XFDs (¾; µ)-approximately satis¯ed by T :
F = f=faculty=course=name ! =faculty=course=book;
=faculty=course=name; =faculty=course=year ! =faculty=course=book;
=faculty=course=name; =faculty=course=year ! =faculty=course=year;
=faculty=course=name ! =faculty=course=book=title;
=faculty=book ! =faculty=course=name;
=faculty=book=title ! =faculty=course=name;g
(
It is easily to see that only (
Thus, to avoid functional dependencies that are trivially satis¯ed or nonsigni¯cative, we give a de¯nition of meaningless XML functional dependencies. De¯nition 17 (Meaningless XFDs). Let T be an XML tree and f : fp1; : : : ; pkg ! q be an XFDs. f is said to be trivial if one of the following conditions holds: 1. there exists i 2 [1::k] s.t. pi = q. 2. there exist i; j 2 [1::k]; j 6= i s.t. pi is a pre¯x of pj ;
In the ¯rst case, the XFD is always satis¯ed, thus is needless to be considered in the XFD inference phase. In the second case, the XFD is not signi¯cative since the information contained in pj is redundant.
In order to reduce the number of XFDs to be examined, we introduce a precedence relation between XFDs.
De¯nition 18 (XFDs Precedence). Let T be an XML tree and f : fp1; : : : ; phg ! q and f 0 : fp01; : : : ; p0kg ! q0 be two XFDs. f precedes f 0 (f Á f 0) if one of the following conditions holds: 1. q = q0, k > h and 8i 2 [1::h]; pi = p0i; 2. q is a pre¯x of q0, k = h and 8i 2 [1::h]pi is a pre¯x of p0i.
In particular, if f is (¾; µ)-approximately satis¯ed then f 0 is also (¾; µ)-approximately satis¯ed in the ¯rst case, whereas f 0 is needless to be inferred in the second case.
Then, the goal is to extract a set of functional dependencies that is minimal in according to the following de¯nition: De¯nition 19. Let F be a set of non-meaningless XFDs, F is minimal if
Now, the task of inferring XFDs approximately satis¯ed by an XML tree can be formally presented.
De¯nition 20. Given an XML tree T , a dissimilarity threshold ¾ and a satisfaction threshold µ, the XFD inference problem is the extraction from T of the minimal set F of XFDs, such that 8f 2 F f is (¾; µ)-approximately satis¯ed by T (T j=µ¾ F ).
Due to lack of space, we omit the algorithm solving the XFD inference problem.
In this paper we de¯ned approximate XFDs, namely XFDs approximately satis¯ed (according to tree similarity) by a certain part of an XML document. Furthermore, we addressed the problem of inferring approximate XFDs from data.