Duplicate Elimination

Description

SQL does not eliminate duplicates implicitly. It allows to enter duplicate values on columns other than candidate key or if did not specified any keys. If the user wants to eliminate duplicate records, he has to use DISTINCT keyword in the query.

Databases, therefore, can have duplicate entries. The problem deals with identifying and removing duplicates from a database.

Parameters

$n$: number of records

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Sorting based (Merge Sort)	1964	$O(n \log n)$	$O(n)$	Exact	Deterministic
Sorting based (Merge Sort) + real-time elimination	1964	$O(n \log n)$		Exact	Deterministic
BST Algorithm	1999	$O(n \log n)$	$O(\log n)$	Exact	Deterministic
Priority Queue Algorithm	1976	$O(n^{2})$	$O(n)$	Exact	Deterministic
Sorted Neighborhood Algorithm (SNA)	1998	$O(n^{2})$	$O(n)$	Exact	Deterministic	Time
Duplicate Elimination Sorted Neighborhood Algorithm (DE-SNA)	2002	$O(n \log n)$		Exact	Deterministic
Adaptive Duplicate Detection Algorithm (ADD)	2003	$O(n^{3})$	$O({1})$	Exact	Deterministic	Time

Time Complexity Graph