On Extracting a Database Schema from Semistructured Documents

摘要

In semistructured data, the data structure is irregular and no explicit database schema is given, which causes several problems such as inefficient data retrieval and wasteful data storage. To cope with such problems, some algorithms extracting database schema from semistructured data have been proposed, in which data is modeled as an unordered tree. However, the order of elements is indispensable for document data, therefore we model data as an ordered tree and consider a problem of extracting an optimum database schema from semistructured data. We first show that the corresponding decision problem is strongly NP-complete. We next propose a polynomial-time algorithm for extracting a database schema.