The similarity-aware relational database set operators. (July 2016)

• Record Type: Journal Article
• Authors: Al Marri, Wadha J.; Malluhi, Qutaibah; Ouzzani, Mourad; Tang, Mingjie; Aref, Walid G.
• Is Part Of: Information systems. Volume 59(2016)
• Page Start: 79
• Page End: 93
• Publication Date: 2016-07
• Subjects: Similarity query processing -- Relational databases -- Set operators; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2015.10.008
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: Identifying similarities in large datasets is an essential operation in several applications such as bioinformatics, pattern recognition, and data integration. To make a relational database management system similarity-aware, the core relational operators have to be extended. While similarity-awareness has been introduced in database engines for relational operators such as joins and group-by, little has been achieved for relational set operators, namely Intersection, Difference, and Union . In this paper, we propose to extend the semantics of relational set operators to take into account the similarity of values. We develop efficient query processing algorithms for evaluating them, and implement these operators inside an open-source database system, namely PostgreSQL. By extending several queries from the TPC-H benchmark to include predicates that involve similarity-based set operators, we perform extensive experiments that demonstrate up to three orders of magnitude speedup in performance over equivalent queries that only employ regular operators.