Abstract
The problem of modeling semi structured data is important in many application areas such as multimedia data management biolog ical databases digital libraries and data integration In this paper we base our work on bdfs 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 par ticular we consider di erent types of constraints and discuss how the expressive power of the constraint language may in uence the complexity of checking subsumption between schemas We then set up a framework for de ning 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