A Locking Protocol for Scheduling Transactions on XML Data♣ © Peter Pleshachkov Petr Chardin Institute for System Programming RAS Moscow State University peter@ispras.ru pchardin@acm.org Abstract permit to acquire more shared locks on the same item. A locking protocol describes rules, according to which a In this paper we propose a new DataGuide- transaction should lock and unlock the data pieces. based locking protocol for isolation of Eswaran et al.[6], introduced the locking protocol, concurrent XML transactions. The protocol which is most popular by now, – the two phase locking adopts DataGuide structure for locking protocol (2PL). This protocol specifies that no data item purposes. We extend the multigranularity can be unlocked until all data items to be accessed have locking protocol by adding node and logical been locked. Eswaran et al. have also demonstrated that locks on DataGuide. This allows to enhance the two phase criterion is necessary and sufficient to concurrency of XML-specific transactions, ensure serializability. thereby increasing the overall system Another kind of protocols is tree-based protocols [14]. performance. They are used in databases organized (logically or physically) as trees. However, the tree protocol is not 1 Introduction adequate for XPath-like queries as the one only supports a top-down access to the document. And The widespread use of eXtensible Markup Language XPath [3] language supports queries with more complex (XML) [2] in scientific data repositories, digital navigational behaviour (via child, descendant, attribute, libraries and across the Web prompted the development parent, preceding-sibling and following-sibling axes). of a method for efficient synchronizing of concurrent Thus, the tree protocol does not support significant updates and queries for XML-data. As XML continues subset of XPath. to gain popularity and the amount of XML-data In a short paper [13] we presented a novel locking constantly grows, the proper scheduling of concurrent method for XPath operations - XDGL. The paper queries and updates becomes an important issue. presented very first results and incomplete in many When several transactions have access to the same extents. document at the same time, we need to protect each of In this paper we investigate a more wide subset of them against the others. To simplify this task, we XPath language including preceding-sibling and usually want to serialize transactions. Serializability following-sibling axes, wildcards and predicates in [10] requires the result of transactions processing to be location steps. Moreover, we examine a more complex equal to the one produced by some serial execution of update operations such as move, replace and rename. the same transaction set. In XML-enabled DBMSs, XML data usually is not Most systems ensure serializability by controlling represented as a tree structure physically. This is why access to each data item according to some particular XDGL employs the DataGuide structure for locking. concurrency control scheme. Locking-based protocols Because of this, our approach can be easily are used most widely. In these methods a transaction implemented on top of any system, which stores XML. must lock a data item before first access to the item, and It could be a Native XML DBMS, a relational or object- unlock it when transaction is done with it. Locking oriented DBMS. protocols usually use two types of locks: exclusive Another advantage of our approach is that DataGuide is locks and shared locks. Exclusive locks prevent any usually much smaller than the document itself. Hence it other lock to be held on a data item, while shared locks may be held in main memory even for large XML documents. This way, the locking overhead is small. ♣ In our locking method we employ two kinds of locks: This work was partially supported by the grant of the the Russian Basic Research Foundation (RBRF) N 05- tree locks and node locks. The tree locks are useful for 07-90204. protecting the whole subtrees addressed by XPath Proceedings of the Spring Young Researcher's location paths. The node locks are useful for protecting Colloquium on Database and Information Systems single DataGuide’s nodes (note, that it may match many SYRCoDIS, St.-Petersburg, Russia, 2005 nodes in document). For example, node locks are used with a set of context nodes (defined as result of the by insert operations. previous location step). An axis specifies the direction We introduce special logical locks and insert new node of movement from the context nodes, node-test locks to avoid phantoms appearance. The logical lock specifies the type of the nodes to be selected and could be set on the DataGuide’s node and specifies a predicate filters the selected nodes. The result of node’s name which should be protected. I.e. the node location path is result of last location step with such name cannot be inserted under this node. A In this paper we investigate only a subset of XPath. The transaction which inserts a new node must obtain insert following axes are of interest: child, descendant, new node lock on each ancestor of the new node. This is attribute, following-sibling and preceding-sibling. needed as it may be a phantom for another transaction Besides we take into consideration only simple The remainder of the paper is organized as follows. predicates (comparison of node’s value with constant). Section 2 presents the XML query and update Finally, let us consider a couple of queries for FS languages, which are of interest in this paper. In Section document. The query /file_system//catalog retrieves all 3 we define DataGuide structure and present the catalog elements in FS. The location path example of DataGuide for XML document. Section 4 is /file_system/catalog[@name=’system’] consists of two devoted to proposed locking protocol. It contains a location steps. It addresses system catalog element number of small examples, which help to understand located under file_system element. Note, that the protocol and its benefits. In Section 5 we give a @name=’system’ is a simple predicate. brief overview of related work. Section 6 contains a summary of our work. 2.2 Update language To change the document one should use update operators. We examine five types of update operators: 10 March, 2003 insert, delete, move, replace and rename operators. 777 • Insert operator: ls.cpp INSERT constructor (INTO | BEFORE | AFTER) ls.h path-expr • Delete operator: 7 April, 2004 754 DELETE path-expr • Move operator: MOVE path-expr1 (INTO | BEFORE | AFTER) 9 April, 2005 path-expr2 750 • Replace operator: REPLACE path-expr WITH constructor • Rename operator: RENAME path-expr AS NCNAME 1 January 2003 743 Here constructor is an element or attribute constructor. passwords We specify an element constructor as element {elem- name} {content}; meaning of the elem-name and content is straightforward. There are complex element constructors. In such constructor content itself is the Figure 1: an XML document FS nested element constructor. In a simple case content could be just a text. 2 Data Manipulation Language One can specify the attribute constructor as attribute {name} {text}; Here name and text specifies the name This section gives an overview of query and update and the value of the attribute. languages. We also consider several examples of We introduce three types of insert operators: insert-into, queries and updates of the sample XML document FS insert-before and insert-after. These operators insert depicted in Figure 1. The document conforms to the new node defined by constructor as the last child, DTD shown in Figure 3. previous sibling and next sibling for each node selected by path-expr respectively. If constructor specifies an 2.1 Query language attribute constructor, then we could only use insert-into We use XPath language to retrieve nodes from the operator that adds new attribute to each node selected XML documents. XPath defines the syntax and by path-expr. It also means that each of the selected semantics for location paths. Each location path consists nodes should be of element type. of a sequence of location steps separated by ‘/’. In turn, Delete operator removes subtrees of all nodes specified location step consists of axis, node-test and optional by path-expr from the document. That is to say, our predicate. Syntactically it looks like axis::node- delete operator uses the deep deletion semantics. test[predicate]. XPath defines the following semantics for evaluation of location step. A location step starts n1 file_system n2 catalog n3 n4 n5 n6 n7 n8 @ nam e date access catalog directory file n10 n11 n12 n13 n14 n15 @ nam e date access @ nam e date access Figure 2: DataGuide of the document FS Move operator transfers subtrees from the place transaction to follow strict two-phase locking protocol specified by path-expr1 to the place specified by path- (S2PL) [1]. According to S2PL a transaction, acquired a expr2. The semantics of INTO, AFTER and BEFORE lock, keeps it until the end. keywords is the same as in insert operator. While traversing or modifying an XML document, a Replace operator substitutes node defined by transaction has to acquire a lock in an acceptable mode constructor for the subtrees specified by path-expr. for each node before accessing it. Since the nodes in an Rename operator gives a new name (NCNAME) for the XML document are organized as a tree-like structure, nodes specified by path-expr. the principles of multigranularity locking scheme Let us consider a couple of examples. The following (MLS) [9] may be exploited. The MLS introduces update operator adds new file element to system intention locks which prevent a subtree t from beeing catalog: INSERT element{file}{‘hosts’} INTO locked in a mode incompatible to locks already granted /file_system/catalog[@name=’system’]. The operator to t or subtrees of t. However, the straightforward RENAME /file_system//catalog AS directory gives a adoption of MLS for synchronization concurrent XML directory name for all catalog elements in FS transactions may result in a low concurrency. For document. instance, one transaction might need to lock some intermediate node n of an XML document in a read 3 DataGuide mode, while another transaction may wish to perform an update of some node in the subtree of n. However, DataGuide [7] is a data structure that summarizes an MLS's share and exclusive locks implicitly lock the XML document. It is concise and accurate because entire subtree which is too restrictive. Example1 studies DataGuide describes every unique label path of a some drawbacks of multigranularity locking scheme document exactly once, regardless of the number of adopted for XML. times it appears in that document, and encodes no label Example 1: Let us suppose that transaction T1 has path that does not appear in that document. Figure 2 issued the XPath query /file_system/catalog/access. It shows the DataGuide of FS document. should be possible for transaction T2 to insert an empty element as a child of file_system element. According to MLS, the entire DataGuide’s access same time, catalog subtree has to be locked in the exclusive mode by T2. And since catalog subtree includes access subtree (see Figure 2) and shared lock held by T1 is not compatible with exclusive lock held by T2. Therefore, T1 and T2 cannot be executed concurrently. In fact, transactions T1 and T2 do not conflict. They Figure 3: DTD of the document FS would conflict if T2 inserted 777 element inside file_system element. 4 Locking Protocol on DataGuide In this paper we introduce granular locking protocol on DataGuide. To cope with hierarchical nature of XML A transaction must lock a data item before the first documents we use IX and IS intention locks. Besides, access to that data item, and unlock it when all accesses we introduce node and tree locks for locking the to the item are complete. Our protocol requires DataGuide’s node and DataGuide’s subtree respectively. Moreover, we use node locks to prevent on the node itself. SI (SA, SB) lock is not compatible document order conflicts during execution of with SI (SA, SB) lock, which prevents concurrent insert- concurrent insert operations. For instance, the document into (insert-after, insert-before) operations upon the order conflict arises if one transaction inserts new node same node. as the last child into a node, while another transaction granted also inserts new node as the last child into the same requested SI SA SB X ST XT IS IX node. SI - + + - + - + + To cope with phantoms appearance we use logical SA + - + - + - + + locks. They allow to lock node’s name in the SB + + - - + - + + DataGuide’s subtree. These locks are useful for such queries as //file. According to the DTD of document FS, X - - - - - - + + file element could appear at any level in FS document. ST + + + - + - + - Therefore, FS’s DataGuide could potentially contain XT - - - - - - - - arbitrary number of the file nodes. The logical lock on IS + + + + + - + + the file name set on DataGuide’s root denies other IX + + + + - - + + transactions from inserting of any element with the name file. Figure 4: Lock compatibility matrix 4.1 Node and Tree Locks 4.2 Predicates Below we describe a set of all node and tree locks, employed by our method. To cope with the value-based constraints on the node’s • SI (shared into), SA(shared after) and SB(shared content (extracted from location path) each node lock before) locks. These node shared locks are used by and tree lock are annotated with predicate. In this case, insert operations. It is set on the DataGuide’s nodes the lock compatibility matrix does not contain strict defined by path-expr of insert operator. This lock incompatibilities. Two locks are compatible if one of prevents any modifications of the node and the following condition hold: (1) the mode of the one insertion of another nodes into the node by lock is compatible with the mode of another lock due to concurrent transactions. SA and SB locks are the lock compatibility matrix, (2) the predicates of these defined in a similar way. locks do not conflict (i.e. the conjunction of predicates is not satisfiable). Thus, taking into consideration the • X (exclusive) lock. This node lock must be obtained predicates on the node’s value allows to reduce the for the node to be modified. Note, that the nested number of conflicts between transactions significantly nodes of the locked node may be read by another thereby increasing concurrency. transactions. We will regard that location step without predicate has • ST (shared tree) lock. This tree lock sets on a the true predicate. Besides, IS and IX locks are always DataGuide’s subtree to protect the whole subtree annotated with true predicate. from any updates. XPath queries require this kind of locks. Due to the semantics of XPath the results 4.3 Logical Locks of the location path are the subtrees selected by the last location step. It implies the request of the ST Now we turn to the discussion of logical locks which lock for subtrees retrieved by location path. are used to prevent phantoms appearance. For example • XT (exclusive tree) lock. This tree lock sets on a the transaction which issued //file query may suffer DataGuide’s subtree to protect the subtree from from phantoms since another transaction may insert reading and modifications. new file element at some deep level of the document FS • IS (intention share) lock. According to the granular (see FS’s DTD). Generally speaking, phantoms can locking protocol we have to obtain these lock on appear when (a) insert operation extends the DataGuide each ancestor of the node which is to be locked in a (adds new path to DataGuide), (b) the insertion of a new shared mode. node changes a target node of some operation • IX (intention exclusive) lock. According to the performed by another transaction. granular locking protocol we have to obtain these Thus, we introduce two locks. The first lock is logical locks on each ancestor of the node which is to be (L) lock, which must be set on DataGuide’s node to locked in an exclusive mode. protect subtrees from a phantom appearance. A logical lock specifies a set of properties. L lock prohibits the Figure 4 shows compatibility matrix for the lock modes insertion of new nodes which possesses these defined above. A compatibility matrix indicates whether properties. The second lock is insert new node (IN) a lock of mode M1 may be granted to a transaction, lock, which specifies the properties of new node. The L while a lock of mode M2 is presently held by another and IN locks are compatible if the properties of L lock transaction. differs from the properties of inserted node. The Note, that IX and X locks are compatible since IX lock properties may includes the node name, node value, on a node only implies the intention to lock the child name and child value. For example the transaction descendants of the node. But it does not imply the lock which issued //file[.=’ls.cpp’] query must obtain L lock on the DataGuide’s root with properties: node- matches the additional branches of path-expr1 or name=’file’, node-value=’ls.cpp’. path-expr2 then obtain (ST, p) lock on the node and IS lock on its ANCSIBL nodes. The rules for 4.4 Locking Rules move-after and move-before operators are In this subsection we describe a list of locking rules. analogous. These rules define which locks must be obtained for • Rule for replace operator. For each node from NP which operations. Each operation contains at least one performs (1) if the node matches the target nodes of path-expr which defines the operation’s target nodes. path-expr then obtain (XT, p) lock on the node and Then the operation is applied to the target nodes. IX lock on its ANCSIBL nodes, (2) if the node Let DP be a data path set of all label paths in DataGuide matches the additional branches of path-expr then that lead to data queried or updated. Then we may obtain (ST, p) lock on the node and IS lock on its compute a set NP of all nodes in DataGuide (and ANCSIBL nodes, (3) if the node matches the new associate predicates with them) which match any label inserted node (defined by constructor) then obtain path from DP. Moreover, let PH be a set of pairs (n, (X, p) lock on the node and IX lock on its properties);here n defines the DataGuide’s node where ANCSIBL nodes. a phantom could appear, properties specifies the • Rule for phantoms prevention. For each node from conditions on the nodes to be logically locked. PH the (L, properties) lock must be obtained. Besides each operation which extends the • Rule for XPath query. For each node from NP DataGuide must obtain (IN, properties) lock on performs (1) obtain (ST, p) lock (p is the associated ANCSIBL nodes of new node. predicate) on the node, (2) obtain IS lock (with true 4.5 Examples predicate) for each ancestor of the node and all nodes traversed via preceding-sibling and Now let us consider several examples to illustrate the following-sibling axes. We denote such nodes as locking rules. Let us return to example1. Now we will ANCSIBL nodes. show that both transactions from the example can • Rule for insert-into operator. For each node from proceed with proposed locking protocol. According to NP performs (1) if the node matches target nodes it, transaction T1 must obtain IS lock on nodes n1, n2 of insert operator then obtain (SI, p) lock on the and (ST,#t) lock on node n5; here #t is the true node and IS lock on its ANCSIBL nodes, (2) if the predicate. At the same time T2 must obtain IX lock on node matches additional branches of path-expr then n1 and (X,#t) lock on n2. As all locks are compatible obtain (ST, p) lock on the node and IS lock on its transactions T1 and T2 could be executed concurrently. ANCSIBL nodes, (3) if the node matches the new This is illustrated in Figure 5. inserted node then obtain (X, p) lock on the node and IX lock on its ANCSIBL nodes. The rules for T1 IS file_system, n1 insert-after and insert-before operators are T2 IX analogous. • Rule for delete operator. For each node from NP T1 IS performs (1) if the node matches the target nodes of T2 (X,#t) catalog, n2 delete operator then obtain (XT, p) lock on the node and IX lock on its ANCSIBL nodes, (2) if the node matches the additional branches of path-expr then T1 (ST,#t) ... obtain (ST, p) lock on the node and IS lock on its ANCSIBL nodes. access, n5 • Rule for rename operator. For each node from NP Figure 5: Locking rules for example1 performs (1) if the node matches the target nodes or the new subtree of rename operator then obtain Example 2 (conflict of two insert operations): (XT, p) lock on the node and IX lock on its Let us suppose that transaction T1 inserts new access ANCSIBL nodes, (2) if the node matches the element: INSERT INTO additional branches of path-expr then obtain (ST, p) /file_system/catalog[name=’home’]/date/following- lock on the node and IS lock on its ANCSIBL sibling::catalog, while transaction T2 inserts new date nodes. element: INSERT INTO • Rule for move-into operator. For each node from /file_system/catalog/catalog. NP performs (1) if the node matches the target Figure 6 shows that transactions T1 and T2 cannot run nodes of path-expr2 (see definition of move concurrently since SI lock is not compatible with itself. operator) then obtain (SI, p) lock on the node and Example 3 (phantoms prevention): IS lock on its ANCSIBL nodes, (2) if the node Let us suppose that transaction T1 retrieves all file matches the target nodes of path-expr1 (i.e. subtree elements found at any level inside catalog elements to be deleted) or the new subtree (i.e. subtree to be which can be found themselves inside file_system inserted) then obtain (XT, p) lock on the node and element. In XPath such a query looks like this: IX lock on its ANCSIBL nodes,(3)if the node /file_system/catalog//file. At the same time transaction T2 inserts new file element into the catalog element by prevention mechanism, (3) the query language does not the following statement: support the descendant axis, which is very important for INSERT element{catalog}{} INTO querying semistructured data. /file_system/catalog/catalog In [11], the synchronization of concurrent transactions is considered in the context of DOM API. The authors T1 IS, IX file_system, n1 present three types of locks: node locks, navigational T2 IS, IX locks and logical locks. Node and navigational locks are T1 IS, IX acquired for context nodes and virtual navigation edges T2 IS, IX catalog, n2 respectively. In turn, logical locks are introduced to T1 (SI,#t), IX prevent phantoms. Authors offer variety options to T1 (ST,name=’home’ ) T1 IS T2 (SI, #t), IX enhance transaction concurrency. But synchronization @name, n3 date, n4 catalog, n6 of other APIs (e.g. XPath) is part of the future work. There are a number of isolation protocols for the DOM T2 (X,#t) T1 (X,#t) API proposed in the work [12]. Unfortunately, these date, n11 access, n12 locking protocols were developed for DOM API only, Figure 6: Incompatibility of insert operations and it is not clear whether they could do for XPath expressions. It is easy to see that the second transaction might add a Dekeyser et al. [4, 5] proposed the fine-grained (node- phantom node for the first one. However, our locking level) XPath-based locking protocol, which ensures rules prevent this situation. This is shown in the Figure serializability. But this method does not use the 7. (L, file) lock is not compatible with (IN, file) lock. DataGuide. Instead all the locks are obtained on the Thus, the insertion of the file element is denied. document itself. Disadvantages of this approach have been already noted in this paper. T1 IS file_system, n1 T2 IS, IX, (IN, file) 6 Conclusions T1 IS, (L, file) In this paper we have presented a new locking protocol T2 IS, IX, (IN, file) catalog, n2 for concurrent processing of XML data. Our method is based on the XDGL protocol proposed in our earlier work [13]. The method is not limited to native XML T2 IX, (SI,#t), (IN, file) T1 (ST,#t) DBMS. It could be implemented on top of existing catalog, n6 file, n8 relational or object-oriented database system. Another important benefit of our protocol is the size of the locking structures. Unlike in most other locking T2 (X,#t) protocols, the size of the XML document does not file, n9 affect the number of locks needed for consistent execution of transaction directly. This happens because Figure 7: Logical locks of the DataGuide structure properties. When a new node is added to a big document, the DataGuide usually does 4.6 Unordered XML Documents not change. The explanation of this feature is that the DataGuide provides only information for the kinds of For some applications document order is not important. paths. And usually, the set of different paths is rather Our locking method could be easily modified to deal small, since we insert nodes of the same type. In our with unordered XML documents. In this case we do not method DataGuide is used for locking. As a need SI, SA and SB locks. Instead, conventional S lock consequence, the lock manager works with a relatively is needed. It is a common shared lock. By definition S small structure, which is very likely to fit into the main lock is compatible with itself. I.e. two insert operations, memory even for the huge documents. adding elements with different names into the same element do not conflict. References 5 Related Work [1] P. Bernstein, V. Hadzilacos and N. Goodman, “Concurrency Control and Recovery in Database There were proposed several locking schemes for System”, Addison-Wesley, 1987. synchronizing concurrent XML operations. Here is a [2] N. Bray, J. Paoli. Extensible markup language brief overview of these methods. (XML) 1.0 (second edition). W3C Grabs et. al. [8] proposed a DGLOCK protocol, which Recommendation, October 2000. is a combination of well-known granular and predicate [3] J. Clark, S. DeRose, “XML path language (XPath) locking on the DataGuide. This work has much in version 1.0”, World Wide Web Consortium (W3C) common with our one. But DGLOCK has several Recommendation, Nov. 1999. disadvantages: (1) as a consequence of granular locking we have a conflict in the example 1, (2) DGLOCK does not guarantee serializability and has no phantom [4] S. Dekeyser, J. Hidders “Path Locks for XML Document Collaboration”, In Proceedings of the Third WISE Conference, 2002. [5] S. Dekeyser, J. Hidders, “A Commit Scheduler for XML Databases”, In proceedings of the fifth Asia Pacific Web Conference, Xina, China, 2003. [6] K. P. Eswaran, J. Gray, R. Lorie and I. Traiger, “The notions of consistency and predicate locks in a database systems”, Comm of ACM, Vol. 19, No 11, pp. 624-633, November 1976. [7] R. Goldman and J. Widom, “DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases”, In Proceedings of 23rd International Conference on Very Large Data Bases, 1997, Athens, Greece, pp. 436-445, Morgan Kaufmann, 1997. [8] T. Grabs, K. Bohm and H. Schek, “XMLTM: efficient transaction management for XML documents”, In Proceedings of the ACM International Conference on Information and Knowledge Management, McLean, Virginia, pp. 142-152. [9] J. Gray, R. Lorie, “Granularity of locks in a large shared databases”, Proceedings of the International Conference on Very Large Databases, 1975. [10] J. Gray and A. Reuter, “Transaction processing: concepts and techniques”, Morgan Kaufmann, 1993. [11] M. P. Haustein, and Theo Haerder, “taDOM: a Tailored Synchronization Concept with Tunable Lock Granularity for the DOM API”, In Proceedings of ADBIS Conference, LNCS 2798, Springer, 2003. [12] S. Helmer, C.-C Kanne and G. Moerkotte, “Evaluating lock-based protocols for cooperation on XML documents”, SIGMOD Record 33(1): 58- 63, 2004. [13] P. Pleshachkov, P. Chardin, S. Kuznetsov, ”XDGL: XPath-Based Concurrency Control Protocol for XML Data”, To appear in Proceedings of 22nd British National Conference on DataBases. [14] A. Silberschatz and Z. Kedem, “Consistency in hierarchical database systems”, Journal of the ACM, 27(1), pp. 72-80, 1980.