A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Complexity and a Method of Extracting a Database Schema over Semistructured Documents Complexidade e um método de extração de um esquema de banco de dados em documentos semiestruturados

Nobutaka SUZUKI, Yoichirou SATO, Michiyoshi HAYASE

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Os dados semiestruturados compreendem uma estrutura irregular e não possuem esquema de banco de dados a priori, portanto, encontramos vários problemas, como recuperação ineficiente de dados e armazenamento de dados desnecessário. Para lidar com tais problemas, foram propostos alguns algoritmos de extração de esquemas sobre dados semiestruturados, nos quais os dados são modelados como um não ordenado árvore. No entanto, a ordem dos elementos é indispensável para os dados do documento, por isso consideramos extrair um esquema de banco de dados ideal em um banco de dados. ordenado árvore. Consideramos um problema de otimização para extrair o menor esquema de banco de dados tal que a densidade de cada classe não seja inferior a um determinado limite, onde a densidade de uma classe representa uma semelhança entre o tipo da classe e os dos objetos da classe. Primeiro provamos que o problema de decisão correspondente é fortemente NP-completo e mostramos que outra versão do problema é fortemente NP-difícil e pertence a Δ2 P. Então mostramos que para qualquer r <3/2, não há tempo polinomial r-algoritmo de aproximação que resolve o problema de otimização a menos que P = NP. Por fim, propomos uma espécie de classe chamada classe limitada que pode ser construído de forma eficiente e, em seguida, mostre um algoritmo de tempo polinomial para construir um esquema de banco de dados usando classes limitadas.

Publicação
IEICE TRANSACTIONS on Information Vol.E85-D No.6 pp.940-949
Data de publicação
2002/06/01
Publicitada
ISSN online
DOI
Tipo de Manuscrito
PAPER
Categoria
Bases de dados

autores

Palavra-chave