Approximating the DTD of a set of XML documents

Approximating the DTD of a set of XML documents Alberto Abell´o Dept. de Llenguatges i Sistemes Inform`atics Universitat Polit`ecnica de Catalunya Xavier de Palol Dept. de Llenguatges i Sistemes Inform`atics Universitat Polit`ecnica de Catalunya Mohand-Sa¨ıd Hacid LIRISUFR d’Informatique Universite Claude Bernard Lyon 1 March 8, 2005 Abstract The WWW contains a huge amount of documents. Some of them share the subject, but are generated by different people or even organizations. To guarantee the interchange of such documents, we can use XML. This allows to share documents that do not have the same structure. However, it makes difficult to understand the core of such heterogeneous documents (in general, schema is not available). In this paper, we offer a characterization and algorithm to obtain the midpoint (in terms of a resemblance function) of a set of semi-structured, heterogeneous documents without optional elements. The trivial case of midpoint would be the common elements to all documents. Nevertheless, in cases with several heterogeneous documents this may result in an empty set. Thus, we consider that those elements present in a given amount of documents belong to the midpoint. Once we have such midpoint, the algorithm is generalized for the obtaining of repetitions and optional elements. Thus, a exact schema can always be found generating optional elements. However, the exact schema of the whole set may result in overspecialization (lots of optional elements), which would make it useless. 1 Introduction The web is a powerful medium for human communication and dissemination of information. Consequently, the web has become a popular knowledge base, where people add documents (private, educational and organizational) and navigate through its content. The rapid growth of information makes it sheer impossible to find, organize, access and maintain the information as the users require. There is a clear need for the web to become semantically richer. The aim of this semantic enrichment of the web is to enhance web searches and to introduce logical reasoning on the web contents [EL02]. The general trend towards Semantic Web (SW) is the use of ontologies to incorporate such semantics to existing and new documents. For scalability reasons, one important aspect of SW consists in distilling the existing documents and extract valuable knowledge from them. There exist multiple formats for information sources, ranging from unstructured data to highly structured. The term semi-structured data has emerged to describe data that has some structure but neither regular, nor known a-priori to the system. It is precisely for this reason that semi-structured documents are self-describing. 1 The importance of knowing the structure (or schema) of a set of documents have been largely described in the literature. For example, [BGM04] outlines its importance on integrating and analyzing structure of the WWW. On the other hand, [ABS00] points out that a known structure would also facilitate the storage (by compressing and exploiting the commonalities) and it would also encourage the queries on these commonalities. It is key to improve the access methods to the data, thus availing query optimization. Moreover, one could use the structure to derive a new ontology or identify (map) the concepts in the documents into an existing ontology; an ontology establishes a common vocabulary for a given domain, which can be used to data interchange among companies. Ontologies are also used for documentation purposes, since they provide an structured view of a domain. Here we consider a certain kind of semi-structured data, in particular, XML documents. XML has been adopted as standard for data interchange, availing the integration of heterogeneous information sources. A well-formed XML document is a document that conforms to the XML syntax rules in [W3C04] (roughly, markups nest properly and attributes are unique). Moreover, a valid XML document is a document that is well-formed and also conforms to the rules of its DTD. A DTD contains the declarations that provide a grammar for a class of documents. It determines the elements and attributes that appear in a document, i.e., the name, type and constraints on every element and attribute. As defined in [W3C04], an XML document primarily consists of a nested hierarchy of elements with a single root. Elements can contain character data (concepts) and child elements, where both can have attributes.Child elements consist either of a sequence list of elements or a choice list of elements. The standard states that elements in a sequence must be ordered. From a practical point of view, an application deals better with a well-known structure and a fixed appearing order, but in general the order of the different subelements among them is not relevant, that is, we can change the order of these subelements without changing the meaning of the overall document. In fact, many interfaces have been developed to access and manipulate an XML document (probably the most popular ones are DOM1and SAX2), and most of them do not consider the order among subelements. The choice construct in a DTD indicates that one, and only one, element in the choice list of contents should appear in the document. The choice construct is the key to find a perfect typing. In the rare case that all the documents belong to the same class and use the same terms, the choice construct is not needed to find a perfect typing. Otherwise, in a grammar that lacks the choice construct we cannot find a common schema, so we have to approximate it. Such approximated schemas are called inexact schemas, whose usefulness was already pointed out in [Wid99]. If we use the choice construct, finding the schema is reduced to find the best grammar expression for each element (for example following a normal form like [AGW01]), so that all elements in the document belong to the corresponding grammar. Nevertheless, a perfect schema, one DTD that is followed by all the documents, may arise an overspecialization problem. Some works have overcome overspecialization by using clustering techniques to approximate typing [NAM98, SPBA03]. We aim at finding a common schema for a set of correct semi-structured documents. We take an inexact approach based on the resemblance of documents, thus using the structure similarity among the documents under study. We call this common schema the midpoint. We use the resemblance family of functions in [BGM04], which take into account extra elements both in the document and in the DTD. We could then redefine valid XML document as a document whose resemblance to its DTD is above a given threshold. The main contribution of this paper is the characterization of the midpoint in terms of a resemblance function and offer an efficient algorithm to obtain it. Although our approach 1http://www.w3.org/DOM 2http://www.saxproject.org/ 2 deals with DTDs, it also applies to XML schemas. The structure of the paper is as follows. In the next section we review the work related with our method. Section 3 presents the formalization of XML into DL that we propose. Section 4 characterizes the midpoint. Section 5 shows an efficient algorithm to obtain the midpoint. Section 6 shows how to deal with optional and repeated elements. Finally, section 7 gives the general conclusions and points out our future work. 2 Related work As pointed out in [Wid99], everything needs to scale to web proportion. However, human mind cannot. Nobody would catch at once the essence of thousands of documents. Some kind of schema (i.e. either structured or semistructured) should be available, summarizing the contents of every set of documents. Thus, several authors worked on the generation of DTDs from XML data. A relevant result is [NAM98], which explains how we can get a well structured schema (i.e. not a DTD) approximating the documents. [JOKA02] describes an implementation of an algorithm to generate a DTD followed by an XML document. [SPBA03] classifies the documents in different classes and gets one DTD per class of documents. This is a good solution if there are a few classes with not many documents or elements each. However, it may result in lots of different classes or optional elements for every class, if we are dealing with a huge amount of heterogeneous documents. On the other hand, [NAM98] pays attention to inexact schemas, outlining that the size of a perfect typing may be the order of the data set, prohibiting its use for query optimization and interfaces. Therefore, we are not searching a perfect typing but a human-friendly, computationally-tractable, and graphically-representable approximation. To this end, we should use some kind of resemblance or distance. The first option would be tree edit distance (like in [BdR04]), but it results in high complexity (see [ZS89]). Therefore, the most promising option is that of structure similarity. [NAM98] uses Manhattan distance (i.e. the number of different descendants/ancestors of two elements), and explains that there are several domain dependent ways to weight it. [BB95] shows different resemblance measures. Among those, [SPBA03] uses |elem(d1)∩elem(d2)| max(|elem(d1)|,|elem(d2)|)(being d1and d2two documents), while [BGM04] uses |elem(d1)∩elem(d2)| |elem(d1)∩elem(d2)|+α·|elem(d1)\elem(d2)|,β·|elem(d2)\elem(d1)|). We took this last measure, because it is more general, and allows to distinguish lack of elements in one side or another. Regarding costs, that of [NAM98] is quadratic for its first step and NP-hard (approximated by a logarithmic greedy algorithm) for its second one. On the other hand, obtaining the schema of every class in [SPBA03] (which corresponds to a exact DTD for all documents in the class) is linear in the number of elements in the representatives, while finding the class of every document is worse case quadratic in the number of documents (we may need to check every document against every other document). 3 Formalizing XML documents by means of Description Logics As we can see in [ABS00], an XML document uses to be thought as a rooted tree. A rooted tree is an acyclic graph (N,E), that has no more than one root. Nis a set of nodes and Ea set of edges. An edge eis an ordered pair of nodes 3 (nsource,ntarget). A node is a leaf, if it is not the source of any edge in E. Along this paper we will use Description Logics (DL) notation to formalize those trees. Since we only take into account element tags, we are not actually interested in XML documents, but in a restricted class of DTDs that can be automatically generated from one XML document. The problem tackled in this paper is that of finding a DTD from a set of XML documents. Nevertheless, for the sake of simplicity, from here on, we will use the DTDs corresponding to the documents instead of the documents themselves. We assume that we have a DTD exactly matching each document. The DTD of a document can be obtaining just parsing it and eliminating data (leaving element tags). Thus, these DTDs cannot contain choice, nor unnumbered repetitions, nor optional elements, nor any, because from one document we are not able to infer such structures. How could we know based only on one document that a present element may not be present? How could we decide that there is a possibly infinite repetition? Regarding XML attributes, they could be used to match different element tags. For example, “<a ID=’Id1’>” should be identified with “<b ID=’Id1’>” in spite of the different tag name. Nevertheless, that is not the aim of this paper. Representing the information either as an attribute or a child is just a design choice. Thus, from here on, without loss of generality, we will consider XML attributes as XML child elements without further nesting structure. As stated in [W3C04], child elements are ordered. Order is an important characteristic for documents. However, in databases unordered data can be processed more efficiently, so it uses to be considered in that way (for example in DOM and SAX). Therefore, we will assume that order is not relevant in our case. [CLN98] already showed the usefulness of DL on conceptual modeling. Thus, we will consider a set of documents as a knowledge base, which comprises two components, i.e. TBox (the terminology, we could recognize it as the schema) and ABox (the assertions about individuals, or instances). As explained in [BCM+03], the TBox contains concepts, and to define a formal semantics of the logic we use an interpretation I. An interpretation is a pair [∆I,·I], where ∆Iis the domain (a non-empty set), and ·Iis an interpretation function that assigns to every atomic concept Aa set (AI⊆∆I) and to every atomic role ra binary relation (rI⊆∆I×∆I). Inductively, this is extended to non-atomic concepts by the following definitions (where Cand Dare concepts, and ris a role): ⊥I=∅ >I= ∆I (CuD)I=CI∩DI (∃r.C)I={a∈∆I| ∃b. (a, b)∈rI∧b∈CI} document 1: <a><b><c>Hello</c></b><d><e>Bye</e></d></a> document 2: <a><b></b><d></d></a> document 3: <a><d><e>Bye</e></d></a> document 4: <a><d><e>Bye bye</e></d></a> dtd1=∃a.(∃b.∃c.>u∃d.∃e.>) dtd2=∃a.(∃b.⊥u∃d.⊥) dtd3=∃a.∃d.∃e.> dtd4=∃a.∃d.∃e.> element: C (concept) child element:∃r.C (existential quantification) sequence:u(conjunction) PCDATA or String:>(top) EMPTY :⊥(bottom) Figure 1: DL representation of an XML document As exemplified in figure 1, we will represent a document or piece of document by a concept “C”. An unordered sequence 4 of pieces of documents will be represented by a conjunction “CuD”. Data types (i.e. PCDATA and string) will be represented by the top concept “>”, while an empty element (i.e. EMPTY ) will be represented by bottom concept “⊥”. Finally, children will be represented by means of existential quantification “∃element.C”. Actually, existential quantification allows the presence of more than one element of the same kind. Nevertheless, as stated before, we do not consider such repetitions by now (see section 6.2 for the treatment of repetitions). We did not use a formalization of XML documents like that in [CDL99] because it does not allow to reason. There, different kinds of elements are represented in the ABox, at the instance level, while reasoning algorithms needed work at the conceptual level. Our formalization allows the usage of DL algorithms like “Subsumption” and “Least Common Subsumer”: Subsumtion (also known as “Query Containment” in other areas and noted “CvD”, if Cis subsumed by D) shows whether one concept is more general than another (i.e. one set contains the other for all interpretations). For example, dtd1vdtd3. CvD⇔ ∀I :CI⊆DI Least Common Subsumer (“LCS” from here on) results in the subsumer of a set of concepts that is subsumed by any other subsumer of the set of documents. LCS uses to be applied to learning from examples, and bottom-up construction of knowledge bases. For example, lcs(dtd2, dtd4) = ∃a.∃d.>. L=lcs(C1, .., Cn)⇔ ∀i:CivL∧@D: (∀i:CivD∧DvL) 4 Characterization of the midpoint Given a set of DTDs, we would like to find the DTD that has the maximum number of common elements wrt the set, at the same time that minimizes the elements being in the DTD not in the documents and those in the documents not in the DTD. We will call such DTD the midpoint of the set. In order to characterize the midpoint, we will use the resemblance family of functions used in [BGM04]. r: (DT D, setOfDT Ds)7→ [0,1] r(C, E) = wc(C, E) wc(C, E) + α·wp(C, E) + β·wm(C, E)for α, β ∈R+ By instantiating αand βwe get the concrete function we would like to use (notice that only if α=βthe resemblance will be symmetric). Positive real values can be assigned to these parameters. They weight the importance of finding plus (elements in some DTD that do not appear in the midpoint) and minus (elements in the midpoint that do not appear in some DTD) elements respectively. The function relies now on three simpler ones that obtain respectively the size of common, plus, and minus elements. It is interesting to notice that the sum of common and plus elements corresponds to the size of all DTDs independently of the concept we are obtaining the distance to. wc(C, E) = X dtd∈E size(lcs(C, dtd)) wp(C, E) = X dtd∈E (size(dtd)−size(lcs(C, dtd))) 5 wm(C, E) = X dtd∈E (size(C)−size(lcs(C, dtd))) ∀C:wc(C, E) + wp(C, E) = X dtd∈E size(dtd) Any result in this paper does not depend on how we compute the size of a DTD. We only impose that the size of a DTD is smaller than the size of adding an element to that DTD. Therefore, from here on, in the examples we will assume that every element contributes to the size of a DTD with one unit independently of its position in the document. For example, size(dtd1) = 5 and size(dtd2) = size(dtd3) = 3. A general, more complex and accurate algorithm for obtaining the size of a DTD is given in [BGM04]. r(∃a.∃d.>,{dtd2, dtd3}) = 4 4+2α+0β=4 4+4 r(∃a.∃d.∃e.>,{dtd2, dtd3}) = 5 5+α+β=5 5+2+3 r(∃a.(∃b.>u∃d.>),{dtd2, dtd3}) = 5 5+α+β=5 5+2+3 r(∃a.(∃b.>u∃d.∃e.>),{dtd2, dtd3}) = 6 6+0α+2β=6 6+6 Figure 2: Example of multiple midpoints At this point, it is also important to notice that there may exist more than one DTD maximizing the resemblance (i.e. more than one midpoint). For example, let be α= 2 and β= 3. In this case, r(∃a.∃d.>,{dtd2, dtd3}) = r(∃a.∃d.∃e.>,{dtd2, dtd3}) = r(∃a.(∃b.>u∃d.>),{dtd2, dtd3}) = r(∃a.(∃b.>u∃d.∃e.>),{dtd2, dtd3}), as we can see in figure 2. Since this is the maximum resemblance, we can choose the midpoint of {dtd2, dtd3}among those four DTDs. As stated by theorem 1, one of the possible midpoints of the set can be obtained by a conjunction of LCS of the documents. Theorem 1. Given a set of DTDs E = {dtd1,...,dtdn}, and being Bibranches of the form ∃r1 Bi.∃r2 Bi...∃rli Bi.>with li≥1 ∃S1, ..., Sp∈P(E) : ∀B1, ..., Bq:r(l i=1..q Bi, E)≤r(l j=1..p lcs(Sj), E) Proof. By hypothesis, let’s suppose that there is a concept M=di=1..m Bithat maximizes the resemblance and it is not a conjunction of LCSs. We will divide the proof in three steps: EC={dtd ∈E|dtd vC} Step 1: ∀i= 1..q :EBi6=∅ Let’s suppose not, i.e. ∃i= 1..q :EBi=∅. We can remove the last kexistentials from it until there exists some DTD dwith a branch matching B0 i(being B0 i=∃r1 Bi.∃r2 Bi...∃rli−k Bi.>). Now, dvB0 i. Let be M0= B1u... uBi−1uB0 iuBi+1 u... uBq. It is easy to see that wc(M, E) = wc(M0, E), wp(M, E) = wp(M0, E), and wm(M, E)≥wm(M0, E). Thus, r(M, E)≤r(M0, E) which means they are equal (if β= 0) or contradicts the hypothesis. Therefore, we can assume that ∀i= 1..q : EBi6=∅. 6 Step 2: Biis exactly a branch of lcs(EBi) Let’s suppose not, because the corresponding chain of existentials in lcs(EBi) is longer than Bi(notice that it can never be shorter, by definition of the LCS). Let’s call BLto ∃r1 Bi.∃r2 Bi...∃rli Bi...∃rli+k BL.>so that it is a branch of lcs(EBi). Let be M0=B1u... uBi−1uBLuBi+1 u... uBq. Notice that ∀dtd ∈E\EBi:size(lcs(dtd, BL)) = size(lcs(dtd, Bi)), because if exists a DTD with a branch B0so that BLvB0@Bi, by definition it belongs to EBi. Therefore, it is easy to see that: wc(M0, E) = wc(M, E)+ |EBi| ·(size(BL)−size(Bi)) wp(M0, E) = wp(M, E)+ |EBi| ·(size(Bi)−size(BL)) wm(M0, E) = wm(M, E)+ |E\EBi| ·(size(BL)−size(Bi)) By hypothesis, r(M, E)≥r(M0, E). Thus, wc(M, E) wc(M, E) + α·wp(M, E) + β·wm(M, E) ≥ wc(M, E)+ |EBi| ·(size(BL)−size(Bi)) (wc(M, E) + α·wp(M, E) + β·wm(M, E)) + (|EBi| −α|EBi|+β|E\EBi|)·(size(BL)−size(Bi)) Let be B0 i=∃r1 Bi.∃r2 Bi...∃rli−1 Bi.>. Since, by hypothesis, Biis not exactly a branch of any DTD, ∀dtd ∈E\EBi: size(lcs(dtd, B0 i)) = size(dtd, Bi)). Therefore, defining M00 =B1u... uBi−1uB0 iuBi+1 u... uBq: wc(M00, E) = wc(M, E)+ |EBi| ·(size(B0 i)−size(Bi)) wp(M00, E) = wp(M, E)+ |EBi| ·(size(Bi)−size(B0 i)) wm(M00, E) = wm(M, E)+ |E\EBi| ·(size(B0 i)−size(Bi)) and given that by hypothesis r(M,E) is the maximum: wc(M, E) wc(M, E) + α·wp(M, E) + β·wm(M, E) ≥ wc(M, E)− | EBi| ·(size(Bi)−size(B0 i)) (wc(M, E) + α·wp(M, E) + β·wm(M, E)) −(|EBi| −α|EBi|+β|E\EBi|)·(size(Bi)−size(B0 i)) However, both inequalities cannot be possible at the same time, because size(BL)−size(Bi) and size(Bi)− size(B0 i) are both positive numbers. Therefore, the hypothesis is not true and Bimust be exactly a branch of lcs(EBi). Step 3: Mvlcs(EBL) As before, let be M0=B1u... uBi−1uBLuBi+1 u... uBq. We already showed that r(M, E)≤r(M0, E) wc(M, E) wc(M, E) + α·wp(M, E) + β·wm(M, E) ≤ wc(M, E)+ |EBi| ·(size(BL)−size(Bi)) (wc(M, E) + α·wp(M, E) + β·wm(M, E)) + (|EBi| −α|EBi|+β|E\EBi|)·(size(BL)−size(Bi)) Being a, b, c, d ∈R+\ {0}:a b≤a+c b+d⇔a b≤c d. Therefore, wc(M, E) wc(M, E) + α·wp(M, E) + β·wm(M, E) ≤ |EBi| ·(size(BL)−size(Bi)) (|EBi| −α|EBi|+β|E\EBi|)·(size(BL)−size(Bi)) = |EBi| |EBi| −α|EBi|+β|E\EBi| In our case, functions (i.e. wc,wp, and wm) are always positive (which makes aand balso positive). If a(i.e. wc) is zero, inequality is still true, because any other DTD would never worsen the resemblance. On the other hand, b(i.e. wc(M, E) + α·wp(M, E) + β·wm(M, E)) being zero means that E=∅(we do not have any DTD). In some cases, depending on αand β,d(i.e. |EBi| −α|EBi|+β|E\EBi|) may be negative or zero. If so, 7 it is easy to see that r(M, E)≤r(M0, E), which would contradict the hypothesis. Therefore, from here on, we can assume that |EBi| −α|EBi|+β|E\EBi|is strictly positive. Let’s suppose that B0 Lis branch of lcs(EBL) so that ¬(MvB0 L). Let be M00 =B1u... uBquB0 L, and Bj=lcs(M, B0 L). wc(M00, E) = wc(M, E) + X dtd∈E (size(lcs(B0 L, dtd)) −size(lcs(Bj, dtd))) wp(M00, E) = wp(M, E) + X dtd∈E (size(lcs(Bj, dtd)) −size(lcs(B0 L, dtd))) wm(M00, E) = wm(M, E) + X dtd∈E (size(B0 L)−size(Bj)−size(lcs(B0 L, dtd)) + size(lcs(Bj, dtd))) Therefore, r(M, E)≤r(M00, E)⇔r(M, E)≤wc(M00, E)−wc(M, E) wc(M00, E)−wc(M, E) + α·(wp(M00, E)−wp(M, E)) + β·(wm(M00, E)−wm(M, E)) wc(M00, E)−wc(M, E) wc(M00, E)−wc(M, E) + α·(wp(M00, E)−wp(M, E)) + β·(wm(M00, E)−wm(M, E)) =Pdtd∈E(size(lcs(B0 L, dtd)) −size(lcs(Bj, dtd))) (1 −α)·(Pdtd∈E(size(lcs(B0 L, dtd)) −size(lcs(Bj, dtd)))) + β·(Pdtd∈E(size(B0 L)−size(Bj)−size(lcs(B0 L, dtd)) + size(lcs(Bj, dtd)))) =1 (1 −α) + β·(Pdtd∈E(size(B0 L)−size(Bj)) Pdtd∈E(size(lcs(B0 L,dtd))−size(lcs(Bj,dtd))) −1) =1 (1 −α) + β·(|E|·(size(B0 L)−size(Bj)) Pdtd∈E(size(lcs(B0 L,dtd))−size(lcs(Bj,dtd))) −1) =1 (1 −α) + β·(|E| Pdtd∈E size(lcs(B0 L,dtd))−size(lcs(Bj,dtd)) size(B0 L)−size(Bj) −1) Since B0 L@Bj, then ∀dtd ∈E\EBj:lcs(B0 L, dtd)) = lcs(Bj, dtd). Therefore, 1 (1 −α) + β·(|E| Pdtd∈E size(lcs(B0 L,dtd))−size(lcs(Bj,dtd)) size(B0 L)−size(Bj) −1) =1 (1 −α) + β·(|E| Pdtd∈EBj size(lcs(B0 L,dtd))−size(lcs(Bj,dtd)) size(B0 L)−size(Bj) −1) Moreover, ∀dtd ∈EBj:lcs(Bj, dtd) = Bj,∀dtd ∈EB0 L:lcs(B0 L, dtd) = B0 L, and ∀dtd ∈EBj\EB0 L:size(B0 L)> size(lcs(B0 L, dtd)) > size(Bj). Therefore, 1 (1 −α) + β·(|E| Pdtd∈EBj size(lcs(B0 L,dtd))−size(lcs(Bj,dtd)) size(B0 L)−size(Bj) −1) ≥1 (1 −α) + β·(|E| |EBj|−1) =1 (1 −α) + β|E\EBj| |EBj| Finally, since |EBj|≥| EB0 L|≥| EBL|=|EBi|, then 1 (1 −α) + β|E\EBj| |EBj| ≥1 (1 −α) + β|E\EBi| |EBi| |EBj| |EBj| −α|EBj|+β|E\EBj| ≥ |EBi| |EBi| −α|EBi|+β|E\EBi| ≥wc(M, E) wc(M, E) + α·wp(M, E) + β·wm(M, E) Therefore, if adding Biimproves the resemblance, adding Bjimproves the resemblance even more. So, every branch of lcs(EBL) subsumes M, which means that Mvlcs(EBL). 8 Lemma 2. There exists a DTD of the form dk=1..p lcs(Sk)maximizing the resemblance, so that ∀1≤i, j ≤p: (Si* Sj). Proof. If ∃i, j :Si⊂Sj, then ∀dtd ∈E:lcs(dk=1..p lcs(Sk), dtd) = lcs(dk=1..j−1lcs(Sk)udk=j+1..p lcs(Sk), dtd) and size(dk=1..p lcs(Sk)) = size(dk=1..j−1lcs(Sk)udk=j+1..p lcs(Sk)). Therefore, r(l k=1..p lcs(Sk), E) = r(l k=1..j−1 lcs(Sk)ul k=j+1..p lcs(Sk), E) Corollary 3. There exists a DTD of the form dk=1..p lcs(Sk)maximizing the resemblance, so that p≤ |E| |E| 2! 5 Obtaining the midpoint of a set of DTD First of all, it is important to notice that depending on the values of αand βthere are some trivial cases (as shown in table 1). If α= 0, we do not mind having extra elements in the DTDs wrt the midpoint. Therefore, among the multiple solutions to the problem, we find ∃element.>(where “element” is the most frequent root element in the documents). If β= 0, we do not mind having extra elements in the midpoint wrt every individual DTD. Therefore, ddtd∈Edtd is among the solutions. Both equaling zero means that just by matching some elements in some DTD we get maximum resemblance (i.e. ∀wc6= 0 : wc wc+0wp+0wm= 1). Thus, from here on, we will only consider the non-trivial case where α6= 0 and β6= 0. Midpoint β= 0 β6= 0 α= 0 any ∃element.> α6= 0 ddtd∈Edtd ? Table 1: Trivial cases on finding a midpoint In this section we analyze three different possibilities to obtain the midpoint of a set of DTDs. Section 5.1 explores the behaviour of a blind search in the space of candidate DTDs. Section 5.2 tries to get benefit from the knowledge of the structure of the midpoint by restricting the search to those DTDs being LCS of some DTDs. Finally, section 5.3 shows how we could find the midpoint just looking at the number of appearances of each element. 5.1 Blind search The first possibility to find the midpoint of a set of documents is generating the whole search space and compare every point to the documents until we find the maximum resemblance. Firstly, as we can see in figure 3, we need to get all elements in the set of documents, which needs linear time on the number of elements (assuming there is a small number of children or they are ordered). After that, we need to generate all possible points in the search space (i.e. the parts of the set of elements), which is exponential in the 9 W DT D ={[∃a.>,4],[∃a.∃b.>,2],[∃a.∃b.∃c.>,1],[∃a.∃d.>,4],[∃a.∃d.∃e.>,3]} M4=∃a.(∃b.>u∃d.∃e.>)t(∃a.(∃b.∃c.>u∃d.∃e.>)) E1={dtd2, dtd3, dtd4};E2={dtd1} r(M4, E) = wc(M1 4,E1)+wc(M2 4,E2) wc(M1 4,E1)+wc(M1 4,E2)+α·(wp(M1 4,E1)+wp(M1 4,E2))+β·(wm(M1 4,E1)+wm(M1 4,E2)) =9+5 9+5+α·(0+0)+β·(3+0) =14 17 Figure 11: Improvement reducing plus elements of the document). In this case, we decided to pick elements up sorted by “#appearance ·size(element)”, because it increases resemblance faster (minimizing the number of elements in the midpoint). What really matters is that only branches with less than mappearance are returned (those of higher appearance already belong to the midpoint). Figure 11 shows how we can improve the resemblance. In figure 8, we stopped the iteration before adding those branches appearing only one time. Therefore, m= 1 and the next branch to be added is “∃a.∃b.∃c.>”. Thus, we get a new midpoint being the disjunction of two parts, and we calculate the resemblance taking into account the best part for each document. In this way, denominator does not change, while numerator increases, improving resemblance. 6.1.2 Reducing minus element s (those in the midpoint, not in the documents) Notice that, by using the algorithm in figure 10 we do not modify wm(which may not be zero after the second phase). Thus, in general, we will not reach the maximum resemblance, because the midpoint contains non-optional elements that are not present in all documents. The more heterogeneous the documents are, the worse will be the result, if we try to obtain only one midpoint. In order to solve this, we should divide the documents into several classes, and obtain separately the midpoint of each of these classes. In this way, at the extreme, each of these midpoints would only contain elements that are present in all its corresponding documents. The midpoint of the whole set of documents will be the disjunction of these partial midpoints Mi. Therefore, we should detect the presence of different clusters of documents, and treat them separately. We may trigger this phase of the algorithm, if after the third phase we did not reach the target resemblance; we may also trigger it, if we cannot reach the target resemblance after a given number of iterations of phase three (i.e. a given number of optional elements); or if wp wmafter phase two is below a threshold; or we may even trigger it based on the number of appearances of elements at first level (i.e. if |E| getMaxW eight(W DT D)is above a threshold). For this clustering, we may use an algorithm like “k-means” which is considered to need linear time (see [ECY00]). If we take k=|E|, the problem becomes trivial taking M=Fdtd∈Edtd. Therefore, we are looking for a small kso that maximizes r(M, E). For example, we could assume that there should be, at least, |E| getMaxW eight(W DT D)different kinds of documents, and generate such number of optional blocks of elements. Figure 12 sketches the algorithm. In our case, we could benefit from the existence of “WDTD” to improve performance, if it keeps the sets of documents that contain every branch instead of just counting them. We can codify every set Eias a list of bits b1b2..b|E|, where bit jshows whether the corresponding DTD contains the branch or not (dtdjvbranch). In this way, we could take krandom disjoint chains of bits as seeds (si) for “k-means”. Then, we can find the midpoint corresponding to each seed by running the second phase of our algorithm on “WDTD” using the corresponding mask of bits. Finally, we could also get the resemblance from each DTD to one midpoint also going through “WDTD” one 16 Choose kinitial seeds (may be randomly) do Assign each document to its nearest center For each cluster get a new center while (centers changed) Figure 12: K-means algorithm more time (by keeping all |E|resemblances in memory). Figure 13 shows an example for clustering documents into two sets, and how this improves the resemblance. As initial seeds, we take odd and even documents (i.e. {dtd1, dtd3}vs {dtd2, dtd4}). For each one of them, we obtain the midpoint (i.e. “∃a.(∃b.∃c.> u ∃d.∃e.>)” and “∃a.(∃b.> u ∃d.∃e.>)” respectively) by applying the algorithm in figure 7, anding the corresponding seed to the sequence of bits of each branch in “WDTD”. Obtaining the resemblance of each document to both midpoints, we see that “dtd3” is in the wrong class, because its resemblance to the midpoint of even documents is bigger, while it is an odd one. Therefore, we perform a second iteration with one cluster for “dtd1” and another one for the rest of the documents. This time, we detect that “dtd2” is in the wrong class, we move it and perform the third iteration. Now every document is in the right class, so we have finished. The midpoint of Eis the disjunction of both midpoints, and overall resemblance improves by reducing the denominator. It is easy to see that with three clusters we had obtained the exact DTD. Notice also that all resemblances can be obtained from WDTD, by crossing only once it in parallel with the corresponding midpoint. For example, let’s see how to obtain in the first iteration of figure 13 the resemblances from “∃a.(∃b.> u ∃d.∃e.>)” to each document (i.e. “r(M2, dtd1)”, “r(M2, dtd2)”, “r(M2, dtd3)”, and “r(M2, dtd4)”). At the first step, we would take “∃a.>” that belongs to the midpoint. Since the sequence of bits indicates that it belongs to the four documents, it would increase all four common elements counters (i.e. wc(M2, dtd1), wc(M2, dtd2), wc(M2, dtd3), and wc(M2, dtd4)). At the second step, we would take “∃a.∃b.>” that also belong to the midpoint. Since the sequence of bits indicates that it belongs to the first two documents, it would increment common elements of these and minus of the others (i.e. wc(M2, dtd1), wc(M2, dtd2), wm(M2, dtd3), and wm(M2, dtd4)). At the third step, we would take “∃a.∃b.∃c.>” that does not belong to the midpoint. Since the sequence of bits indicates that it belongs only to the first document, it would just increment plus elements of this (i.e. wp(M2, dtd1)). We would follow this way for the other two elements in “WDTD”. 6.2 Repeated elements It is possible that the same element appears at different places (i.e. different levels, or just having a different parent) in the same document (or even in different documents). If we consider that in this case all elements share the same DTD internal structure independently of their position in the document, we should start a previous process to find the midpoint of such element (i.e. we should consider it a whole document, get its internal structure, and treat it as a black box). This section does not deal with this kind of repetitions, but with one element that contains several others of the same kind in a sequence. First of all, on talking about repetitions, it is important to distinguish between unnumbered repetitions (i.e. +in XML notation) or numbered repetitions (i.e. a fixed number of children of the same kind). The point is that we cannot decide that there exists an unnumbered repetition without human participation. How could we decide (based 17 W DT D ={[∃a.>,{1111}],[∃a.∃b.>,{1100}],[∃a.∃b.∃c.>,{1000}],[∃a.∃d.>,{1111}],[∃a.∃d.∃e.>,{1011}]} Iteration 1: s1= 1010, s2= 0101 W DT D1={[∃a.>,{1010}],[∃a.∃b.>,{1000}],[∃a.∃b.∃c.>,{1000}],[∃a.∃d.>,{1010}],[∃a.∃d.∃e.>,{1010}]} M1 0=>2 2β≥0 M1 1=∃a.∃d.∃e.>1 2β≥6 8α+3·2β M1 2=∃a.(∃b.∃c.> u ∃d.∃e.>)0 2β<8 8α+5·2β W DT D2={[∃a.>,{0101}],[∃a.∃b.>,{0100}],[∃a.∃b.∃c.>,{0000}],[∃a.∃d.>,{0101}],[∃a.∃d.∃e.>,{0001}]} M2 0=>2 2β≥0 M2 1=∃a.∃d.>1 2β≥4 6α+2·2β M2 2=∃a.(∃b.> u ∃d.∃e.>)0 2β<6 6α+4·2β r(M1, dtd1) = 5 5+0α+0βr(M2, dtd1) = 4 4+1α+0β r(M1, dtd2) = 3 3+0α+2βr(M2, dtd2) = 3 3+0α+1β r(M1, dtd3) = 3 3+0α+2βr(M2, dtd3) = 3 3+0α+1β r(M1, dtd4) = 3 3+0α+2βr(M2, dtd4) = 3 3+0α+1β Iteration 2: s1= 1000, s2= 0111 W DT D1={[∃a.>,{1000}],[∃a.∃b.>,{1000}],[∃a.∃b.∃c.>,{1000}],[∃a.∃d.>,{1000}],[∃a.∃d.∃e.>,{1000}]} M1 0=>1 1β≥0 M1 1=∃a.(∃b.∃c.> u ∃d.∃e.>)0 1β<5 5α+5·1β W DT D2={[∃a.>,{0111}],[∃a.∃b.>,{0100}],[∃a.∃b.∃c.>,{0000}],[∃a.∃d.>,{0111}],[∃a.∃d.∃e.>,{0011}]} M2 0=>3 3β≥0 M2 1=∃a.∃d.>2 3β≥6 9α+2·3β M2 2=∃a.∃d.∃e.>1 3β<8 9α+3·3β r(M1, dtd1) = 5 5+0α+0βr(M2, dtd1) = 3 3+2α+0β r(M1, dtd2) = 3 3+0α+2βr(M2, dtd2) = 2 2+1α+1β r(M1, dtd3) = 3 3+0α+2βr(M2, dtd3) = 3 3+0α+0β r(M1, dtd4) = 3 3+0α+2βr(M2, dtd4) = 3 3+0α+0β Iteration 3: s1= 1100, s2= 0011 W DT D1={[∃a.>,{1100}],[∃a.∃b.>,{1100}],[∃a.∃b.∃c.>,{1000}],[∃a.∃d.>,{1100}],[∃a.∃d.∃e.>,{1000}]} M1 0=>2 2β≥0 M1 1=∃a.(∃b.> u ∃d.>)1 2β≥6 8α+3·2β M1 2=∃a.(∃b.∃c.> u ∃d.∃e.>)0 2β<8 8α+5·2β W DT D2={[∃a.>,{0011}],[∃a.∃b.>,{0000}],[∃a.∃b.∃c.>,{0000}],[∃a.∃d.>,{0011}],[∃a.∃d.∃e.>,{0011}]} M2 0=>2 2β≥0 M2 1=∃a.∃d.∃e.>1 2β≥6 6α+3·2β M2 2=∃a.∃d.∃e.>0 2β<6 6α+3·2β r(M1, dtd1) = 5 5+0α+0βr(M2, dtd1) = 3 3+2α+0β r(M1, dtd2) = 3 3+0α+2βr(M2, dtd2) = 2 2+1α+1β r(M1, dtd3) = 3 3+0α+2βr(M2, dtd3) = 3 3+0α+0β r(M1, dtd4) = 3 3+0α+2βr(M2, dtd4) = 3 3+0α+0β M= (∃a.(∃b.∃c.>u∃d.∃e.>)) t(∃a.∃d.∃e.>) E1={dtd1, dtd2};E2={dtd3, dtd4} r(M, E) = wc(M1, E1) + wc(M2, E2) wc(M1, E1) + wc(M2, E2) + α·(wp(M1, E1) + wp(M2, E2)) + β·(wm(M1, E1) + wm(M2, E2)) =8+6 8+6+α·(0 + 0) + β·(2 + 0) =14 16 Figure 13: Clustering the documents on a finite set of finite documents) that there is a possibly infinite repetition of elements? We cannot. Therefore, we should decide a priori if we are interested on generating numbered or unnumbered repetitions. If we want to generate numbered repetitions, we should just consider that each sibling element is a completely different one and we can use again the same algorithms. For example, in order to be able to treat the XML document “<a><b>brother</b><b>sister</b></a>”, we should translate it into ∃a.(∃b1.>u∃b2.>). This would work specially well for ordered elements, because their position indicates which sibling they are. In the example, the first one would always be identified as b1, and the second as b2. Doing it this way, a different position indicates different internal structure. If we are treating unordered documents, repeated elements result in undistinguishable twins with the same intensional internal structure. Otherwise, if they have a different schema, there is a design problem in the document. Even when dealing with semi-structured data, two elements of the same (undistinguishable) class should share the same (semistructured) schema. Thus, we have two different problems. The first one is deciding when there exists a unnumbered repetition, and the second is how to find the internal structure of the repeated elements. 18 To be able to handle repeated elements, we should modify the parser of XML documents that generates the DTDs. If the parser finds a repetition it should use a special mark showing the presence of sibling elements, and indicating the number tof them existing in the corresponding parent. Since XML documents are deep-first written, we would visit the children before we know the number of twins. Therefore, we should keep in memory the branches of each DTD, to generate t. In order to decide whether there is a repetition or not, if the first phase of the algorithm in figure 7 finds the mark, “branch” and “branch+” should both be increased in “WDTD”. During the second phase, on adding “branch+”, we should remove “branch” from M. Notice that the appearance of “branch” will always be higher than that of “branch+”, because we always increase the counter of the first, while only increase the latter if there is a repetition. Regarding the problem of finding the internal structure of repeated elements, we treat the subelements in only one pass. When, during the first phase of the algorithm, we find a subelement in any of the repetitions, we should just increase the counter of the corresponding branch in 1 t, where tis the number of twins. By doing this, we avoid overweighting the subelements of repetitions, and keep the basic idea of the algorithm still true (i.e. a child cannot appear more times in the documents that its parent). document 5: <a><b>Single</b></a> document 6: <a><b>Twin2</b><b> T win1</b></a> document 7: <a><b>PlainTwin</b><b><c>ComposedTwin</c></b></a> W DT D ={[∃a.>,3],[∃a.∃.b.>,3],[∃a.∃b+.>,2],[∃a.∃b.∃c.>,0.5]} Figure 14: Example of documents with repetitions Figure 14 exemplifies how repetitions should be treated by the algorithm. In this case, “∃a.>” weights three, because appears in three documents. The same happens for “∃a.∃.b.>”, because three documents contain such branch. Moreover, there are two documents containing repetitions of “b”, which is recorded by the appearance of “∃a.∃b+”. Finally, “∃a.∃b.∃c.>” appears once in one document. Nevertheless, it is part of a repetition of two twins. Therefore, its weight is 1 2= 0.5. 7 Conclusions and future work Along this paper, we have studied the possibility of approximating the schema (DTD) of a set of XML documents. Based on a given measure of resemblance, we are able to find the midpoint of the set. This midpoint have been characterized in terms of conjunction of Least Common Subsumers of the documents. Moreover different algorithms (of different costs) have also been presented to obtain it. We begun by considering only a restricted class of DTDs (without repetition nor choice), and it has been generalized to any DTD. Thus, we are able to approximate the schema as much as we want to the set of documents (eventually until we get an exact matching) in linear time. In order to get integrated access to several XML sources, first of all we should guarantee that a given element uses the same tag name everywhere, i.e. they share the same vocabulary. Therefore, as future work, we plan to deal with the problem of matching tag names, where ontologies can be used. The presence of optional elements in the schema may lead to the identification of equivalent tags from different sources. 19 Acknowledgements Our work has been partially supported by the Spanish Research Program PRONTIC and FEDER under project TIC2002-00744. References [ABS00] Serge Abiteboul, Peter Buneman, and Dan Suciu. Data on the Web - From Relations to Semistructured Data and XML. Morgan Kaufmann, 2000. [AGW01] J¨urgen Albert, Dora Giammarresi, and Derick Wood. Normal Form algorithms for extended Context-Free Grammars. Theoretical Computer Science, 267(1-2):35–47, 2001. [BB95] Vladimir Batagelj and Matevz Bren. Comparing resemblance measures. Journal of Classification, 12(1):73– 90, 1995. [BCM+03] Franz Baader, Diego Calvanese, Deborah McGuinness, Daniele Nardi, and Peter Patel-Schneider, editors. The Description Logic Handbook. Cambridge University Press, 2003. [BdR04] Utsav Boobna and Michel de Rougemont. Correctors for XML Data. In Proceedings of 2nd International XML Database Symposium (XSYM’04), volume 3186 of LNCS, pages 97–111. Springer, 2004. [BGM04] Elisa Bertino, Giovanna Guerrini, and Marco Mesiti. A matching algorithm for measuring the structural similarity between an XML document and a DTD and its applications. Information Systems, 29(1):23–46, March 2004. [CDL99] Diego Calvanese, Giuseppe De Giacomo, and Maurizio Lenzerini. Representing and Reasoning on XML Documents: A decription Logic Approach. Journal of Logic and Computation, 9(3):295–318, 1999. [CLN98] Diego Calvanese, Maurizio Lenzerini, and Daniele Nardi. Logics for Databases and Information Systems, chapter Description Logics for Conceptual Data Modeling, pages 229–264. Kluwer, 1998. [ECY00] Vladimir Estivill-Castro and Jianhua Yang. Fast and Robust General Purpose Clustering Algorithms. In Proceedings of 6th Pacific Rim International Conference on Artificial Intelligence (PRICAI 2000), volume 1886 of LNCS, pages 208–218. Springer, 2000. [EL02] Robert Engels and Till Christopher Lech. Generating ontologies for the semantic web: OntoBuilder. In J. Davies, D. Fensel, and F. van Harmelen, editors, Towards the semantic web: ontology-driven knowledge management, chapter 6, pages 91–115. John Wiley and Sons, Ltd., 2002. [JOKA02] Jong-Seok Jung, Dong-Ik Oh, Yong-Hae Kong, and Jong-Keun Ahn. Extracting Information from XML Documents by Reverse Generating a DTD. In Proceedings of the (EurAsia-ICT 2002), volume 2510 of LNCS, pages 314–321. Springer, 2002. [NAM98] Svetlozar Nestorov, Serge Abiteboul, and Rajeev Motwani. Extracting schema from semistructured data. In Proceedings ACM SIGMOD International Conference on Management of Data (SIGMOD 1998), pages 295–306. ACM, 1998. [SPBA03] Ismael Sanz, Juan Manuel P´erez, Rafael Berlanga, and Mar´ıa Jos´e Aramburu. XML Schemata Inference and Evolution. In Proceedings of 14th International Conference on Database and Expert Systems Applications (DEXA’03), volume 2736 of LNCS, pages 109–118. Springer, 2003. 20 [W3C04] W3C. Extensible Markup Language (XML) 1.0, third edition, February 2004. [Wid99] Jennifer Widom. Data Management for XML: Research Directions. IEEE Data Engineering Bulletin, 22(3):44–52, 1999. [ZS89] Zaizhong Zhang and Dennis Shasha. Simple Fast Algorithms for the Editing Distance Between Trees and Related Problems. SIAM Journal on Computing, 18(6):1245–1262, 1989. 21