Extracting Typical Classes and a Database Schema from Semistructured Data

概要

論文の詳細を見る
Semistructured data has no a-priori schema information, which causes some problems such as inefficient storage and query execution. To sope with such problems, extracting schema information from semistructured data has been an important issue. However in most cases optimal schema information cannot be extracted efficiently, and few efficient approximation algorithms have been proposed. In this paper, we consider an approximation algorithm for extracting "typical" classes from semistructured data, Intuitively, a class C is said to be typical if the structure of C is "similar" to those of "many" objects. We present the following results. First, we prove that the problem of deciding if a typical class can be extracted from given semistructured data is NP-complete. Second, we present an approximation algorithm for extracting typical classes from given semistrucured data, and show a suffucient condition for the approximation algorithm to run in polynomial time. Finally, by using extracted classes obtained by the approximation algorithm, we propose a polynomial-time algorithm for constructing a set R of classes such that R covers all the objects to from a database schema.
社団法人電子情報通信学会の論文
2001-01-01