Complexity of extracting database schema from semistructured documents

摘要

Semistructured data comprises irregular structure and has no a-priori database schema, therefore we encounter several problems such as inefficient data retrieval and wasteful data storage. Some heuristic algorithms extracting database schema have been proposed, however, complexity of schema extraction problem has hardly discussed yet. In this paper, we consider an optimization problem to extract a database schema consisting of the least classes such that the density of each class is no less than a given threshold, where the density of a class represents the similarity between the type of the class and those of the objects in the class. We first prove that the corresponding decision problem is strongly NP-hard and belongs to ∑{sub}2P Then we show that for any r < 3/2, there is no polynomial-time r-approximation algorithm that solves the optimization problem unless P = NP.