Problem of optimizing the number of block accesses in performing relational join is NP-hard

DOI10.1016/0020-0190(91)90070-XMaRDI QIDQ808230zbMATH OpenOpenAlexFDO

Authors Farshad Fotouhi, Sakti Pramanik

Publication date 1991

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(91)90070-x

zbMATH Keywords

database accessNP-complete problemsrelational join

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Database theory (68P15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Access Path Optimization in Relational Joins
• Worst-case optimal join algorithms
• On the complexity of join dependencies
• On the optimality of strategies for multiple join
• Optimising the distributed execution of join queries in polynomial time
• scientific article; zbMATH DE number 7566062
• Use of graph-theoretic models for optimal relational database accesses to perform join
• Constraint Databases

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Optimizing the cost of relational queries using partial-relation schemes
• Use of graph-theoretic models for optimal relational database accesses to perform join

Cited in

(4)

• Page access scheduling in join processing
• Access Path Optimization in Relational Joins
• Use of graph-theoretic models for optimal relational database accesses to perform join
• An upper bound on buffer size for join operation using nonclustered indexes

This page was built for publication: Problem of optimizing the number of block accesses in performing relational join is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q808230)