Updating Views Over Recursive XML Ming Jiang, Ling Wang, Murali Mani, and Elke Rundensteiner Worcester Polytechnic Institute, 100 Institute Road, Worcester MA 01609, USA {jiangm|lingw|mmani|rundenst}@cs.wpi.edu Abstract. We study the problem of updating XML views defined over XML documents. A view update is performed by finding the base updates over the underlying data sources that achieve the desired view update. If such base updates do not exist, the view update is said to be untranslatable and rejected. In SQL, determining whether a view update is translatable is performed using schema level analysis, where the view definition and the base schema are used. XML schemas are more complex than SQL schemas, and can specify recursive types and cardinality constraints. In this paper, we propose a solution based on schema level analysis for determining whether an update over XML views is translatable and for finding the translation if one exists, while considering the features of XML schemas. 1 Introduction In databases systems, a user sees a portion of the base data called a view. Therefore he/she may need to update base data through these views (view updates). Especially in shared databases, it is essential to provide the capacity to support view updates. In the relational scenario, there have been many studies on determining whether a view update is translatable [5]. A common semantics used for determining whether a view update is translatable is side-effect free semantics. In this semantics, a view update is said to be translatable if there exists base updates that achieve the desired view update without affecting any other portion of the view. Current relational/SQL systems use schema level analysis for determining whether a view update is translatable, where the view definition and the base schemas are used. Nowadays, as XML is becoming the standard format for data exchange, database community is exploring its ability to store data. In fact, view updates become more common as many XML databases are available on the internet, and a large number of users have access to such databases. In this paper, we study how to perform XML view updates over XML data sources, using schema level analysis. This problem is much harder than for relational schemas because of the complex features in XML schema, such as recursive types and cardinality constraints. Let us consider an example XML document with its schema as in Figure 1. Note the base schema element course is recursive, as a course may have a child element pre, which stands for pre-requisite for this course, and pre in turn can have course elements as its children. Similarly, the base element pre is also recursive. Now consider two queries over D, as shown in Figure 2 and Figure 3. In Figure 2, (a) is the XQuery statement which defines the view. (b) is the view schema tree that corresponds to the XQuery. (c) is the view instance tree generated by the XQuery and XML document D. The same goes with Figure 3. 1 1 The subscripts a, b, c in Figure 1 and 1,2,3 in Figure 2(c) and Figure 3(c) are for illustration purpose only. They do not appear in the actual documents or views. 2 Database { result FOR $course IN course+)> FOR $course IN Document(“base.xml” ) //course * Document(“base.xml” ) //course RETURN course Algorithm { $course/name } ]> (a) (b) course/name } (c) result WPI Data Structure CS course1 course2 course3 Henry (a) view query John name name name (b) view schema tree STView (c) view instance tree Joe Database Algorithm Data Structure Fig. 2. Query Q1 and correspond- Fig. 1. XML document D with Schema(D) ing view { FOR $pre IN Document(“base.xml” ) //pre RETURN FOR $pre IN 
 {
                                                    pre                                   
                 FOR $course IN $pre//course                                                             { FOR $prof IN Document
                                                      FOR $course IN
                 RETURN                             * $pre //course                                                 ( “base.xml”) //professor,
                                                   course                                 
                                                                                  ]>                      $student IN Document

                       { $course/name } (a) (b)                                                  (a) base schema                                  (“base.xml”)//student
                                               course/name                                                                                 RETURN 
                                                                                                  result
                                                   (c)                                                                                                     { $prof/name,
                    }
result * } pre pre $student/name } prof-student } course1 course2 course3 (a) view query name name name (b) view schema tree STView $prof/name $student/name (c) query statement Q (c) view instance tree Algorithm Data Structure Data Structure (b) view schema tree STView Fig. 3. Query Q2 and corresponding view Fig. 4. Query Q3 A user may want to delete course1 in Figure 2(c). If we delete coursea in D, this update would cause course2 , course3 and their descendants to be removed in Fig- ure 2(c). This is a side-effect and therefore it is not a correct translation. Now let us consider Figure 3(c) and try to delete course2 . We can achieve this by deleting the base element coursec which has the name child. However, doing so will also delete course3 in the view and therefore it is also not a correct translation. Intuitively, recursive base schemas and queries cause the above problems. However, are the above two scenarios the only cases that recursion may have side-effects? If not, how can we effectively check out all such side-effects? This problem has not been studied, to the best of our knowledge. There are also other XML features that need to be considered for XML view up- date problems, such as cardinality constraints in the base schema. Will these features make the problem different from the relational scenario? Let us take a look at the query in Figure 4(c). It indicates that each prof essor element in the base will join with ev- ery student element. Therefore each prof essor and student may be used more than once and we cannot delete prof -student view element. However, let us reconsider this query, given the base schema as shown in Figure 4(a). It indicates that there is only one prof essor in the base. We now know that each student will be used only once and we can delete a certain prof -student by deleting the corresponding student in the base XML document. From this example, we can observe that utilizing cardinality informa- 3 tion provided in the base schema may give a better translation for the view update. How to fully handle cardinality is also discussed in this paper. Our main technical contributions include: we study how features in XML schemas, such as recursive types and cardinality constraints, impact the XML view update prob- lem. We propose an algorithm for determining whether a view update over XML data sources is translatable and for finding the translation if one exists, based on schema level analysis. Our algorithm is sound (a translation returned by our algorithm is guaranteed to not cause side-effects) and complete (a translation is guaranteed to be returned by our algorithm if there exists one). We believe these results go a long way towards under- standing the XML view update problem and provide the capacity to efficiently update XML views. Outline. The rest of the paper is organized as follows. Section 2 defines view update translatability and then defines the scope of the problem we consider. Section 3 intro- duces notations and background. Section 4 discusses how to handle unique features in XML schemas when solving the view update problem over XML data sources. Sec- tion 5 proposes our three-step checking algorithm and Section 6 gives a conclusion and discusses the future work. 2 Related Work There are many studies on view updates in relational scenario, such as [6, 5, 9, 4]. [6] introduces the concept of a complementary view. The authors argue that when changing the data in the base corresponding to the updates on the view, the rest of the database that is not in the view should remain unchanged. This solution tends to be too strict, as many view updates are not translatable by this theory. In [5], the authors argue that we can perform a view update by deleting base tuples that contribute to the existence of this view element. Also such base tuples are required not to contribute to other view elements to avoid side-effects. Similarly, in [9], Keller proposes an algorithm to check whether 1-1 mapping exists between a set of base tuples and a set of view tuples. This mapping indicates that a certain view element can be deleted without side-effects. While [6, 5, 9] study the view update problem on the schema level, there are other works such as [4] that study the problem on the instance level. Therefore in [4], more updates can be performed without side-effects. However, because of the large size of the database, such data-centric algorithms tend to be more time-consuming. In order to utilize the maturity of relational database techniques and also adapt to the current required web applications, people tend to build XML views over relational databases, such as [12, 13]. There are some research that consider XML views as com- positions of flat relational views, such as [7], for the purpose of querying relational databases. Some other work further study the updatability of XML views over rela- tional databases. In [15], the authors discuss how to check side-effects for updating XML view elements over a relational database. In [3] the authors use the nested rela- tional algebra as the formalism for an XML view of a relational database to study the problem of when such views are updatable. However, given an XML view over XML data, how to check the updatability of the view elements and further give the correct, efficient translation of this view update remains unsolved. Language for updating XML documents is being studied by [1]. [2] discusses updates in XML scenarios. [14] presents some interesting problems in XML view updates. [10] considers virtual updatable views for a query language addressing native 4 XML databases, including information about intents of updates into view definitions. [11] studies type checking in XML view updates. 3 View Update Translatability and Problem Scope 3.1 View Update Translatability Definition A view update operation u can be a delete, an insert or a replacement. The corresponding update on the XML base is said to be the translation of the view update. Definition 1. Let D be an XML document and V a view defined by DEF V over D. An XML document update sequence U R is a correct translation of a view update u V if u V (DEF V (D))=DEF V (U R (D )). This definition is depicted in Figure 5. The update is correct if the diagram in Fig- ure 5 commutes. (2) uv v uv(v) (1) (4) DEF v DEF v D UR(D) (3) UR Fig. 5. Rectangle rule 3.2 Problem Scope Update Operations Considered As we introduced above, a view update operation can be a delete, an insert or a replacement. Deletions are typically considered to be different from insertions. For instance, consider an SQL view defined as a join between student table and prof essor table, where a student row joins with at most one prof essor row. The SQL standard [8] supports deleting a row in this view by deleting a corresponding student row, whereas inserts are rejected as they might need to insert into student table, or prof essor table or even both, which is more complex and hard to decide. As the first work considering view updates over XML data sources, we consider only dele- tions and inserts are out of our scope. Further, we study single view element deletion, as opposed to deleting a set of view elements. In addition, we do not use a view update language. As we focus on updates of a single view element, how the view element is specified (by the view update language) is not significant. Base Schema Language We use DTD (Document Type Definition) as schema lan- guage to describe the underlying databases. DTD is a very expressive and complex language. The two most significant features in DTD that we consider are recursion and cardinality. The cardinality information is obtained from the content model in DTD, which uses ”*”, ”+”, ”?”, ”,” or ”|”. We will not consider other features in XML schema languages, for doing so will make the algorithm extremely complicated and hard to un- derstand. More specifically, we will not consider ID/IDREF constraints in DTD, and sub-typing and key/foreign key constraints in XML schema. View Definition Language We will use a subset of XQuery as the view definition language described as follows: 1. The XQuery we consider could have FOR, WHERE and RETURN clauses and dirElemConstructor [1] in the statement. 5 2. In each FOR clause, there can be multiple variable binding statements. 3. In an XPath expression, multiple ”//” and ”|” can exist. Further, a node test [1] can be specified as a wildcard. 4. RETURN can contain nested XQuery statements. Even though we consider WHERE clause, the predicates specified in the WHERE clause are not used to determine whether a view update is translatable. Though consid- ering such predicates might result in more view updates being translatable, it can be handled similarly as in relational scenario and we want to focus on the unique XML features. Also, the LET clause is not considered as an XQuery that uses LET can be rewritten into one without the LET clause. Similar to SQL solutions, we do not con- sider aggregation, user-defined functions and Orderby clauses. Restrictions on Translations Considered There are various strategies for translat- ing view updates. For those base XML elements corresponding to the view element to be deleted, we can set its value to null, or delete it but keep its descendants, etc. However, we consider only the translations where we delete an XML view element by deleting the corresponding base elements and also the descendants. This keeps the problem tractable, and is similar to existing solutions in SQL/relational scenarios. Now the problem we study can be described as: Problem Statement: Let Schema(D) be an XML schema and Q a view query over Schema(D). Given a view schema node n, n ∈ Q, does there exist a translation for deleting a view element whose view schema node is n that is correct for every instance of Schema(D)? Note that we study the problem with schema level analysis, which utilizes the view definition and the schema of the base XML data sources. In other words, we do not examine the base data to determine whether there exists a translation. Such schema level analysis is similar to the approach in relational scenarios [5, 9]; data level analysis for the view update problem has been studied in [4]. 4 Notations In this section we first introduce some concepts and notations which are the founda- tion of later discussions. A summary of them can be found in Table 1 2 . Let D be an XML document(base XML data sources) with schema Schema(D). Schema(D) can be represented as a tree called the base schema tree, denoted as STBase . The STBase of the XML Document in Figure 1 is shown in Figure 6 3 . The XML view is defined as a query Q over Schema(D). The corresponding in- stance is denoted as V . Q specifies a view schema tree, denoted as STV iew , such as Figure 2(b), Figure 3(b) and Figure 4(b). vei is a view element in V that is to be deleted. The node in STV iew corresponding to vei is called the view schema node of vei , denoted as SNV iew (vei ). Let us consider the view element course1 in Figure 2(c), SNV iew (course1 ) is the node course in Figure 2(b). 2 SNV iew stands for View Schema Node and STV iew stands for View Schema Tree. SNBase and STBase are analogously defined for the base XML document. 3 Note there is some information not captured by STBase such as order of elements. We only capture those information that will be utilized by our algorithm, such as cardinality constraints and recursive types. 6 Semantic Meaninig Semantic Meaning Notations Notations D XML data sources Q XQuery Statement defining the view Schema(D) XML schema of D V view instance defined by Q STBase schema tree of XML data STView schema tree of Q sources SNBase a node in STBase SNView a node in STView bej a base element in D vei a view element in V source(vei) a base element that sources(vei) All base elements that contribute to the existence contribute to the existence of of vei vei Source(vei) a SNBase that contributes Sources(vei) all the SNBase that contribute to the existence of vei in V to the existence of vei des(source) The set of base elements Des(Source) The set of schema nodes that that are the descendants of are the descendants of Source source and source itself and Source itself Table 1. concepts and notations summary Let us examine the view element course1 in Figure 3(c) again. It exists in the view only when the following two conditions are both satisfied: 1. In the base XML document, there exists one pre element, demonstrated as prea , and one course element, denoted as courseb . 2. The courseb element is a descendant of the prea element. course1 in Figure 3(c) exists because of prea and courseb in base XML Document. Deleting any one of these base elements will lead to deleting course1 . Therefore, these base elements are considered as candidates for deleting course1 . Let us now define those candidates 4 . Given a SNV iew (vei ) in STV iew , every XPath expression that appears on the path from the root till SNV iew (vei ) in STV iew corresponds to a base schema node, which is called a Source and denoted as Source(vei ). The name indicates that it is a way to delete the view element. The set of all such XPath expressions is denoted as Sources(vei ). For example, in Figure 7(c), let us consider the view element name1 . According to Figure 7(b), There are four path expressions from the root till name1 , which are Document(”base.xml”)//department, $dept//prof essor, $prof /student, $student/name. Therefore, Sources(name1 ) = {department, prof essor, student, namestudent }. For each Source(vei ), there exists a set of base elements I(Source(vei )) in D corresponding to it. In I(Source(vei )), there exists one base element contributing to the existence of vei and we call this a source, denoted as source(vei ). For example, in Figure 7(c), sources(name1 ) is {department, prof essor, studenta, namea }. Note while we can delete a source to delete its corresponding view element, it is possible that some other view elements got unexpectedly affected because of this up- date, which are normally called side-effects. There are two kinds of side-effects. The first kind of side-effects is a descendant of source(vei ) is a source of another view element. For example, we may want to delete coursea in Figure 1 to delete course1 4 In fact, deleting an ancestor of any of these base elements can be considered as a candidate for deleting course1 also. Doing this, however, will delete some base elements that are not required to get updated. Further this does not affect translatability. Therefore, we do not include them in our candidates. 7 result root FOR $dept IN Document(“base.xml” )//department, * professor * $prof IN $dept//professor institute RETURN $prof /name + * $prof/name, student FOR $student IN $prof/student (b) department $student/name name RETURN + $student/name result + (a) professor * professor (c) name * course student Henry student1 student2 (a) view query name name1 name2 name (b) view schema tree STView namestudent (c) view instance tree John Joe Fig. 6. base schema of D Fig. 7. Query Q4 and correspond- ing view in Figure 3(c), as coursea is a source of course1 . However, courseb , which is a de- scendant of coursea , is the source of course2 in Figure 2(c). Therefore, such update will cause side-effects over view element course2 ,as one of its sources get deleted. The second kind is source(vei ) is also a source of another view element. For example, courseb in Figure 1 is the source of course2 in Figure 3(c). However, it is also a source of course3 . If we want to delete courseb to delete course2 , there will be side-effects over course3 , as one of its sources get deleted. Our goal is to find, given a view element vei , whether there exists a non-empty subset of sources(vei ) such that deleting any source source(vei ) in this subset will delete vei without affecting any other non-descendant view element of vei . Deleting source(vei ) does not affect vej if des(source(vei )) ∩ sources(vej ) = ∅. Based on the above concepts, the definition of correctly translating the deletion of a view element problem can be refined as: Problem Statement: Let Schema(D) be an XML schema and Q a view query over it. Given a view schema node n, does the following condition hold for every instance of Schema(D) whose corresponding view instance is V : For any element vei , whose schema node is n, does there exist source(vei ) such that ∀ vej ∈ V , vei 6= vej and vej is not descendant of vei , where des(source(vei )) ∩ sources(vej ) = ∅. 5 Algorithm Analysis 5.1 A Naive Algorithm Using the above concepts, we can observe the following. Consider deleting a view ele- ment vei by deleting a certain base element source(vei ). Let this element correspond to the base schema node Source(vei ). Consider all base schema nodes that could be descendants of Source(vei ), basically Des(Source(vei )). If none of these nodes form a Source(vej ), then deleting source(vei ) will not affect vej . This is stated below. Lemma 1. Deleting a source(vei ) will not affect view element vej , if Des(Source(vei )) ∩ Sources(vej ) = ∅. For example, consider course2 and course3 in Figure 3(c). Suppose we want to delete course2 . As course in Figure 1 is a Source(course2 ), Des(course) ∩ Sources (course3 ) = {course, pre} which is not empty. This implies if we delete course2 , some base elements contributing to the existence of course3 may also get deleted and therefore there may exist side-effects on course3 , which gives the same result as in our previous analysis. 8 Using Lemma 1, we can come up with a naive algorithm. Let sum be the union of Sources of every non-descendant view element vej of vei , vej 6= vei . If there exists Source(vei ), such that Des(Source(vei )) ∩ sum = ∅, Source(vei ) is a correct translation of deleting vei . However, this algorithm cannot be applied for all view elements. Consider view elements whose view schema nodes are the same. SNV iew (vei ), such as student1 and student2 in Figure 7(c). If we want to delete student1 , it is easy to observe that we can delete the studenta element in the base document, corresponding to the base schema node student in Figure 1. However, according to the above lemma, Des(student) ∩ Sources (student2 ) 6= ∅ and thus student1 cannot be updated. Also, Lemma 1 cannot be applied to detect side-effects on view elements whose schema nodes are descendants of SNV iew (vei ). Because for such a view element vej , we have Sources(vei ) ⊆ Sources(vej ), as all the base schema nodes that contribute to the existence of vei , also contribute to the existence of every view element that is the descendant of vei . For the above two cases, we need other strategies. Though Lemma 1 cannot be applied to the above two types of view elements, it can still be applied to detect side-effects on nodes whose schema nodes are non-descendants of Source(vei ). 1 2 3 Fig. 8. Schema Tree Structure We therefore partition the view schema tree into three parts, as shown in Figure 8. Let n = SNV iew (vei ) be the view schema node for vei . The first group, marked as 1, is view schema nodes that are non-descendant of n. We can apply Lemma 1 to detect side-effects on view elements whose schema nodes are in this group. The second group, marked as 2, is view schema node n itself. We discuss how to detect side-effects on view elements whose schema node is in this group in Section 5.2. The third group, marked as 3, is schema nodes that are descendants of n. We discuss how to detect side-effects on view elements whose schema nodes are in this group in Section 5.3. Also, these three groups cover all schema nodes without any overlap. Thus we check all view elements for side-effects effectively, and a correct translation is returned if there exists one. 5.2 Detecting Side-Effects in Group 2 Here we check view elements that share the same view schema node as vei , the view element to be updated. This is similar to the relational view update problem, and we can utilize the solutions from the relational scenario. Updating Relational Views In [9], Keller proposes an algorithm to check whether there is a 1-1 mapping between the set of tuples in the relational view and the set of tuples in a base relation. This algorithm can be used to check whether we can delete a tuple in the view without side-effects in the relational scenario. We use Keller’s algo- rithm as the basis for studying view updates in XML scenario as well. Therefore, in this section, we will introduce and discuss this algorithm. 9 Keller’s Algorithm: Given a relational database D and a relational view V , in order to find all possible relations r1 , r2 , . . . , ri such that there is a 1-1 mapping between the set of tuples in V and the set of tuples in every rp , 1 ≤ p ≤ i, construct a directed graph, also called as a trace graph, as: 1. every relation used by the view forms a node in the graph. Suppose there are nodes r1 , r2 , . . . , rn in the graph. 2. let ri , rj be two nodes (ri 6= rj ). There is an edge ri → rj iff there is a join condition of the form ri .a = rj .k (rj .k is the key for rj . If there is a ri .k = rj .k join, then there are two edges ri → rj and also rj → ri .). If there is any node r which can reach all other nodes, then there is a 1-1 mapping from tuples in V to tuples in the relation which is denoted by node r. 2 Adapting Keller’s Algorithm to XML scenario In Keller’s Algorithm, an edge ri → rj represents that a tuple in ri joins with at most one tuple in rj . The same intuition can be applied to XML scenario. Given view element vei , its trace graph has a root element and one node for every Source(vei ). Let Sourcei , Sourcej ∈ Sources(vei ). We draw an edge from Sourcei to Sourcej if the XPath expression of Sourcei starts with the variable representing Sourcej . We draw an edge from Sourcei to root if the XPath expression of Sourcei starts with Document(”base.xml”). Let us consider element student in Figure 7(b); Sources(student) = {department, prof essor, student}. The corresponding XPath expressions are Document(”base”)//department, $dept //prof essor, $prof /student respectively. Every prof essor will join with at most one department. Similarly, every student is guaranteed to join with at most one prof essor. According to Keller’s algorithm, there are four nodes in the trace graph: root, department, prof essor and student. We can draw an edge from student to prof essor, one from prof essor to department and one from department to root. student can reach all the other nodes. This implies we can delete view element student1 by deleting base element student1 in D, as analyzed before. However there are differences between relational and XML scenarios. For instance, a node in the trace graph that does not reach all other nodes can still be a correct trans- lation. Consider view schema node prof -student in Figure 4(b). A view element of prof -student has Sources = {prof essor, student}, without any edge between them in the trace graph. However, as base schema in Figure 4(a) implies that there is only one prof essor element in the base, any view element whose schema node is prof -student can be deleted by deleting a base element whose schema node is student. So cardinal- ity constraints should be considered to determine whether a Source can be a correct translation. On the other hand, a node in the trace graph that reaches other nodes might not be a correct translation. Consider course1 in Figure 3(c), Sources(course1 ) = {pre, course}. In the trace graph there is an edge from course to pre. However, course1 cannot be deleted by deleting courseb in Figure 1. This is because coursec is a descendant of courseb and is source of both course2 and course3 . Also course2 in Figure 3(c) cannot be deleted because it shares the same source as course3 . Both of these occur because of recursive types in XML. In the rest of the section, we study how we can extend Keller’s algorithm to handle cardinality constraints and recursive types in XML. 10 ri …… ri h rj ri.t1 t1 ri.t1 rj.t1 …… ri.t2 t2 …… ri.t1 rj.t2 …… …… …… ri.t2 rj.t1 …… rj ri.t2 rj.t2 …… ri rj.t1 t1 …… …… …… …… rj.t2 t2 …… rj …… …… (b) situation when cardinality information for each table is not revealed ri (a) trace graph generated from …… ri hrj ri.t1 t1 Keller’s Algorithm ri.t1 rj.t1 …… rj ri.t1 rj.t2 …… rj.t1 t1 …… (c) situation when cardinality for each …… …… …… table is revealed rj.t2 t2 …… …… …… (c) Fig. 9. Keller’s algorithm and cardinality constraints Handling Cardinality Constraints How cardinality information impacts the trans- latability of view updates in relational scenario is illustrated in Figure 9, where ri and rj can reach all other nodes except each other. Without any cardinality information, a view tuple cannot be deleted either from ri or rj , as there can be side-effects shown in Figure 9(b). However, if we know the cardinality information that there is only one tuple in ri 5 , then view tuples can be deleted from rj , shown in Figure 9(c). While such cardinality information cannot be specified easily in relational schema, it does exist in XML schema, as we mentioned in section 3.2. We only capture cardi- nality constraints *, 1 and 0. Note XML schema can specify more complex cardinality constraints such as MaxOccurs and MinOccurs. However they do not affect whether a view element can be updated or not. So we ignore them in this paper. Given two base schema nodes t and tn which are of ancestor-descendant relation- ship, however, what is the cardinality between them? Here we give the formal definition: Definition 2. Let t/a1 :: t1 /a2 :: t2 / . . . /an :: tn be a path expression between two nodes t and tn in the base schema, where ∀ai , 1 ≤ i ≤ n, can be child, descendant- or-self, or attribute. The cardinality card(t, tn ) between t and tn , which can also be denoted as card(t, /a1 :: t1 /a2 :: t2 / . . . /an :: tn ), is defined as: 1. if n >1, card(t, /a1 :: t1 /a2 :: t2 / . . . /an :: tn ) = card(t, /a1 :: t1 )×card(t1 , /a2 :: t2 ) × . . . × card(tn−1 , /an :: tn ). For the multiplication, please refer to Figure 10. 2. if n=1: (a) if a1 is descendant-or-self, card(t, /a1 :: t1 ) = *. (b) if a1 is attribute, card(t, /a1 :: t1 ) = 1. (c) if a1 is child, and the content model of t is re. Then card(t, /a1 :: t1 ) = cardRE(t1 , re). cardRE(t1 , re) is defined as follows: i. if re = (re1 , re2 ), cardRE(t, re) = cardRE(t1 , re1 )+ cardRE(t1 , re2 ). ii. if re = (re1 | re2 ), cardRE(t1 , re) = max{ cardRE(t1 , re1 ), cardRE(t1 , re2 )}. iii. if re = (re1 )∗, cardRE(t, re) = cardRE(t1 , re1 ) × ∗. iv. if re = ti : A. if ti = t1 , then cardRE(t1 , re) = 1. B. if ti 6= t1 , then cardRE(t1 , re) = 0. 11 $prof x 1 0 * + 1 0 * root 1 1 1 0 * 1 * 1 * 0 0 0 0 0 1 0 * * * 0 * * * * * * $student Cardinality Multiplication Cardinality Addition Table TableFig. 11. trace graph of prof - student in Figure 4(b) with Fig. 10. cardinality tables cardinalities Consider Figure 6, cardinality between root and department can be computed as card(root, /child :: institute/child :: department) = card(root, /child :: institute) ×card(institute, /child :: department) = ∗. Our proposition below uses the cardinality information in the base schema for de- ciding whether a base element is a correct translation of deleting the required view element. Proposition 1. Given Sources(vei ), draw the trace graph according to Keller’s al- gorithm. Suppose there are n 0-indegree nodes in the trace graph, say r1 , r2 , . . . , rn . Among Sources(vei ), find one that is the lowest common ancestor of all 0-indegree nodes, denoted as SNancestor . For each ri , card(SNancestor , ri ) is called the relative cardinality of ri . Let the number of relative cardinalities whose value is 1 be l. 1. if l = n, we can delete vei from any source(vei ) whose corresponding node in trace graph has 0-indegree. 2. if l = n − 1, we can delete vei by deleting the source whose base schema node is the 0-indegree node with cardinality as ”*”. 3. if l ≤ n − 2, there is no correct translation. Let us consider the query in Figure 4 again. Figure 11 is the trace graph of prof - student in Figure 4(b). With Definition 1, card(result, prof essor)= 1, card(result, student) = *. Therefore, to delete the view element whose view schema node is prof -student, we can delete from Source student. Handling Recursive Type Let us first consider the side-effects where source(vej ) ∈ des(source(vei )), vei and vej share the same view schema node. Consider course1 in Figure 2(c). Deleting it will have side-effects because some descendants of its source, sourcea , also contribute to the existence of other view elements, such as course2 . To identify such side-effects, we define recursive Source as below. Definition 3. Let Schema be an XML schema and Q a view query defined over this schema. Let S be a Source for a view element whose view schema node is n. S is said to be a recursive Source if ∃D, an XML Document confirming to Schema, where the conditions below are all satisfied: 1. there exist two view elements in Q(D), vei and vej , such that i 6= j but SNV iew (vei ) = SNV iew (vej ) = n. 2. I(S) contains bei and bej , bei and bej is source of vei and vej respectively, and they have ancestor-descendant relationship. 5 This is a quite strict requirement, which will be relaxed in later discussions. 12 One might think that if a path expression for a Source has ”//” operation, then the Source is recursive. However, this need not be the case, such as in the XPath expression Document(”base.xml”)//department/course. To identify recursive Source, we de- fine AbsoluteXP ath below. Definition 4. The path in the trace graph from Source to root is called a branch, de- noted as branchSource . The XPath expression obtained by concatenating all the XPath expressions in branchSource is called the absolute XPath of Source. To identify whether a Source is recursive, we check its absolute XPath. If the abso- lute XPath retrieves two base elements that have ancestor-descendant relationship, then the Source is recursive. Proposition 2. Let P be the absolute XPath of a Source(vei ) for view element vei . We call Source(vei ) as recursive iff the following two conditions are both satisfied: 1. P is of the form /P1 //bere/P2 /bel , where P1 , P2 are path expressions and bere , bel are base schema nodes. 2. the last base element bel in P can have bere as its descendant. Proposition 2 is illustrated in Figure 13(a). Here both the bel ’s satisfy P and have ancestor-descendant relationship. The Source, student, for a student view element in Figure 7 has the absolute XPath Document(”base.xml”)//department//prof essor /student, which does not match Proposition 2, therefore student is not recursive. However the Source, course, for a course view element in Figure 2 has the abso- lute XPath Document(”base.xml”)//course. This matches Proposition 2 where P1 is Document(”base.xml”), P2 is empty and bere = bel = course, and course has course as descendant. P1 P1 a1 z a (a) base schema tree STBase bere * c1 P2 (b) base instance b1 P2 c y b (c) view query a2 (d) view instance tree bel P3 (a) bere (b) c2 x z root (c) b2 P2 P2 (d) P4 y FOR $a IN Document(“base1.xml”)//a bel P3 a1 a2 RETURN FOR $c IN $a/c, x $b IN $c//b (a) Proposition 2 (b) Proposition 3 P4 RETURN $b b1 b2 b2 0 Fig. 12. STBase , Query Q4 Fig. 13. Illustrating Proposition 2 and Proposition 3 Now let us consider the second type of side-effects, where source(vei ) is also source(vej ). Consider the query in Figure 3(a). coursec in Figure 1 contributes to two view elements, course2 and course3 , in Figure 3(c). A more general example is shown in Figure 12. Figure 12(a) is the base schema and Figure 12(b) is one possible instance. Based on the query in Figure 12(c), we have the view instance tree shown in Figure 12(d). Specified by the query, b2 joins with a1 and a2 and thus appears multiple times in the view. Deleting any of them may cause side-effects over other appearances of b2 . For such situations we have the following proposition: 13 Proposition 3. Consider the trace graph of a view element whose view schema node is n. Let Source1 and Source2 be two Sources in this trace graph, with an edge from Source2 to Source1 . I(Source2 ) may contain a base element that is the source of two view elements, ve1 and ve2 , iff all the following conditions below are satisfied: 1. The absolute XPath of Source1 is of the form P1 //z/P2 /y. Let y be the variable that Source1 binds to and Source1 is marked as recursive using Proposition 2. 2. The absolute XPath of Source2 is of the form $y/P3 //x//P4 . 3. z ∈ Des(x). Figure 13(b) illustrates Proposition 3. Here, there are two view elements where Source2 binds to the rightmost P4 , and where Source1 binds to the two different y’s. Actually this scenario implies a much stronger condition: there exists no correct translation for deleting the view element. Let us examine this. First of all, no Sourcei that can reach Source2 can be a correct translation, as an instance of Sourcei can be the source of two different view elements. Now, consider a Sourcei that cannot reach Source2 . Since this node cannot reach Source2 , we must consider cardinality constraints. Let Source21 be a 0-indegree that reach Source2 . As the lowest common ancestor of all 0-indegree nodes, SNancestor , must be a node in the path from root to Source1 , card(SNancestor , Source21 ) = *. Thus Sourcei can never be a correct translation. This is stated in the corollary below: Corollary 1. Consider the trace graph of view element vei . If ∃Source1 , Source2 in this graph that satisfy Proposition 3, there is no correct translation for deleting vei . With Proposition 1, Proposition 2 and Proposition 3, we can detect all the possi- ble side-effects on view elements whose schema node is in Group 2 when deleting Source(vei ). Please refer to Section 6 for how to integrate them. 5.3 Detecting Side-Effects in Group 3 In this section, we will discuss how to detect side-effects on view elements whose schema nodes are descendants of n. Note view elements that are descendants of vei will get deleted with vei , according to the hierarchial structure of XML view. There- fore, we focus on whether any view element, vej , that are descendants of siblings of vei , gets affected when deleting source(vei ). (a) base schema tree STBase aa ab cc a (b) base instance c (c) view query b (a) (d) view instance tree ba bb (b) root (d) (c) a2 FOR $a IN Document(“base1.xml”)//a a1 RETURN Document(“base1.xml”)//b, Document(“base1.xml”)//c ba1 bb1 cc1 ba2 bb2 cc2 0 Fig. 14. STBase , Query Q5 Figure 14 illustrates side-effects on Group 3. If we delete a1 in Figure 14(d) by deleting aa in Figure 14(b), then the view element ba2 , the descendant of a2 in Fig- ure 14(d) is deleted. This is a side-effect. This happens because view element ba2 has 14 a source, ba , which is the descendant of source(a1 ). On the other hand, there is no side-effects on view element cc2 . We identify such side-effects as follows. Let vej be a descendant of sibling view element of vei . If Source(vej ) is not a descendant of Source(vei ), we need not con- sider it as it will never get affected. Consider cc2 in Figure 14(d) as vej and a1 as vei . As c is Source(vej ) ∈ / Sources(vei ) and also c is not a descendant of Source(vei ), a, no side-effect on view element cc2 will appear. On the other hand, if Source(vej ) is descendant of Source (vei ) or itself, source (vej ) must contribute to at most one view element that must be a descendant of vei . This implies there should need an edge from Source(vej ) to Source(vei ) in the trace graph of vej . Consider ba2 as vej and a1 as vei . As Source(vej ), b, is a descendant of Source(a1 ), there needs to be an edge from b to a in the trace graph of vej , which actu- ally does not exist. Therefore, there may be side-effects on ba2 . The above conclusions are formalized in the following lemma: Lemma 2. For every descendant element ved of SNV iew (vei ), get its trace graph. Sup- pose there are n 0-indegree nodes that cannot reach Source(vei ), say r1 , r2 , . . . , rn . For some ved , if ∃ ri such that SNBase (ri ) ∈ Des(SNBase (Source(vei ))), Source (vei ) cannot be the correct translation of deleting vei . 6 Algorithm for Correctly Deleting Single View Element in XML Scenario In this section, we will present the three-step algorithm for finding the correct transla- tion of deleting a view element vei . Step 0: 0. Candidates = Sources(vei ) Step 1: 1. Let Sources0 be the union of Sources of all non-descendant view elements of vei . 2. For every Source(vei ) ∈ Candidates, if Des(Source(vei )) ∩ Sources0 6= ∅, Candidates = Candidates − Source(vei ). 3. If Candidates = ∅, the algorithm terminates; else go to Step 2. Step 2: 4. Draw the trace graph of vei and let SourcesKeller be the set of 0-indegree nodes. 5. Use Proposition 1 to check SourcesKeller . Let l be the number of nodes whose relative cardinality is ”1”. (a) if l = n − 1, SourcesKeller = {SNrest }, where SNrest is the only schema node in SourcesKeller whose relative cardinality is ”*”. (b) if l ≤ n − 2, Candidates = ∅; the algorithm terminates. 6. Use Proposition 2 to check if Source(vei ) is recursive. If so Candidates = Candidates − Source(vei ). 7. For every branch of the trace graph, find two consecutive Sources that satisfy the condition in Proposition 3. If there exists such two Sources, Candidates = ∅; the algorithm terminates. 8. Candidates = Candidates ∩ SourcesKeller . If Candidates = ∅, the algorithm terminates; otherwise go to Step 3. Step 3: 9. For every Source ∈ Candidates, if deleting Source has side-effects on a descen- dant according to Lemma 2, Candidates = Candidates − Source. 10. The algorithm terminates. If Candidates = ∅, there is no correct translation of deleting vei ; otherwise each Source ∈ Candidates 0is a correct translation. Theorem 1. After the above algorithm, if Sources(vei ) is empty, deleting vei is un- translatable. Otherwise deleting ∀source ∈ sources0 (vei ) is a correct translation of deleting vei . 15 7 Conclusion In this paper we presented an algorithm for correctly translating the deletion of an XML view element as deleting an element in the underlying XML base. Our algorithm uses a schema-level analysis to efficiently find a correct translation and it is based on the previous work for updating relational views, extending this with recursive types and cardinality constraints in XML, and ”//” operator in XQuery. Our algorithm is sound and complete. This paper forms a first major step in studying view updates in XML scenario. Fu- ture work needs to consider incorporating other update operations such as insert, replace and XML specific operations and considering updating multiple elements. Further, we need to consider more semantics both in XML Schema and XQuery statements. References 1. http://www.w3.org/xml/query/. 2006. 2. S. Abiteboul. On views and xml. PODS, 1999. 3. V. Braganholo, S. Davidson, and C. Heuser. the updatability of xml views over relational databases, June 2003. 4. Y. Cui and J. Widom. Lineage tracing for general data warehouse transformations. In The VLDB Journal, pages 471–480, 2001. 5. U. Dayal and P. A. Bernstein. On the Correct Translation of Update Operations on Relational Views. In ACM Transactions on Database Systems, volume 7(3), pages 381–416, Sept 1982. 6. F. Bancilhon and N. Spyratos. Update Semantics of Relational Views. ACM Transactions on Database Systems (TODS), pages 557–575, 1981. 7. M. Fernandez, W. Tan, and D. Suciu. SilkRoute: Trading between Relations and XML. http://www.www9.org/w9cdrom/202/202.html, May 2000. 8. International Organization for Standardization (ISO) & American National Standards Insti- tute (ANSI). 9. A. M. Keller. Algorithms for Translating View Updates to Database Updates for View In- volving Selections, Projections and Joins. In Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pages 154–163, 1985. 10. H. Kozankiewicz, J. Leszczyowski, and K. Subieta. Updatable xml views. Advances in Databases and Information Systems, pages 381–399, September 2003. 11. P. Lehti and P. Fankhauser. Towards type safe updates in xquery. http://www.ipsi.fhg.de/ lehti/Typing 12. Oracle Technologies Network. Using XML in Oracle Database Applications. http://technet.oracle.com/tech/xml/htdocs/about oracle xml products.htm, November 1999. 13. M. Rys. Bringing the Internet to Your Database: Using SQL Server 2000 and XML to Build Loosely-Coupled Systems. In VLDB, pages 465–472, 2001. 14. R. Vercammen. Updating xml views. VLDB PhD Workshop, page 6ł10, 2005. 15. L. Wang, E. A. Rundensteiner, and M. Mani. UFilter: A Lightweight XML View Update Checker. In ICDE, poster paper, 2006.