Semistructured Data Schemas with Expressive Constraints

Proc. of the 7th Int. Workshop on Knowledge Representation meets Databases (KRDB 2000). Volume 29 of CEUR Workshop Proceedings, https://ceur-ws.org/. 2000.

Recently, there have been several proposals of formalisms for modeling semistructured data, which is data that is neither raw, nor strictly typed as in conventional database systems. Semistructured data models are graph-based models, where graphs are used to represent both databases and schemas. We study the basic problem of schema subsumption, which amounts to check whether all databases conforming to a schema also conform to another schema, in the presence of constraints, which are used to enforce additional conditions on databases. In particular, we study the relationship between various constraint languages and the basic property of locality, which allows one to check subsumption between schemas in polynomial time in the number of nodes of the schemas. We show that locality holds when both numeric constraints and disjunction are added to a simple constraint language. On the other hand, locality is lost when we consider constraints both on outgoing and incoming edges of databases.

@inproceedings{KRDB-2000-ssd,
   title = "Semistructured Data Schemas with Expressive Constraints",
   year = "2000",
  author = "Andrea Calì and Diego Calvanese and Maurizio Lenzerini",
   booktitle = "Proc. of the 7th Int. Workshop on Knowledge Representation
meets Databases (KRDB 2000)",
   pages = "3--16",
   volume = "29",
   publisher = "CEUR-WS.org",
   series = "CEUR Workshop Proceedings, https://ceur-ws.org/",
}