12th International Symposium on Database Programming
Languages (DBPL 2009)
Co-located with VLDB 2009

Lyon, France. August 24, 2009.

Invited speaker (shared with XSym 2009)

Ioana Manolescu (INRIA)


Web data management on DHTs


Many data management settings involve distribution, due to the participation of multiple data producers and consumers. This is true in particular in the context of Web data, consisting of structured documents, Web services, and semantic data. The development of Distributed Hash Tables (or DHTs in short) lead to their adoption indistributed data management applications, including XML. In this talk, I will present the work carried on in the Gemo INRIA group on building large-scale Web data management platforms based on DHTs. The talk will span over two peer-to-peer systems backed by DHTs: KadoP, a system we built for indexing and querying XML content, and VIP2P, a platform for managing corpora of inter-related XML and RDF data.

Invited speaker

Giorgio Ghelli (UniversitÓ di Pisa)


Almost linear inclusion of XML types


Checking inclusion of XML types is a crucial task for a typed compiler of an XML DBPL, to be invoked for every function call or variable assignment. Unfortunately, this task is PSPACE-hard, or worse, in general. We present here an approach to tame the complexity, down to a quadratic, and often linear, time. The approach is based on:
  • a restricted XML type system, corresponding to what is typically used by programmers
  • asymmetric subtyping, which limits the programmer but gives the compiler all the power it may need
  • representation of types as constraints that can be verified in quadratic time
  • a set of no-backtracking incomplete structural rules, which may often solve the problem in linear time.
As an added bonus, we learn properties of regular expressions with interleaving, and discover that automata are not always the best way to work with these things.