Quadratic Algorithms for Minimizing Joins in Restricted Relational Expressions | Zendy

Yehoshua Sagiv | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Quadratic Algorithms for Minimizing Joins in Restricted Relational Expressions

Author(s) -

Yehoshua Sagiv

Publication year - 1983

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/0212020

Subject(s) - joins , relational database , join (topology) , computer science , minification , relational algebra , equivalence (formal languages) , algorithm , quadratic equation , relational model , relational calculus , conjunctive query , mathematics , theoretical computer science , combinatorics , discrete mathematics , database , programming language , geometry

An important step in the optimization of queries in relational databases is minimizing the number of join operations in the evaluation of a query. It is shown that three subclasses of tableaux (including the subclass of simple tableaux) have $O(n^2 )$ time equivalence and minimization algorithms. Since tableaux are nonprocedural representations of relational expressions over select, project and join, these minimization algorithms can be used to minimize the number of join operators in expressions whose tableaux belong to one of these subclasses.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research