Introduction
With the advent of native and XML-enabled
databases, a new look at traditional tasks provided by DBMSs has become necessary. In particular, several
papers discussed on this page have shown that classic concurrency control mechanisms developed for relational,
hierarchical, and object oriented databases are no longer adequate for semi-structured databases.
The aim of this page is to present our own research in this emerging field, and to provide links to other
papers on the subject.
Instance-dependent CC Methods
This section is based mostly on research done by Jan Hidders (UA) and Stijn Dekeyser (USQ). Click
here for a list of publications.
In our Kluwer WWW Journal article A
Transaction Model for XML Databases, we present the following concepts to solve the concurrency control problem
for XML data:
- A data model of documents and query and update languages as seen and used by the
user transactions and by the scheduler subsystem of the document server.
So far, the model does not take order among sibling elements into account, and both the query (based on XPath)
and update language are rather limited in expressive power.
- Two alternative and equivalent Path Locking schemes: PL-Prop (for propagation) and PL-Sat (for
satisfiability). There is a trade-off between space and time complexity between both schemes, in regards
to checking for conflicts between read and write locks. The locks are associated to nodes in the document,
hence the instance-dependent nature of this work.
- Two alternative Schedulers that can use both PL-Prop and PL-Sat locking schemes. The Commit
scheduler does not allow conflicts between read and write locks to arise, whereas the Conflict
scheduler does, but keeps a dependency graph. Importantly, we show that both schedulers guarantee
serializability of the schedules they allow.
Other results include a local necessity proof which shows that the conflict rules presented for
path locks are indeed necessary.
Many issues remain, so our research in this field is ongoing. We also hope to work on an implementation soon.
Instance-Independent CC Methods
This section is based mostly on research done by Jan Hidders, Jan Paredaens, Roel Vercammen (all at UA), and Stijn Dekeyser (USQ). Click
here for a list of publications.
In contrast to the research mentioned above, in this section we assume that we have no knowledge of the document instance,
or (for reasons of efficiency) do not want to use that knowledge. As a result, our approach here is more fundamental and general in
nature compared to the more applied nature of the research above.
We present a framework that is document-independent in the sense that two schedules of semistructured transactions are equivalent
if they are equivalent on all possible documents. We prove that it is decidable in polynomial time and space whether two given
schedules in this framework are equivalent. This also solves the serializability issue for semistructured schedules, polynomially in
the size of the schedule and exponentially in the number of transactions.
Other Research Papers
To date (August '04), a few other papers have appeared which try to solve the issues described above.
- Sven Helmer, Carl-Christian Kanne, and Guido Moerkotte;
Evaluating lock-based protocols for cooperation on XML documents, In:
SIGMOD Record (33):1, 2004. Available at: http://portal.acm.org/citation.cfm?doid=974121.974132#
- Michael Haustein, Theo Härder, Lock Manager
for Collaborative Processing of Natively Stored XML Documents, In: proceedings of
SBBD 2004. Available at:
http://wwwdvs.informatik.uni-kl.de/pubs/p2004.html
- Torsten Grabs, Klemens Böhm and Hans-Jörg Schek, XMLTM: efficient transaction management
for XML documents, In: Proceedings of the 2002 ACM CIKM
International Conference on Information and Knowledge Management (CIKM
2002), McLean, VA, USA, November 4-9, pp. 142-152, ACM, 2002. Available at:
http://www-dbs.inf.ethz.ch/~grabs/publications/cikm2002.pdf
- Sven Helmer, Carl-Christian Kanne and Guido Moerkotte, Isolation in XML Bases, Technical
report: Reihe Informatik 15/2001, University of Mannheim, Germany, 2001.
Available at: http://pi3.informatik.uni-mannheim.de/publications/MA-01-15.ps
- Sven Helmer, Carl-Christian Kanne and Guido Moerkotte, Lock-based Protocols for Cooporation on
XML Documents, Technical Report: Reihe Informatik 06/2003, University of Mannheim, Germany, 2003. Available at:
http://pi3.informatik.uni-mannheim.de/publications/TR-03-006.ps
- Kuen-Fang Jea, Shih-Ying Chen and Sheng-Hsien Wang, Concurrency Control in XML Document
Databases: XPath Locking
Protocol, In: Proceedings of the 9th International Conference on
Parallel and Distributed Systems (ICPADS 2002), Taiwan, ROC, December
17-20, pp. 551-556, IEEE, 2002. Available at:
http://csdl.computer.org/comp/proceedings/icpads/2002/1760/00/17600551abs.htm
- Eun-Hye Choi and Tatsunori Kanai, XPath-based Concurrency Control for XML
Data, In: Proceedings of the 14th Data Engineering Workshop (DEWS 2003), Kaga city, Ishikawa, Japan, March 3-5, 2003. Available at:
http://www.ieice.org/iss/de/DEWS/proc/2003/papers/6-C/6-C-04.pdf
|
