"Managing Schemata for Semistructured Databases using Constraints"

Andre Bergholz, Johann Christoph Freytag

Abstract:
Managing semistructured data requires more flexibility than
traditional database systems provide. Recently we proposed a query
language for semistructured data represented as labeled directed
graphs. This language is based on matching a partial schema into the
database. In this paper we describe how we achieve this matching using
constraints. We show how to match a schema into a database without
using any additional information. In order to match schemata more
efficiently, we are able to incorporate results of previously matched
schemata. To this end, we formulate a sufficient condition for schema
containment and describe how to test this condition, again, using
constraints. We show how the knowledge of schema containment can be
used for optimization. As a theoretical contribution we prove that,
under some circumstances, schema matches can be found without any
backtracking and in polynomial time.