Collaborative processing of XML documents in Internet

• Autorzy: Sikorski, A.

Warianty tytułu

PL

Współbieżne przetwarzanie dokumentów XML w Internecie

• Konferencja: 5th International Conference: Internet in the Information Society
• Języki publikacji: EN

Abstrakty

EN

In order to enable eective collaboration on XML documents published in Internet, we propose an indexing technique making use of nodes labeling. In particular we consider two types of locks, acquired by multiple user transactions on segments of a document. These segments correspond to paths and ranges – defined by labels, with the document subtree being a special case of a range. We put forward algorithms for consolidation of shared locks that define a continuous covering, a way of initial processing simplifying and accelerating the lock manager. Two algorithms for the lock manager are framed with the use of XML labels for both the 2PL protocol and the cooperative one. We also point to some interesting ties between the lock management and the shortest path problem. Our motivation is given in the context of the SEDNA native XML DB isolation rules, however, our technique is useful for most of the fine-granular lock protocols.

PL

Ze względu na swa elastyczność oraz poparcie formatu przez znaczące gremia standaryzacyjne XML stał się powszechnie stosowanym sposobem udostępniania i wymiany danych, popularnym zwłaszcza w Internecie. Dokument XML można postrzegać również jako instancję, co prawda dość ograniczoną funkcjonalnie, obiektowej bazy danych, na której możliwe jest współbieżnie wykonywanie operacji aktualizujących. Jeżeli aktualizacje zasobu danych mają się odbywać współbieżnie, to konieczne jest ich synchronizowanie za pomocą odpowiedniego menedżera, zarządzającego blokowaniem węzłów XML i udostępnianiem odpowiednich danych. Zaproponowane w pracy rozwiązanie oparte jest na wykorzystaniu tzw. etykiet węzłów dokumentu XML [5],[6], do celów identyfikacji blokowanych obiektów i obsługi stanu menedżera blokad. Pojawienie się etykiet związane jest z pracami [7],[8] nad efektywnym wykonywaniem zapytań XPath, mającymi na celu optymalizację algorytmu wyznaczania tzw. złączenia strukturalnego (odpowiednik złączenia relacyjnego znanego z SQL). Okazuje się, że wartości etykiety mogą w wydajny sposób definiować pewne podzbiory węzłów dokumentu XML, podlegające blokowaniu przez menedżera współbieżności, umożliwiając tym samym implementację złożonych reguł współbieżności. Kluczowe dla wydajnego zarządzania współbieżnością jest operowanie takimi podzbiorami węzłów jak: ścieżka, poddrzewo czy zakres wierzchołków (wierzchołki o etykietach mających wartości z określonego przedziału). Chociaż rozwiązanie jest prezentowane w kontekście dokumentów XML i reguł współbieżnego przetwarzania bazy XML Sedna [2], to możliwe jest jego stosowanie do celów synchronizacji współbieżnego przetwarzania hierarchicznych (drzewiastych) struktur danych (Fig.4.). Blokady zakładane na zbiorach sa są przykładami szczególnych blokad predykatowych (intensjonalnych), których obsługa jest możliwa w czasie log(n), względem liczby założonych blokad. Predykaty te są formułami o postaciach zależnych jedynie od typu zbioru (tj. drzewo, ścieżka , zakres), zawierającymi wartości etykiet. Należy też zwrócić uwagę, że liczba n od której zależy złożoność obsługi blokady, jest na ogół dużo mniejsza od liczby zablokowanych węzłów dokumentów, ponieważ blokady zakładane mogą być na całych zbiorach.

Słowa kluczowe

EN

databases; concurrency; internet

• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2008
• Tom: Vol. 20, No. 4
• Strony: 229-244
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Sikorski, A.

• Technical University Poznań Institute of Automation and Information Engineering ul. Piotrowo 3A, Poznań, Poland,

Bibliografia

• [1] Fomichev A., GrinevM., Kuznetsov S.D. Sedna: A Native XML DBMS. InWiedermann J., Tel G., Pokorný J., Bieliková M., & Stuller J. (eds) Theory and Practice of Computer Science, 32nd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2006, January 21-27, Merín, Czech Republic, Berlin: Springer, (LNCS), pp. 272-281, 2006.
• [2] Pleshachkov P., Chardin P., Kuznetsov S.D.: A DataGuide-Based Concurrency Control Protocol for Cooperation on XML Data. In Eder J., Haav H.-M., Kalja A., & Penjam J. (eds) Advances in Databases and Information Systems, 9th East European Conference, ADBIS 2005, September 12-15, Tallinn, Estonia, Berlin: Springer, (LNCS), pp. 268-282, 2005.
• [3] Pleshachkov P., Novak L. (2004): Transaction Isolation in the Sedna Native XML DBMS. SYRCoDIS, (available at http://syrcodis.citforum.ru/2004/pleshachkov.pdf), St. Petersburg, 2004.
• [4] Tropashko V.: Nested Intervals for Tree Encoding in SQL. ACM SIGMODRecord, 34(2): 47-52, 2005.
• [5] Wu X., Lee M.L., Hsu W.: A Prime Number Labeling Scheme for Dynamic Ordered XML Trees. Proc. of the 20th Intl. Conf. on Data Engineering, ICDE 2004, 30 March – 2 April, Boston, MA, USA. IEEE Computer Society, pp.66-78, 2004.
• [6] O’Neil P., O’Neil E., Shankar P., Cseri I., Schaller G., Westbury N.: ORDPATHs: Insert-Friendly XML Node Labels. SIGMOD, Paris, pp. 903-908, 2004.
• [7] Al-Khalifa S., Jagadish H.V., Koudas N., Patel J., Srivastava D., Wu Y.: Structural Joins: A Primitive for Ecient XML Query Pattern Matching. Proc. of the 18th Intl. Conf. on Data Engineering, ICDE 2002, 26 February – 1 March, San Jose, CA. IEEE Computer Society, pp. 141-152, 2002.
• [8] Jagadish H.V., Al-Khalifa S., Chapman A., Lakshmanan L.V.S, Nierman A., Paparizos S., Patel J.M., Srivastava D., Wiwatwattana N., & Wu Y.: A Native XML Database. VLDB Journal 11(4), pp. 274-291, 2002.
• [9] Rusinkiewicz M., Klas W., Tesch T., Wäsch J., Muth P.: Towards a Cooperative Transaction Model – The Cooperative Activity Model. In Dayal U., Gray P.M.D., & Nishio S. (eds) VLDB’95, Proc. of 21th Intl. Conf. on Very Large Data Bases, September 11-15, Zurich, Switzerland. Morgan Kaufmann, pp. 194-205, 1995.
• [10] Lidl R.: Algebra für Naturwissenschaftler und Ingenieure. Walter de Gruyter, Berlin, 329 p., 1975.
• [11] Dijkstra E.: Two Problems in Connection with Graphs. Num. Math 1,pp 269-271, 1959.
• [12] Sleator D.D., Tarjan R.E.: Amortized Eciency of List Updates and Paging Rules. CACM, 28(2), pp. 202-208, 1985.
• [13] Tarjan R.E.: Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics. Philadelphia, PA, 140 p., 1983.
• [14] Willard. D.E.: Maintaining dense sequential files in a dynamic environment. Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, San Francisco, California, USA, pp. 114-121, 1982