As XML has become a standard for data representation, it is inevitable to propose and implement techniques for efficient managing of XML data. A natural alternative is to exploit features and functions of (object-)relational database systems, i.e. to rely on their long theoretical and practical history. The main concern of such techniques is the choice of an appropriate XML-to-relational mapping strategy. In this paper we focus on enhancing of userdriven techniques which leave the mapping decisions in hands of users. We propose an algorithm which exploits the user-given annotations more deeply searching the user-specified “hints” in the rest of the schema and applies an adaptive method on the remaining schema fragments. We describe the algorithm theoretically, discussing the key ideas of the approach, chosen solutions, their reasons, and consequences. Finally, we overview the open issues related to implementation of the proposed algorithm and its experimental testing on real XML data. ¤ This work was supported in part by the National Programme of Research (Information Society Project number 1ET100300419).
Without any doubt the eXtensible Markup Language
(XML) [
Probably the most natural and practically used approach involves techniques which exploit features of (object-)relational database systems, though they are not as efficient as the native ones due to the key problem of structural differences between XML data and relations. The reason for the popularity is that relational databases are still regarded as universal and powerful data processing tools and their long theoretical and practical history can guarantee a reasonable level of reliability and efficiency. Contrary to native methods it is not necessary to start “from scratch” but we can rely on a mature and verified technology, i.e. properties that no native XML database can offer yet. On this account we believe that these methods and their possible improvements should be further enhanced.
The main concern of the database-based1 XML
techniques is the choice of an appropriate XML-to-relational
mapping strategy, i.e. the way the given XML data are
stored into relations. We can distinguish the following
three types approaches [
The first set of methods can be further divided [
In this paper we focus on further enhancing of userdriven techniques, particularly on their (in our opinion) two main persisting disadvantages. The first one is the fact that the default mapping strategy is (to our knowledge) always a fixed one. It is quite a surprising finding since we know that the proposed systems are able to store schema fragments in various ways. From this point of view an adaptive enhancing of the fixed method seems to be quite natural and suitable. The second key shortcoming we are dealing with is weak exploitation of the user-given information. We believe that the schema annotations a user provides can not only be directly applied on particular schema fragments, but the information they carry can be further exploited. The main idea is quite simple – we regard the annotations as “hints” how a user wants to store particular XML patterns and we use this information twice again. Firstly, we search for similar patterns in the rest of the schema and store the found fragments in a similar way. And secondly, we exploit the information in the adaptive strategy for not annotated parts of the schema.
To sum up, the main contribution of this paper is a proposal of an algorithm which enhances classical userdriven strategies using the following two approaches: ² a deeper exploitation of the information carried in user-given schema annotations and ² an adaptive mapping strategy for not annotated parts of the schema.
We describe the proposed algorithm theoretically. We discuss the key ideas and problems, their possible solutions, reasons for our particular decisions, and their consequences. Finally, we overview the related problems and open issues of a particular implementation of the proposal.
The rest of the paper is structured as follows: Section 2 contains a motivation for focusing on user-given information. Section 3 overviews the existing related works in the area of user-driven methods, adaptive methods, and similarity of XML data. In the fourth section we describe and discuss the proposed algorithm in more detail and in the fifth section we sum up the corresponding implementation open issues. Finally, Section 6 provides conclusions and outlines our future work.
The key concern of this paper is to exploit the user-given information as much as possible. We result from the idea of user-driven enhancing of the user-defined techniques, where a user is expected to help the mapping process, not to perform it. We want to go even farther. But first of all we discuss why user-given information is so important to deal with.
A simple demonstrative example can be a set of XML
documents which contain various XHTML [
Another example can be the crucial feature of database storage strategies – updatability of the data. On one hand, we could know that the data will not be updated too much or at all but we need an effective query evaluation. On the other hand, there could be a strong demand for effective data updates, whereas the queries are of marginal importance. And there are of course cases which require effective processing of both. Naturally, the appropriate storage strategies differ strongly. In case of effective query processing a number of indices and numbering schemes can be exploited but at the cost of corresponding expensive updates. Effective updates, conversely, require the simplest information of mutual data relationships. And if both the aspects are required, it is unavoidable to compromise. And such decision can be again made correctly only if we have an appropriate information on the required future usage.
Last but not least, let us consider the question of data
redundancy. Without any additional information the
optimal storage strategy is so-called 4NF schema
decomposition into relations [
Both the cost-driven and user-driven methods are
based on the idea of exploiting additional user-given
information and they appropriately adapt the target
database schema. In the former case it is extracted from
a sample set of XML documents and/or XML queries
which characterize the typical future usage, in the
latter case it is specified by user-given annotations, i.e. the
user directly specifies the required changes of the default
mapping. But although there is a plenty of existing
representatives of the two approaches, there are still numerous
weak points and open issues that should be improved and
solved [
As mentioned above, our first improvement is searching for identical or similar fragments in the not annotated schema parts. This approach has two main advantages: 1. The user is not forced to annotate all schema fragments that have to be stored alternatively, but only those with different structure. Thus the system is not endangered of unintended omitting of annotating all similar cases. 2. The system can reveal structural similarities which are not evident “at first glance” and which could remain hidden to the user.
Thus the first main concern of our proposal is how to identify identical or similar fragments within the schema.
Our second enhancing focuses on the choice of the mapping strategy for schema fragments which were neither annotated by the user, nor identified as fragments similar to the annotated ones. In this case we combine the idea of cost-driven methods with the fact that a userdriven technique should support various storage strategies too. Hence our second concern is how to find the optimal mapping strategy for the remaining schema fragments and, in addition, with exploitation of the information we already have, i.e. the user-specified annotations, as much as possible. 3
As we have mentioned, methods which involve a user in
the mapping process can be divided into user-defined and
user-driven. Probably due to simple implementation the
former ones are supported in most commercial database
systems [
In both the cases the mapping for not annotated parts
is fixed and the annotations are applied just directly on
the annotated schema fragments. The two ideas we want
to use for their enhancing are adaptivity [
Probably the first proposal of an adaptive cost-driven
method can be found in [
The other existing cost-driven approaches [
Exploitation of similarity of XML data can be found in various XML technologies, such as, e.g., document validation, query processing, data transformation, storage strategies based on clustering, data integration systems, dissemination-based applications, etc. Consequently, the number of existing works is enormous. We can search for similarity among XML documents, XML schemes, or between the two groups. Furthermore, we can distinguish several levels of similarity that can be taken into account during the search process – a structural level (i.e. considering only the structure of the given XML fragments), a semantic level (i.e. taking into account also the meaning of element / attribute names), a constraint level (i.e. taking into account also various text value constraints), etc.
In case of document similarity we distinguish
techniques expressing the similarity of two documents D1
and D2 by measuring how difficult is to transform D1
into D2 (e.g. [
The general idea of fixed schema-driven
XML-torelational mapping methods is to decompose the given
XML schema S into a set of schema fragments
F = ff1; f2; :::; fng. Each fi 2 F is then mapped to
a corresponding relation ri using a mapping strategy
sfrag. The relationship between fragments is kept
using a mapping strategy srel. In other words, the 3-tuple
2An element with multiple parent elements in the schema – see [
Note that fixed generic methods can be described using the 3-tuple ¿ as well. Each of the techniques views an XML document as general directed tree with several types of nodes. And the view can be considered as a special kind of XML schema.
In user-driven strategies the three characteristics are influenced by user-defined annotations which specify how a particular user wants to store selected fragments F 0 = ff10 ; f20 ; :::; f m0g. The user usually provides S with annotating attributes from the predefined set of attribute names §A0 , which represent various fixed mapping strategies, resulting in an annotated schema S0. Obviously, annotated fragments in F 0 do not have to correspond to schema fragments in F . For instance, a user may specify that whole S should be stored using a 4NF decomposition and thus F 0 = fS0g is a singleton, whereas corresponding F can contain several schema fragments depending on the complexity of S. Also note that while F should cover whole S, F 0 usually does not.
A classical user-driven strategy consists of the following steps: 1. S is provided with annotations from §A0 resulting in S0 and F 0. 2. Annotated fragments from F 0 are decomposed into corresponding schema fragments F1 = ff1; f2; :::; fkg. 3. Not annotated fragments of S0 are decomposed into schema fragments F2 = ffk+1; fk+2; :::; fng using a default (predefined or user-defined) fixed strategy sdef . 4. F = F1 [ F2 is mapped to R using sf rag and srel.
Using this notation our proposed enhancing simply adds the following steps between the step 1 and 2: a. For 8 f 0 2 F 0 we identify a set Ff0 0 of all fragments similar to f 0 occurring in S0nff 0g. b. For 8 f 0 2 F 0 all fragments in Ff0 0 are annotated with annotating attributes of f 0 and F 0 = F 0 [ Ff0 0 . c. S0nF 0 is annotated using an adaptive strategy which adds new annotated fragments to F 0.
The mapping process is schematically depicted in Figure 1 where the given schema S with two annotated fragments f and g is mapped to a database schema R. If the proposed enhancing (i.e. steps 1.a – 1.c) is included, the system gradually identifies and adds new annotated fragments f1, f2, g1, g2, and g3 which are mapped using user-required mapping strategies. If the enhancing is not included (i.e. in case of a classical user-driven strategy), only fragments f and g are annotated using user-required strategies and the rest of the schema using sdef . 4.1
As we have mentioned, there are numerous approaches to measuring similarity of XML data. Nevertheless, most of them cannot be directly used for our case since our demanded key characteristics differ. In particular, we search for similarity within the scope of a single schema, the similarity measure should not depend on similarity of element / attribute names but primarily on complexity of content models, and the similarity measure cannot obviously depend on the context of fragments.
Considering the problem in more depth, several fundamental questions arise: 1. How are the annotated fragments defined?
strategies, are supported? fixed mapping 3. What measure is used for measuring similarity of two schema fragments? 4. Can we optimize the exhaustive search strategy? The answers for the questions mutually influence each other and specify the algorithm. Furthermore, the definition of annotated fragments together with the question of their mutual intersection are closely related to supported mapping strategies. 4.1.1
First of all, for easier processing we define a graph
representation of an XML schema S, no matter if annotated
or not. For easier explanation we assume that the given
XML schema S is expressed in DTD3 [
Definition 2 A fragment of a schema S is each subgraph of S consisting of an element e, all its descendants, and corresponding edges.
© is a set of all fragments of S.
Next, we assume that each annotated fragment f 0 2 F 0 is uniquely determined by the element e which was annotated using an annotating attribute a 2 §A0 . Definition 3 An annotated element e0 of schema S0 is an element provided with an annotated attribute from §A0 .
3We omit supplemental constructs such as entities, CDATA sections, comments, etc. Definition 4 An annotated fragment f 0 of schema S0 is a fragment of S0 rooted at an annotated element e0 excluding all annotating attributes from §A0 .
As we want to support shared elements and recursion,
since both the constructs are widely used in real XML
data [
Definition 5 An expanded schema graph GeSx is a result of the following transformations of schema graph GS : 1. Each shared element is duplicated for each sharer using a deep copy operation, i.e. including all its descendants and corresponding edges. 2. Each recursive element is duplicated for each repeated occurrence using a shallow copy operation, i.e. only the element node itself is duplicated.
An illustrative example of a schema graph GS and its expanded schema graph GeSx is depicted in Figure 2. A shared element is highlighted using a dotted rectangle, a recursive element is highlighted using a dotted circle.
As it is obvious, in case of shared elements the
expansion is lossless operation. It simply omits the key
advantage of shared elements which allows reusing of
previously defined schema fragments. The situation is more
complicated in case of recursive elements which need to
be treated in a special way henceforth. For this purpose
we exploit results of statistical analysis of real-world
recursive elements [
In the following text we assume that a schema graph of an XML schema is always an expanded schema graph, if not explicitly stated alternatively. 4.1.2
From Definitions 4 and 5 we can easily prove the following two statements: Lemma 1 Each expanded schema graph GeSx is a tree. Lemma 2 Two annotated fragments f x0 and fy0 of an expanded schema graph GeSx0 can intersect only if f x0 µ fy0 or f x0 µ fy0 .
Furthermore, we can observe that the common schema fragment, i.e. the intersection, contains all descendants of a particular element.
We distinguish three types of the annotation intersection depending on the way the corresponding mapping strategies influence each other.
Definition 6 Intersecting annotations are redundant if the corresponding mapping strategies are applied on the common schema fragment separately.
Definition 7 Intersecting annotations are overriding if only one of the corresponding mapping strategies is applied on the common schema fragment.
Definition 8 Intersecting annotations are influencing if the corresponding mapping strategies are combined resulting in one composite storage strategy applied on the common schema fragment.
Redundant annotations can be exploited, e.g., when a user wants to store XHTML fragments both in a single CLOB column (for fast retrieval of the whole fragment) and, at the same time, into a set of tables (to enable querying particular items). An example of overriding annotations can occur when a user specifies a general mapping strategy for the whole schema S and then annotates fragments which should be stored differently. Naturally, in this case the strategy which is applied on the common schema fragment is always the one specified for its root element. The last mentioned type of annotations can be used in a situation when a user specifies, e.g., the 4NF decomposition for a particular schema fragment and at the same time an additional numbering schema which speeds up processing of particular types of queries. In this case the numbering schema is regarded as a supplemental index over the data stored in relations of 4NF decomposition, i.e. the data are not stored redundantly as in the first case.
We assume that each pair of annotations implemented
in a corresponding system is assigned its intersection
type or, if necessary, a particular combination of
annotations can be denoted as forbidden. The existing
systems [
The similarity measure, the search algorithm, and its possible optimization are closely related. However, the main idea of the enhancing of user-driven techniques remains the same regardless the chosen measure and algorithm. The choice of the measure influences the precision and scalability of the system, whereas the algorithm influences the efficiency of finding the required fragments. In case of “classical” adaptive methods this can be a marginal aim, since the schema adaptation is performed only once, before the schema is created. But its importance significantly rises when the system needs to be dynamic and adapt continuously.
Let us suppose that we have a similarity measure sim(fx; fy ) 2 [0; 1] expressing similarity of two fragments fx and fy of an expanded graph, where 1 represents strong similarity and 0 strong dissimilarity, and a similarity threshold Tsim 2 [0; 1]. A naive strategy would exploit an exhaustive search as depicted by Algorithm 1.
The algorithm evaluates similarity of each annotated fragment f 0 2 F 0 and each fragment fe rooted at an element e 2 S0nff 0g. We can assume that if the storage strategy for any fe should not change, the user would mark it as final. For such fragment either the default strategy sdef or the strategy specified by corresponding user-defined annotation will be used, regardless the results of the search or adaptive algorithm. As such this situation is rather the problem of implementation than a theoretical one and thus we further assume that there are no such fragments in S0. On the other hand, we naturally regard fragments annotated by a user to be final by default.
The resulting similarity values are stored into socalled similarity matrix fsim[f 0; fe]gf 02F 0; e2S0 . An element e is annotated if there exists a fragment fmax 2 F 0 with the highest similarity value sim(fmax; fe) > Tsim. In Algorithm 1 we assume that there is always one such candidate at most. Otherwise, the system can ask for user intervention when necessary. We call this approach a single annotation strategy (SAS).
Input: S0, F 0, sim(fx; fy ), Tsim Output: F 00, i.e. F 0 [ newly annotated fragments fconstruction of the similarity matrixg 1: F 00 à F 0 2: for all f 0 2 F 0 do 3: for all element e 2 S0 do 4: fe à subgraph rooted at e 5: if e 2 S0nff 0g then 6: sim[f 0; fe] à sim(f 0; fe) 7: else 8: sim[f 0; fe] à 0 9: end if 10: end for 11: end for
fannotation strategyg 12: for all element e 2 S0 do 13: maxe à maxf 02F 0 fsim[f 0; fe]g 14: fmax à f 0 2 F 0 s.t. sim[f 0; fe] = maxe 15: if maxe > Tsim then 16: fe.annotation à fmax.annotation 17: F 00 à F 00 [ ffeg 18: end if 19: end for 20: return F 00
The question is whether this approach is correct actually. From another point of view it could be more reasonable to annotate an element e using annotations of all fragments f 0 2 F 0 s.t. sim(f 0; fe) > Tsim. Together with the assumption that for each pair of annotations the result of their composition is predefined and that the annotations have priorities according to which they are composed, this approach seems to be a better choice since it does not omit important information. But, on the other hand, let us consider the situation depicted in Figure 3, where for i 2 f1; 2; 3g sim(f 0; fi) > Tsim and f 0 is the annotated fragment. The problem is whether we can annotate all the three fragments f1; f2; f3 using the annotation of f 0, especially what will be the result of intersection in case of f1 and f3 or f2 and f3, i.e. fragments occurring on the same root path5. We can naturally assume that intersection of two identical annotations is overriding and as such has no effect. Thus we could annotate only the topmost fragment on each root path. In case of example in Figure 3 this rule would be applied twice, resulting in a single annotation of fragment f3. But what if we knew, in addition, that sim(f 0; f1) > sim(f 0; f3) and sim(f 0; f2) > sim(f 0; f3)? As it is obvious, in such case it is seems to be more reasonable and natural to annotate fragments f1 and f2 rather than whole f3. Or this 5A path from the root node to a leaf node. situation can be again a case for user intervention, depending on the point of view of it. We will further consider the former one.
If we generalize the idea, the algorithm annotates an element e using annotations of all fragments f 0 2 F 0 s.t. sim(f 0; fe) > Tsim and 6 9 element e0 on any root path traversing e s.t. sim(f 0; fe0 ) > sim(f 0; fe). The resulting algorithm, so-called multiple annotation strategy (MAS), is depicted by Algorithm 2, where e:ancs denotes a set of (direct or undirect) ancestors of element e and e:descs denotes a set of (direct or undirect) descendants of e. The process of construction of the similarity matrix remains the same as in case of Algorithm 1. Algorithm 2 Multiple Annotation Strategy (MAS) Input: S0, F 0, sim(fx; fy ), Tsim Output: F 00, i.e. F 0 [ newly annotated fragments 1: F 00 Ã F 0
fconstruction of the similarity matrixg 2: -//
fannotation strategyg 3: for all f 0 2 F 0 do 4: for all element e 2 S0 do 5: if (sim[f 0; fe] > Tsim) ^ (6 9ea 2 e:ancs : sim[f 0; fea ] > sim[f 0; fe]) ^ (6 9ed 2 e:descs : sim[f 0; fed ] > sim[f 0; fe]) then 6: fe.annotation à f 0.annotation 7: F 00 à F 00 [ ffeg 8: end if 9: end for 10: end for 11: return F 00
Using this approach we should consider what will happen in case a user annotates two structurally identical (or too similar) fragments using different annotations. We cannot simply rely on predefined type of their intersection and corresponding priorities, because the situation is a slightly different one. In this case the system should rather ask for user intervention whenever it is not able to decide. And this is again a problem of the particular implementation. 4.1.4
Now let us consider the search strategy from the point of view of complexity of the algorithm. Figure 4 depicts an example of processing a single annotated fragment, in particular the amount of similarity comparisons. Annotated fragments f and g are highlighted using rectangles, all schema fragments, which are compared with f are highlighted using dotted ovals.
If we do not know any features of the measure, there are not many ways how to avoid the exhaustive search. Also the order in which fragments in F 0 are processed is then unimportant. But although we can assume that card(F 0) = m is small, i.e. that a user annotates several fragments but the number is not large, the exhaustive search can be expensive due to the size of GeSx. And even from the simple example in Figure 4 it is obvious that there are pairs of schema fragments which do not have to be compared at all. Another problem is the complexity of the if condition of Algorithm 2 (line 5) which can in the worst case lead to multiple searching through the whole GeSx. So in both the cases we need to avoid the unnecessary similarity evaluations.
It seems promising to borrow the idea of
clustering, similarly to paper [
All schema fragments (depicted using black-filled circles) are divided into clusters C1, C2,..., Ck (depicted using black circular lines) having their centroids c1, c2,..., ck and radii r1, r2,..., rk (or one common radius r, depending on the implementation). Having this information, only those schema fragments have to be compared with fragment f , whose clusters intersect the cluster with centroid f and radius Tsim. In case of Figure 5 these are clusters C1 and C2. Obviously, if the clusters were selected appropriately, the amount of comparisons would decrease rapidly. Hence the key concern of all clustering algorithms is mainly the construction of the clusters.
The construction is usually performed using a
kmeans algorithm or its variations (e.g. [
For further optimization we can exploit
characteristics of the chosen similarity measure. The existing
algorithms for measuring similarity on schema level usually
exploit various supplemental matchers [
Definition 9 A matcher is a function m : ©2 ! [0; 1] which evaluates similarity of a particular feature of two schema fragments fx; fy 2 ©.
Definition 10 A partial similarity measure is a function mpart : ©2 ! [0; 1]p which evaluates similarity of the given schema fragments fx; fy 2 © using matchers m1; m2; :::; mp : ©2 ! [0; 1] and returns a p-tuple of their results.
Then the partial results are combined using an appropriate approach, usually a kind of a weighted sum, into the resulting composite similarity value.
Definition 11 A composite similarity measure is a function mcomp : [0; 1]p ! [0; 1] which combines the results of particular matchers and returns the total similarity value.
Due to the features of selected partial matchers the existing techniques usually exploit a bottom-up strategy, i.e. starting from leaf nodes towards the root node. Together with the previously mentioned problem of similar intersecting fragments this is why we need to know the behavior of the similarity measure on particular root paths.
For instance, if we knew that the similarity measure is concave, i.e. that it has only one global maximum, we could skip processing of all the ancestors on the current root path whenever we reach the fragment with the extreme value. A sample situation can be seen in Figure 6 which depicts an example of a graph of similarity function for an annotated fragment f 0 and fragments f1; f2; :::; fr on a single root path. From the graph we can see, that only fragments f1; f2; f3; f4 need to be processed (f4 for testing the extremity), then the similarity evaluation can terminate, skipping fragments f5; f6; :::; fr.
As it is obvious, this way we can decrease the number of unnecessary similarity evaluations as well as avoid pre-processing of the schema and expensive checking of the if condition of Algorithm 2. Naturally, the efficiency of such approach depends strongly on the position of the extreme on the root path. The key problem is how to define such similarity measure. For our purpose we need a measure which focuses especially on the structure of the compared fragments, known equivalences or relations between regular expressions, differences between simple and complex types, etc., i.e. on features that influence the efficiency of database processing the most. But it is hard, if not impossible, to propose a measure with concave behavior which is at the same time enough precise in relation to these requests. Nevertheless, we can exploit a relaxed version of this idea as a kind of heuristic of the bottom-up strategy.
Although we can hardly ensure that mcomp is concave, we can assume that at least q of the matchers, where 1 · q · p, have this property. Without loss of generality we suppose that these are m1; m2; :::; mq. For instance a trivial matcher with such behavior can compare the number of distinct element or attribute names, the amount of similar operators, the depth of the corresponding regular expression, etc. The heuristic is then based on the idea that if at least “sufficient amount” of the q matchers exceed their extreme value, we can terminate processing of the current root path too. There are just two differences from the previously mentioned idea. Firstly, the exceeding of the particular extreme is expressed using a threshold Tex 2 [0; 1] which guarantees that processing of the current root path does not terminate neither too soon (to reach the optimum of the composite similarity measure) nor too late (to avoid unnecessary similarity evaluations). Secondly, as it is obvious, the matchers themselves are not precise in terms of similarity evaluation. Hence each of them is assigned a user-specified reliability r1; r2; :::; rq 2 [0; 1], where 0 expresses strong unreliability and 1 strong reliability of the matcher. The reliabilities then influence the real value of threshold Tex for particular matchers multiplying its value.
The whole optimization of the approach, so-called basic annotation strategy (BAS), is depicted by Algorithm 3, where function terminate returns true if the search algorithm should terminate in the given node, otherwise it returns false. Furthermore, we assume that each element of the graph is assigned an auxiliary list of candidates consisting of pairs < f ragment; similarity >, i.e. references to fragments (and corresponding similarity values) within its subtree that are candidates for annotation.
The algorithm processes schema graph starting from leaf nodes. For each root path the optimal similarity value and the reference to corresponding fragment are propagated until a better candidate is found or the condition of the heuristic is fulfilled. Then the processing of the current root path is terminated and current candidates are annotated. The complexity of the algorithm depends on the heuristics. In the worst case it does not enable to skip processing of any node that results in the exhaustive search. But in contrast to the clustering approach we have avoided the expensive preprocessing of the algorithm.
In general we could use an arbitrary similarity measure, not exactly the above defined composite one. It is also possible to use disjoint sets of matchers for the heuristic and for the composite similarity measure. Nevertheless, we will deal with the above described ones, since it is the typical and verified way for evaluating similarity among XML schemes. 4.1.5
Last but not least, we have to solve the open problem of
expanded recursive elements, since the expansion is not
a lossless operation as in case of shared elements. As
we have already indicated, we will exploit the results of
analysis of real-world XML data which shows two
important aspects [
If we realize that we need the “lost” information about recursion only at one stage of the algorithm, the solution is quite obvious. We analyze the structure of schema fragments when evaluating matchers m1; m2; :::; mp, whereas each of the matchers describes similarity of a particular feature of the given fragments. In case the fragments contain recursive elements we will not use the exact measure, but its approximation with regard to the real complexity of recursive elements. For instance if the matcher analyzes the maximum depth of fragment containing a recursive element, the resulting depth is not infinite, but considers the average depth of real-world recursive elements.
The question is whether it is necessary to involve a matcher which analyzes the amount of recursive elements in schema fragments. On one hand it can increase the precision of the composite measure. But from another point of view the approximation transforms the recursive element to a “classical” element and hence such matcher can be misleading. 4.2
At this stage of the algorithm we have a schema S0 and a set of annotated fragments F 0 which involve the userdefined fragments and fragments identified by Algorithm 3. As the second enhancing we want to apply an adaptive mapping strategy to the remaining parts of the schema.
As mentioned previously, the key idea of adaptive strategies is to adapt the target relational schema R to the expected future application, which is specified by a sample set of XML data and/or XML queries. The techniques define a set of XML-to-XML transformations which produce a space of equivalent or more general XML schemes. A search algorithm is used to find a schema, where the evaluation of the given queries is most efficient. Thus at first glance the user-driven techniques have nothing in common with the adaptive ones. Or, we could expect that the user provides not only a set of annotations, but also sample XML documents and XML queries. Then we could use a classical adaptive strategy for not annotated parts of schema S0. Such combination should not be difficult considering the fact that userdriven techniques enable to store various schema fragments in various ways. Nevertheless, the key shortcoming of such approach is that the user is expected to provide too many information.
Under a closer investigation we can see that the usergiven annotations provide a similar information – they say how particular schema fragments should be stored to enable efficient data querying and processing. Thus we can simply reuse the user-given information. For this purpose we define an operation contraction which enables to omit those schema fragments, where we already know the storage strategy, and focus on the remaining ones.
Definition 12 A contraction of an expanded schema graph GeSx0 with annotated fragment set F 0 is an operation which replaces each fragment f 0 2 F 0 with a single auxiliary node called a contracted node.
The resulting graph is called a contracted graph GcSo0n.
From Definitions 4 and 12 we can easily prove the following simple statement which enables to reuse the search algorithm on the contracted graph.
Lemma 3 Contracted graph GcSo0n of a connected expanded schema graph GeSx0 is connected.
The basic idea of the adaptive strategy is as follows: Having a contracted graph GcSo0n we repeat the search algorithm (in particular its slight modification) and operation contraction until there can be found any fragment to annotate. Contrary to the previous situation the search algorithm has the following differences: ² It searches for schema fragments which are not involved in the schema, i.e. it searches among all nodes of the given (contracted) graph and returns the (eventually empty) set of found fragments. ² For similarity evaluation we do not take into account contracted nodes, i.e. neither their current, nor their previous structure or any other features. These were already analyzed and processed in previous steps of the algorithm. ² The annotations of contracted nodes are always overriding in relation to the newly defined ones. ² The required threshold is more precise, i.e. we use a threshold Tcon < Tsim.
We denote this modification of BAS as a contractionaware annotation strategy (CAS). (We omit its formal description for obviousness and the paper length.) The resulting annotating strategy, so called global annotation strategy (GAS), is depicted by Algorithm 4, where function contract applies operation contraction on expanded graph of the given schema and corresponding fragments,
and function expand contractions expands all the contracted nodes of the given schema to the original ones.
The resulting complexity of the algorithm depends on the number of iterations of the cycle (lines 3 – 7). In the worst case each iteration results in annotating of a single element, i.e. the search algorithm repeats (j©j ¡ jF 0j + 1) times.
Considering the whole approach, we are especially interested in the efficiency of the resulting XML-torelational storage strategy which can be verified only through appropriate tests on real XML data. We discuss it in the following section. 5
In the previous section we have described and discussed the proposed algorithm on theoretical level. We have mentioned several possible solutions and discussed their consequences and disadvantages as well as reasons for the choices we have made. But despite the detailed description there are still several open issues. We distinguish two main categories: 1. Features of the particular implementation and
As for the former case the key implementation decisions are especially: ² the set of supported schema annotations, types of their mutual intersection (or forbiddance), and their priorities, ² the matchers m1, m2, :::, mq, mq+1, :::, mp and corresponding reliabilities r1, r2, :::, rq, ² the composite similarity measure mcomp, and ² the thresholds Tsim, Tex, and Tcon.
The key problem lies especially in tuning of reliabilities and thresholds, since both influence the precision and efficiency of the system strongly. The remaining characteristics are related rather to its usefulness and versatility. There are also marginal questions such as, e.g., whether the system will support final elements or user intervention if there are more candidates for a particular situation. But these features do not have the key influence on the proposed approach itself.
The latter category of open issues is quite
unpredictable, despite the existing statistics of real XML data
[
As it is obvious, both the categories are also related significantly. And though some particular features can be estimated or preset according to the existing user-driven systems and statistical analysis of data, most of them will still require a series of experimental tests. 6
The main aim of this paper was to illustrate that since the idea of database-based XML processing methods is still up-to-date, the techniques should and can be further enhanced. On this account we have proposed a user-driven mapping algorithm which is able to exploit the user given information, i.e. schema annotations, more deeply and, at the same time, to find the mapping strategy for the not annotated parts more efficiently – using an adaptive approach. We have described and discussed the algorithm on theoretical level as well as summed up the corresponding open issues related to particular implementation decisions.
A natural next step of our work is the implementation
of the proposed algorithm and especially experimental
tests of its behavior on real data. For this purpose we
are enhancing our previous implementation of a fixed
XML-to-relational mapping strategy [
A possible further enhancing of our approach can be found in focussing on statistically frequent XML schema patterns. They can be used in several ways – e.g. as a reasonable default setting or as XML patterns with a higher priority.
Another improvement can be an exploitation of the semantic of element and/or attribute names. The similarity can be searched not only on structural level, but using a kind of thesaurus or appropriate user-given information. Although our proposal focuses mainly on structural similarities related to efficiency of database processing, it is at least worth testing whether the semantic of the names carries additional important information useful for this purpose too.
Next interesting task could be also a combination of our approach with a real cost-driven one, i.e. an exploitation of both user-given annotations and a sample set of XML data and XML queries together. As we have already mentioned, the key disadvantage is in the amount of required input data. But, on the other hand, the combination of the two approaches could bring interesting results or the efficiency of the two approaches can be at least compared.
And last but not least, the key enhancing lies in
dynamic adaptability of the system [