Similarity operators for detecting denial constraint violations

Abstract

Resumo: A detecção de violações a restrições de integridade (ICs) é uma tarefa importante na limpeza de dados. Existem vários tipos de ICs, cada um deles expressando um conjunto diferente de restrições. Um tipo bem estudado de IC são as restrições de negação (DCs), que podem expressar umgrande conjunto de restrições. Entretanto, DCs podem falhar em detectar violações quando na presença de dados textuais ruidosos, i.e., dados textuais contendo valores diferentes para representar a mesma entidade do mundo real. A existência de diferentes representações da mesma entidade pode ser causada, por exemplo, por erros de digitação, acrônimos, ou abreviações. Apesar da existência de vários sistemas para detectar violações de DCs, nenhum deles ataca o problema de detectar violações na presença de dados ruidosos. Além disso, outros tipos de ICs já foram propostos para lidar com dados ruidosos, mas nenhum deles pode expressar o mesmo conjunto de restrições representadas por DCs. Para atacar essas limitações das abordagens anteriores na detecção de violações a ICs, nós exploramos o uso de operadores de similaridade para detectar violações a DCs ao apresentar o Similarity FAst Constraint-based Error DeTector (SimFACET), um detector de violações a DCs com similaridade. Ele avalia eficientemente DCs contendo predicados com operadores de similaridade usando algoritmos exatos e aproximados para executar junções por similaridade. Para determinar a similaridade entre dados textuais, o detector suporta distância de edição entre dados textuais e distância de cossenos entre text embeddings. Nós também exploramos diferentes estratégias para o planejamento da order de processamento dos predicados de similaridade, tentando balancear custo de avaliação e a seletividade dos predicados para reduzir o tempo total de detecção. Para avaliar os algoritmos e estratégias propostos, nós conduzimos experimentos entre múltiplos datasets e utilizando DCs com diferentes características. Os resultados mostram que o SimFACET mantém alta acurácia enquanto consistentemente reduz o tempo de detecção, executando até 4× mais rápido do que versões de base

Abstract: The detection of integrity constraints (ICs) violations is an important task in data cleaning. There are many types of ICs, each of them capable of expressing different sets of constraints. A well-studied type of IC are denial constraints (DCs), which can express a large set of constraints. However, DCs can fail in detecting violations when in the presence of noise string data, i.e., string data containing different values to represent the same real-world entity. The existence of these different representations of the same entity may be caused, for example, by typos, acronyms, or abbreviations. Despite the existence of several systems to detect DC violations, none of them addresses the problem of detecting violations in the presence of noisy data. Furthermore, other IC types have already been proposed to deal with noisy data, but none of them can express the same set of constraints represented by DCs. To address these limitations of the previous approaches in the detection of IC violations, we explore the use of similarity operators for detecting DC violations by presenting Similarity FAst Constraint-based Error DeTector (SimFACET), a violations detector for similarity DCs. It efficiently evaluates DCs containing predicates with similarity operators using exact and approximate algorithms for performing similarity joins. To determine string similarity, the detector supports edit distance between strings and cosine distance between text embeddings. We also explore different strategies for planning the processing order of the similarity predicates, trying to balance the evaluation cost and the selectivity of predicates to reduce the overall detection time. To evaluate the proposed algorithms and strategies, we have conducted experiments across multiple datasets and using DCs with different characteristics. The results show that SimFACET maintains high accuracy while consistently reducing detection time, executing up to 4× faster than baselines