We develop a new notion of a schema for unstructured data.
Traditional schemas resemble the type systems of programming languages.
However for unstructured data, by which we mean data that is represented as an edge-labeled graph, the underlying type may be much less constrained and hence an alternative way of expressing constraints on the data is needed. Here, we propose that the schema is also a graph whose edges are labeled with predicates. We develop notions of conformance between a graph database and a graph schema and show that there is a natural and efficiently computable ordering on graph schemas. We then examine certain subclasses of schemas and show that schemas are in a certain sense closed under query applications. Finally, as part of future work, we indicate how they may be used in query decomposition and optimization.