Studies on Inferring Type Dependencies for Semi-structured Data

半结构化数据推断类型依赖性的研究

• 批准号: 11680416
• 负责人: ITO Minora
• 金额: $ 1.86万
• 依托单位: NARA INSTITUTE OF SCIENCE AND TECHNOLOGY
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1999
• 资助国家: 日本
• 起止时间: 1999 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-11680416/
• 关键词: Semi-structured Data; Object-Oriented Database; Type Dependency; Inference Problem; Path Expression

1. In usual databases, it is assumed that the stored data must be in a fixed format for the underlying database schema that is designed in advance. In semi-structured data, on the other hand, the data (that would have a common concept) may not have the same structure, so that it is difficult to design a fixed database schema in advance. In this project, we focus on types of properties, introduce a constraint that can expresses a type information including ambiguity of semi-structured data, and aim to solve a number of basic problems on such a constraint.2. We extend the constraint called SC (specialization constraint) that express a type of a property so as to be able to express a constraint which a semi-structured data should satisfy. By the extension, an SC may have a set of path expressions.3. For the inference problem on SCs (which decides if an SC σ is a logical consequence of a set of SCs Σ), we obtain a set of inference rules that is sound and complete.4. We obtain a sufficient condition such that the inference problem is partially decidable. Similarly, for the co-problem (that is, negation) of the inference problem, we obtain a sufficient condition such that the co-problem is partially decidable.5. By the result above, if the set of path expressions in an SC is context-free, then the inference problem is undecidable. If the set of path expressions in an SC is regular, then the inference problem is decidable.6. As for the navigation problem of a path expression (which decides if there is a database that contains a path which we can navigate along the given path expression), we obtain a similar result as above.

1。在通常的数据库中，假定存储的数据必须是固定格式的基础数据库模式，该数据库i结构数据（在以太之手上）结构，以便提前设计固定的数据库架构。称为SC Perth SO Express一个约束，半结构化数据可满足扩展的满足，SC可能具有一组表达式。3对于SCS SCSσ的推理问题）。这是完整的关于SC中的不含上下文的路径表达式是常规的，我们的推理问题是可确定的。6。

项目成果

松山哲平: "データマイニングにおける相関規則を求める問題に関する研究"電子情報通信学会技術研究報告. COMP2000-83. 81-87 (2001)

Teppei Matsuyama：“数据挖掘中寻找关联规则问题的研究”IEICE COMP2000-83（2001）。

Kotaro Nonaka: "An Incremental Algorithm to Search for Meaningful Association Rules from Large Hemsets"Tech.Rep.of IEICE. COMP99-32. 7-14 (1999)

Kotaro Nonaka：“一种从大型 Hemsets 中搜索有意义的关联规则的增量算法”IEICE 的 Tech.Rep.。

Yoshihiro Murata: "An Approximation Algorithm for the Task-Coalition Assignment Problem"Tech.Rep.of IEICE. COMP99-59. 25-32 (1999)

Yoshihiro Murata：“任务联盟分配问题的近似算法”Tech.Rep.of IEICE。

横内淳史: "無閉路オブジェクト指向データベースにおける型検査問題の計算量"電子情報通信学会技術研究報告. COMP99-16. 1-8 (1999)

Atsushi Yokouchi：“非循环面向对象数据库中类型检查问题的计算复杂性”IEICE COMP99-16 (1999)。

横内淳史: "無閉路オブジェクト指向データベーススキーマにおける型検査問題の計算量"電子情報通信学会技術研究報告. COMP99-16. 1-8 (1999)

Atsushi Yokouchi：“非循环面向对象数据库模式中的类型检查问题的计算量”IEICE 技术报告 1-8 (1999)。