Semi-Structured Data with Constraints and Incomplete Information

Diego Calvanese, Giuseppe De Giacomo, and Maurizio Lenzerini

Proc. of the 11th Int. Workshop on Description Logics (DL 1998). Volume 11 of CEUR Workshop Proceedings, 1998.

The problem of modeling semi-structured data is important in many application areas such as multimedia data management, biological databases, digital libraries, and data integration. In this paper, we base our work on BDFS [Bunemanetal.'97], which is a formal and elegant model for semi-structured data where schemas are graphs whose edges are labeled with formulae of a theory T. We extend BDFS with the possibility of expressing constraints and dealing with incomplete information. In particular, we consider different types of constraints, and discuss how the expressive power of the constraint language may influence the complexity of checking subsumption between schemas. We then set up a framework for defining BDFS schemas under the assumption that the theory T is not complete. Finally, we propose a new semi-structured data model, which extends BDFS with both constraints and incomplete theories. We present a technique for checking subsumption in a setting where both the constraints and the theory are expressed in a very powerful language.

   title = "Semi-Structured Data with Constraints and Incomplete
   year = "1998",
   author = "Diego Calvanese and De Giacomo, Giuseppe and Maurizio
   booktitle = "Proc. of the 11th Int. Workshop on Description Logics
(DL 1998)",
   pages = "11--20",
   volume = "11",
   series = "CEUR Workshop Proceedings,",
ps.gz pdf url