半構造データからのスキーマ情報抽出アルゴリズムの開発

半结构化数据模式信息提取算法的开发

• 批准号: 12780317
• 负责人: 鈴木 伸崇
• 金额: $ 1.54万
• 依托单位: Okayama Prefectural University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2001
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-12780317/
• 关键词: 半構造データ; スキーマ抽出問題; アルゴリズム; NP困難性

本研究では,半構造データから「各クラスの密度が与えられた閾値以上,かつ,クラス数が最小である」という条件を満たすデータベーススキーマ(以下,スキーマ)を抽出する最適化問題について考察している.ここで,クラス密度とはクラスの型とそれに属する各オブジェクトの型の類似度を表す尺度であり,クラス密度が大きいほどその類似度が高いことを表す.本年度の主な研究実績は以下の通りである.1.スキーマ抽出問題の計算量申請者らは,これまでに上記最適化問題が強NP困難であることを示している.本年度は,同最適化問題に関して,「各抽出クラスの型が最適である(型を表す属性系列が最短である)」という条件を加えた場合の計算量について考察した.そして,この場合,同問題が強NP困難でありかつΔ_2Pに属することを示した.2.スキーマ抽出アルゴリズムの改良上記の結果から,厳密な最適解(スキーマ)を効率良く抽出することは困難である.そこで,昨年度,申請者らは根付クラス(rooted class)というクラスを提案し,それを用いてスキーマを効率良く抽出する多項式時間アルゴリズムを構成した.本年度は,この根付クラスをより一般的な構造をもつクラス(bounded class)に拡張することにより,よりサイズ(クラス数)の小さいスキーマが抽出できるようにアルゴリズムの改良を行った.具体的には,根付クラスは「そのクラスに属するどの基本クラスも,一つのクラス(そのクラスの根)の下位クラスである」という制限をもつが,今回拡張されたクラスではそのような根に相当するクラスを複数もつことが許されている.そのような拡張を行った場合でも,スキーマ抽出アルゴリズムが多項式時間で実行時間可能であることを示した.

In this study, the semi-structured structure "the density of each container and the threshold value of each container is above the threshold, and the minimum number of containers is the minimum" and the condition is満たすデータベーススキーマ(hereinafter,スキーマ)をdraw outるOptimization problem and investigation Similarity of はクラスのtype and とそれに genus するeach オブジェクトのtype The scale of the table is high, the density of the table is large, the similarity is highいことをTable. This year's main research results are listed below. 1. The calculation amount of the selected problem is listed in the applicant's らは, これまでにThe optimization problem is a strong NP-hard problem. This year's problem is the same as the optimization problem. "Each extraction type is the most suitable solution."る (type table す attribute series が shortest で あ る) 」 と い う condition を え た occasion の calculation amount に つ い て inspection し た. そ し て, こ の occasion, the same question Question がstrong NP difficultyでありかつΔ_2Pに belong to することをshow した.2.スキーマdraw out アルゴリズムの Improvement of the result of the above note から, 厳The best solution for secrets (スキーマ), good efficiency, and difficult extraction. Last year, the applicant was rooted. class)というクラスをProposalし,それを useいてスキーマをefficiently extract the polynomial timeアルゴリズムをstructure した. This year's は, このnettsuke クラスをよりgeneral なstructure をもつクラス(bounded class)に拡张することにより,よりサイズ(クラス number )の小さいスキーマが出できるようにアルゴリズムの Improvementを行った. Specific には, netsuke クラスは「そのクラスに belong to するどの Basic クラスも, 一つのクラス(そのクラスのroot)'s lower positionクラスである」という limit をもつが, this time 拡张されたクラスではそのようなroot quite するクラスをplural もつことが Xu されている.そのような拡张を行ったoccasionでも,スキーマdraw outアルゴリズムがpolynomial time で実行时间possible であることをshow した.

项目成果

Nobutaka Suzuki: "Complexity and a Method of Extracting a Database Schema over Semistructured Documents"IEICE Transactions on Information and Systems. (採録決定). (2002)

Nobutaka Suzuki：“半结构化文档的复杂性和提取数据库模式的方法”IEICE Transactions on Information and Systems（已接受）。

Nobutaka Suzuki: "On Extracting a Database Schema from Semistructured Documents"Proceedings of the 5th World Multi-Conference on Systemics, Cybernetics and Informatics (SCI2001). IXV. 220-225 (2001)

Nobutaka Suzuki：“论从半结构化文档中提取数据库模式”第五届系统学、控制论和信息学世界多方会议论文集（SCI2001）。

Nobutaka Suzuki: "Complexity of Extracting Database Schema from Semistructured Documents"Technical Report of IEICE (COMP). 100・705. 89-96 (2001)

Nobutaka Suzuki：“从半结构化文档中提取数据库模式的复杂性”IEICE 100・705 (2001) 的技术报告。

Nobutaka Suzuki: "On Extracting a Database Schema from Semistructured Documents(採録決定)"Proceedings of the 5th World Multi-Conference on Systemics, Cybernetics and Informatics. (2001)

Nobutaka Suzuki：“从半结构化文档中提取数据库模式（已接受）”第五届系统学、控制论和信息学世界多方会议论文集（2001 年）。