Subscribe Now Subscribe Today
Science Alert
Curve Top
Information Technology Journal
  Year: 2011 | Volume: 10 | Issue: 1 | Page No.: 201-206
DOI: 10.3923/itj.2011.201.206
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail

Efficient Algorithm for Overlap-Join

M.H. Saheb

This study introduces Overlap-Join which is non-equi self join that joins a table to itself with a non-equal condition for joining. Overlap-Join arises in real word queries that deal with time. Time scheduling and time tabling applications are clear examples for time overlapping, this in addition to its usage in temporal databases. JOIN is the most expensive operation in relational databases. For this reason an efficient algorithm is needed. Overlap-Join and two parameters for Overlapping; Overlap Coefficient (OC) and Span Coefficient (SC) have been defined. Three properties for overlapping has been developed and discussed. Two algorithms have been proposed. These algorithms are modified versions of two known join algorithms; the block nested-loop join and the Sort-merge join. Models for joining costs have been presented and analyzed. The modifications take advantage of the fact that overlap-Join is self-join and the sc concept. The study shows that performance of sort-merge join is not better than the performance of block nested loop join for Overlap-Join when the SC is high.
PDF Fulltext XML References Citation Report Citation
  •    A New Approach in Airport Capacity Enhancement Based on Integrated Runway Assignment and Operations Planning Model
How to cite this article:

M.H. Saheb , 2011. Efficient Algorithm for Overlap-Join. Information Technology Journal, 10: 201-206.

DOI: 10.3923/itj.2011.201.206






Curve Bottom