Abstract
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 [Buneman et al.'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.