Reducing Database Storage Space by Eliminating Duplicate Records

Abstract

Reducing the storage space of the relational database management system (DBMS) like Microsoft SQL (MS SQL), MySQL is very challenging nowadays. Using DBMS is vital to any local area network (LAN)-based application including Web-based application and mobile application to store and manage data. These data leave traces on servers and are retained on storage devices for a very long time. Due to heavy program usage and potential user error, the data eventually need to be examined for abnormalities and integrity. The chapter discusses the duplication detection algorithm approaches. In addition, the Levenshtein Algorithm was used and implemented to detect duplicate record in the database alongside the method used for matching records’ multiple fields and the Rule-Based Technique approaches. This topic will contribute knowledge on data cleansing and reducing storage space used by applications and help to maximize storage space of data center.

1. Introduction

Today’s data-intensive digital environment presents a significant challenge for data administrators. In order to provide its users with helpful services, Cloud Servers and Local Servers also receive information from various client transactions and store it periodically. In this context, maintaining repositories with “dirty” data—that is, replicas, nonstandardized representation that goes far beyond purely technical issues like data management system’s overall speed or performance; therefore, additional technical work, management, and even cultural shifts are required to address these issues [1].

Finding duplicated data that are kept in a database, collection of documents, or dataset is known as duplicate record detection. Nonetheless, there are two different approaches to detecting duplicates: Block-Level duplicate detection, which separates a file into chunks and saves a single copy of each chunk, and Duplicate File-Level detection, which saves only a copy of every file [2]. Additionally, there are two primary approaches to the architecture of the duplicate detection solution: the target-based approach, which targets the data storage device or service to handle duplicate detection while keeping the user uninformed of any identical detection that may arise throughout the development, and the source-based approach, which happens at the user side before it is moved to another source [3]. A number of scholars have previously tackled the challenges of eliminating redundant chunks of data before transmitting to the distant backup location. Source global and local chunk-level deduplication [4, 5, 6] are two common deduplication techniques.

Removing duplicate records by first detecting and locating them. One step in the integration and cleansing of data that is vital is locating roughly duplicate records in a database. There are numerous Web databases, particularly when the duplicate entry is identified using only a portion of the record’s fields. Using exact matching techniques, records that are exactly the same can be detected [7]. Also by using commonly used distinct function to find match data in the records that can be implemented to help find redundant data, resulting in data cleansing and that can reduce storage space of application [8].

2. Common algorithm approaches to find duplicate data in the list

This common approach has a vital role in finding duplicate record in the database that can help reduce the storage space used by many applications.

2.1 Sorting and comparing

Sorting is an important process that arranges things in a list in a predetermined order for several purposes. Scientists commonly utilize sorting to actually convey the results of numerical computations that include estimated accuracy levels. Sorting is a commonly used technique in string dispensation to find the lengthiest joint prefix in a set of strings and the lengthiest substring recurring in a specified string. Sorting algorithms are utilized in the literature and in the creation of work schedules, and they can be implemented in many different ways [9].

The method of this algorithm is sorting the list in a specified time complexity and then comparing the adjacent elements to find duplicates, and if a duplicate is found the algorithm can terminate early the execution, worst it traverses until the end of list or records.

There are many different sorting algorithms, and each of them has a different processing complexity. The different algorithms for sorting are listed in Table 1 along with their Average and Worst Case time complexity [10, 11, 12].

Sort Algorithm	Time Complexity
	Average	Worst Case
Selection	$O\left(n^2\right)$	$O\left(n^2\right)$
Insertion	$O\left(n^2\right)$	$O\left(n^2\right)$
Merge	$O\left(n\log n\right)$	$O\left(n\log n\right)$
Quick	$O\left(n\log n\right)$	$O\left(n^2\right)$
Bubblesort	$O\left(n^2\right)$	$O\left(n^2\right)$
Comparison	$O\left(n^2\right)$	$O\left(n^2\right)$

Table 1.

List of the sorting algorithm with time complexity.

2.2 Hashing

The hashing algorithm works by storing entries in a hash table as it traverses the list. For each element, it then determines whether it already exists in the hash table; if a duplicate is found, the program can cease searching. $O\left(n\right)$ is the typical case time complexity.

Applications including backup systems, Web caches, search engine databases, data stream management systems, and even cryptographic contexts use hashing to detect duplicate records in their streaming data [13]. Hashing algorithms are also used in cryptography and the most commonly used ones are listed in Table 2 with their usage description respectively [14].

Algorithm	Usage
MD5	The Message Digest algorithm is currently on its fifth iteration. Results from MD5 are 128 bits.
SHA-1	The standard Secure Hash Algorithm has two versions: SHA-0 is the first one to be developed. SHA-1 produces outputs with 160 bits. It is one of the primary algorithms that started to trade MD5, when the MD5 discovered vulnerabilities.
SHA-2	This algorithm is a set of hashing algorithms that contain SHA-224, SHA-256, SHA-384, and SHA-512.
NTLM	The NT LAN Manager algorithm is used for secret key hashing during authentication.
LANMAN	Microsoft LAN Manager hashing algorithm was used by legacy systems of Windows to store passwords.

Table 2.

List of the common hashing algorithms.

2.3 Bitwise manipulation

All of the data that the computer has altered, such as the words “yes” and “no,” can be represented by bits. Additionally, 0 and 1 can be used to portray a switch that can be turned on or off. It is also possible to characterize a piece as true or untrue, alive or dead, yes or no, etc. [15]. Additionally, you can indicate the existence of numbers using a bitwise manipulation technique if the range of numbers is restricted. This is particularly effective when working with narrow range integers.

2.4 Floyd’s tortoise and hare

Cycle detection is the algorithmic issue in computer science that involves identifying a cycle in iterated function values [16]. This algorithm can be adapted to find duplicates in an array or list in $O\left(n\right)$ time complexity. It’s particularly efficient when the list represents a permutation of numbers from 1 to n. Floyd’s cycle-finding method is often referred to as the tortoise and the hare algorithm [17]. The algorithm has a two-pointer approach that employs varying speeds, as it moves through the sequence [18].

2.5 Counting sort

A fundamental sorting method in computer science is the counting sort, which has an $O\left(N+K\right)$time complexity, where the number of elements is represented by N and the largest value among those N elements is represented by K. If any count exceeds 1, it means it has duplicate occurrence in the list [19].

2.6 Binary search trees

A basic and extensive data structure researched are binary search trees (BSTs). You can end the search if entering a number into the Binary Search Trees (BSTs) yields duplicate results. The maximum and expected number of comparisons made during a search are the two-complexity metrics that are typically connected with them [20].

3. Rule-based techniques

Using rules to determine whether two records are identical or not is one way to identify duplicate records in a database using distance-based approaches. When two records are either 0 or 1, rule-based procedures can be thought of as distance-based techniques [21]. Additionally, researchers suggested using a rule-based method to cluster records that link to the same real-world entity [22, 23].

Nevertheless, if you expand on this notion and create the theory equation that governs the domain logic equivalency, two people with identical names may be assumed to be the same individual [24]. The following are additional methods for identifying duplicate records that have numerous fields:

• Notation Techniques

• Probabilistic Matching Models

• Supervised and Semi-supervised Learning Approach

• Active-Learning-Based Techniques

• Distance-Based Techniques

• Unsupervised Learning

4. Levenshtein distance algorithm

A frequently occurring cause of discrepancies in the database input is the typographic representation of textual data. Because of this, string comparison algorithms are usually used in duplication detection to handle typographic variances. Levenshtein distance, also known as edit distance in the context of duplicate record identification, is one method used for matching fields with string data under character-based similarity metrics [21].

4.1 Goal

To use the Levenshtein Distance Algorithm for record duplication detection that can reduce database storage space by eliminating duplicate records in the databases.

4.2 Data preparation

The Products (Walmart and Amazon) and Bibliography (Database systems and Logic Programming (DBLP) and Google Scholar) [25] are collection of benchmark datasets for evaluating the algorithm. Each dataset is comprised of .csv files and a defined number of duplicate records. From this dataset, the data in the MS SQL Server Database were imported for usage and analysis in the experiments conducted.

To evaluate their algorithms and techniques for getting rid of redundant data in relational databases, a variety of studies were conducted [26, 27, 28, 29]. Product Dataset with the following fields (id, title, category, brand, model no, and price), which has a total record of 24,628 with a total of 1154 duplicate records. These are joint product information of Walmart and Amazon Company.

At the same time, Bibliography Dataset has total fields of five, namely ID, title, authors, venue, and year, and a complete record of 66,879 with an identified duplicate record of 5347. These data come from the combined list of Bibliographical researchers of Database systems and Logic Programming (DBLP) and Google Scholar information [25]. Table 3 is a list of the data that were used to assess how well the Levenshtein distance technique was implemented for identifying duplicate records in SQL databases.

Dataset	Size	Duplicates
Products	24,628	1154
Bibliography	66,879	5347

Table 3.

List of datasets used in the experiment for record duplication detection.

4.3 Implementation design flowchart

Figure 1 illustrates the process of detecting duplicate record in the database. As shown in the flowchart, the Product and Bibliography benchmark datasets were used to evaluate the data to detect duplicate record in the database using Levenshtein Distance Algorithm.

Figure 1.

Flowchart of the implementation design.

4.4 Levenshtein distance algorithm implementation

The Hypertext Preprocessor (PHP) scripting language is widely used and particularly suitable for website development. PHP was used to create and implement the record duplication detection in the database using the Levenshtein Distance Algorithm and the pseudocode below (Figure 2).

Figure 2.

The pseudocode for Levenshtein distance algorithm duplicate record detection.

where;

$strlen1 and $strlen2 get the length of the string

$max gets the highest number from $strlen1 and $strlen2

$lev1 variable gets the edit distance from the function lev using Levenshtein Distance Algorithm.

and the $percentage gets the percentage or the threshold similarity of the two string each row in the table.

5. Calculating database storage space

The method to calculate storage space followed the formula from the research paper of Ref. [30]. By determining the heap’s size, it is possible to compute the comparison of the storage space used in the database by the two suggested techniques.

The following Data Dictionary to compute the storage space is given in the Table 4:

No.	Variables	Description
1.	Num_Rows	The number of rows in a table
2.	Num_Cols	The total number of columns (fixed-length and variable-length) in a table
3.	Fixed_Data_Size	The sum byte size of all fixed-length columns
4.	Var_Data_Size	The data size variable-length
5.	Num_Var_Cols	The number of columns’ variable-length
6.	Max_Var_Size	The maximum total byte size of all columns’ variable-length
7.	Null_Bitmap	Manage column nullability reserved
8.	Row_Size	The total row size in a table
9.	Rows_Per_Page	The number of rows per page
10.	Num_Pages	The number of pages in each table
11.	Heap size	The volume of space that is required to save the data in the heap
12	Num_Duplicate	The total number of duplicate detected records

Table 4.

Data dictionary to calculate a relational database’s storage capacity.

Formula:

Num_Rows = Num_Rows - Num_Duplicate.

Null_Bitmap = 2 + ((Num_Cols +7) / 8).

Var_Data_Size = 2 + (Num_Var_Cols x 2) + Max_Var_Size.

Row_Size = Fixed_Data_Size + Var_Data_Size + Null_Bitmap +4.

Rows_Per_Page = 8096 / (Row_Size +2).

Num_Pages = Num_Rows / Rows_Per_Page.

Heap size (bytes) = 8192 x Num_Pages.

Table 5 lists the improvement of the database storage space between improved and unimproved dataset. The table shows the different test datasets used in the experiment. The Products Dataset has a size of 32.27 MB on disk based on the computation of storage space provided by Ref. [30], reduced a total of 8.45 MB on disk in the 75% threshold and the Bibliography Dataset reduced a total of 4.88 MB on disk in the 75% threshold.

Dataset	Improved	Unimproved	Reduced	Threshold	Percent
Products	23.82 MB	32.27 MB	8.45 MB	75%	26.18%
Bibliography	82.74 MB	87.62 MB	4.88 MB	75%	5.57%

Table 5.

An overview of the outcomes of reducing duplicate records in the database to increase storage space.

6. Conclusions

To cope with data duplication in relational databases, duplication detection usually uses a string comparison technique. With the following approaches and techniques discussed in this chapter, record duplicate detection using Levenshtein Distance Algorithm and other Rule-based approaches helped and contributed in reducing storage space by the database applications.

Acknowledgments

The researcher would like to extend his profound gratitude to Dr. Noel J. Petero, Vice President for Academic Affairs of the Tarlac Agricultural University for his insights and recommendations and for supporting the researcher in all his endeavors.

The researcher would like to express his sincerest appreciation to Dr. Arnold R. Lorenzo and Dr. Ruben A. Parazo of the Tarlac Agricultural University for their invaluable advice and sharing their expertise that led to realization of the research.

To the researcher’s colleagues for the words of encouragement and unwavering support, which in one way or another led to improving the work.

To the researcher’s better half Kathleen B. Valeriano and his sons Gino and Ethan, for the undying love, encouragement, financial and moral support which served as my driving force to finish this endeavor.

Above all, to the Holy and Triune God, for giving enough knowledge, strength, inspiration, love, guidance, and blessings.

Conflict of interest

The author declared no conflict of interest.