Modeling and Querying Semi-Structured Data

Networking and Information Systems. 2(2):253--273 1999.

We extend the model for semi-structured data proposed in BDFS97, 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.

@article{NISJ-1999-ssd,
   title = "Modeling and Querying Semi-Structured Data",
   year = "1999",
   author = "Diego Calvanese and De Giacomo, Giuseppe and Maurizio
Lenzerini",
   journal = "Networking and Information Systems",
   pages = "253--273",
   number = "2",
   volume = "2",
}