Beyond Equi-joins: Ranking, Enumeration and Factorization

Area of Science:

• Database Systems
• Theoretical Computer Science
• Data Mining

Background:

• Theta-joins, especially with complex inequality predicates, pose significant computational challenges.
• Existing methods for ranked query processing are often limited to equi-joins or lack theoretical guarantees for more general join types.

Purpose of the Study:

• To develop an efficient algorithm for ranked enumeration of theta-joins with inequality predicates.
• To provide strong theoretical time and space complexity guarantees for this class of queries.
• To demonstrate the practical efficiency and memory usage of the proposed approach.

Main Methods:

• Developing a novel factorized representation of the query output.
• Designing an on-the-fly construction method for this representation.
• Analyzing the time and space complexity for acyclic full join queries with inequality conditions.

Main Results:

• Achieving $$ time complexity for returning the top-k ranked answers for acyclic full join queries with inequality conditions.
• Demonstrating guarantees that are polylogarithmic factors away from the best known complexities for equi-joins and even output-sensitive complexities.
• Extending guarantees to queries with selections and specific types of projections (free-connex, bag semantics).
• Showing practical performance improvements of orders of magnitude over state-of-the-art systems.

Conclusions:

• The proposed ranked enumeration approach offers the first non-trivial theoretical guarantees for theta-joins beyond equi-joins.
• The method is both theoretically sound and practically efficient, providing significant speedups and memory savings.