Querying and Updating Structured Files

Dr. Serge Abiteboul

on leave at Stanford University
email: abitebou@db.stanford.edu


Database systems are concerned with structured data. Unfortunately, data is still often available in an unstructured manner (e.g., in files) even when it does have a strong internal structure (e.g., data exchange formats such as SGML or ASN.1, electronic documents or programs). We are concerned with specifying logical views of such data and with querying and updating these views.

A logical view is specified using a context-free grammar (giving the syntax of the file) and some annotations in a "logical" language. This provides a semantics for queries. We show how queries can be evaluated without having to reconstruct entirely the view. This notably uses known query rewriting techniques adapted to our context.

When an update is specified on a logical view of a file, determining its effect on the file is an intricate issue. (Indeed, it is undecidable in general.) We consider restricted cases that allow (unexpensive) translation of updates. This is based on deriving correspondences between vertices in the parse tree of the file and the graph of the database.

This is based on joint work with Sophie Cluet and Tova Milo.

Copy of slides