Queries and Constraints on Semi-Structured Data

Proc. of the 11th Int. Conf. on Advanced Information Systems Engineering (CAiSE 1999). Volume 1626 of Lecture Notes in Computer Science. 1999.

We extend the model for semi-structured data proposed in [?], where both databases and schemas are represented as graphs, with the possibility of expressing different types of constraints on the nodes of the graphs. We discuss how the expressive power of the constraint language may influence the complexity of checking subsumption between schemas, and devise a polynomial algorithm for an interesting class of constraints. We then set up a framework for defining queries which are used to select graphs from a database. The proposed query language allows for expressing sophisticated fixpoint properties of graphs and can be regarded as a basic building block of full-featured languages. We show that reasoning tasks at the basis of query optimization, such as query-schema comparison, query containment, and query satisfiability, are decidable.

@inproceedings{CAiSE-1999,
   title = "Queries and Constraints on Semi-Structured Data",
   year = "1999",
   author = "Diego Calvanese and De Giacomo, Giuseppe and Maurizio
Lenzerini",
   booktitle = "Proc. of the 11th Int. Conf. on Advanced Information Systems
Engineering (CAiSE 1999)",
   pages = "434--438",
   volume = "1626",
   publisher = "Springer",
   series = "Lecture Notes in Computer Science",
   doi = "10.1007/3-540-48738-7_34",
}