@techreport{oai:tsukuba.repo.nii.ac.jp:00030365,
author = {森嶋, 厚行 and 杉本, 重雄 and 北川, 博之 and Morishima, Atsuyuki and Yumiya, Erika and Takahashi, Masami and Sugimoto, Shigeo and Kitagawa, Hiroyuki},
month = {},
note = {Data integrity constraints are fundamental in various applications, such as data management,
integration, cleaning, and schema extraction. This paper presents the results of a first comprehensive
study on finding inclusion dependencies on the Web. The problem is important because
(1) applications of inclusion dependencies, such as data quality management, are beneficial in
the Web context, and (2) such dependencies are not explicitly given in general. In our approach,
we enumerate pairs of HTML/XML elements that possibly represent inclusion dependencies and
then rank the results for verification. First, we propose a bit-based signature scheme to efficiently
select candidates (element pairs) in the enumeration process. The signature scheme is unique
in that it supports Jaccard containment to deal with the incomplete nature of data on the Web,
and preserves the semiorder inclusion relationship among sets of words. Second, we propose a
ranking scheme to support a user in checking whether each enumerated pair actually suggests
inclusion dependencies. The ranking scheme sorts the enumerated pairs so that we can examine a
small number of pairs for simultaneously verifying many pairs. Finally, we prove that there exist
efficient algorithms for the ranking scheme. In addition to the theoretical results for the signature
and ranking schemes, we present a comprehensive set of experimental results using various real
Web sites. The results show that in the enumeration process the signature scheme reduces the
number of candidate pairs by orders of magnitude, and that the ranking scheme allows a small
number of higher ranked results to cover many other pairs.},
title = {Efficient Filtering and Ranking Schemes for Finding Inclusion Dependencies on the Web},
year = {2014}
}