A fast algorithm for query optimization in universal-relation databases

DOI10.1006/JCSS.1998.1570MaRDI QIDQ1271615zbMATH OpenOpenAlexFDO

Authors Francesco M. Malvestuto, Marina Moscarini

Publication date 10 November 1998

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.1998.1570

zbMATH Keywords

canonical connectionquery processinguniversal-relation databases

Mathematics Subject Classification ID

Database theory (68P15)

Review text

The method of the canonical connection introduced by D. Maier and J. D. Ullman in 1984 provides an optimal procedure for query processing in universal-relation databases. The authors present an algorithm for computing canonical connections in a database scheme which is more efficient than the Classical algorithm based on tableau reduction. Moreover, with a slight modification of the algorithm the authors obtain a join plan which succeeds in controlling the nonmonotonicity of cyclic canonical connections.

Recommendations

• scientific article; zbMATH DE number 4201597
• scientific article; zbMATH DE number 11737
• On the foundations of the universal relation model
• An efficient algorithm for processing multi-relation queries in relational databases

Cites work

• A universal table model for categorical databases
• Chordality properties on graphs and minimal conceptual connections in semantic data models
• Connections in acyclic hypergraphs
• Decomposing constraint satisfaction problems using database techniques
• Degrees of acyclicity for hypergraphs and relational database schemes
• Equivalences among Relational Expressions
• GYO reductions, canonical connections, tree and cyclic schemas, and tree projections
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• On hypergraph acyclicity and graph chordality
• On the Desirability of Acyclic Database Schemes
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs

Cited in

(11)

• Canonical and monophonic convexities in hypergraphs
• Decomposition of a hypergraph by partial-edge separators
• An implementation of the iterative proportional fitting procedure by propagation trees.
• Decomposable convexities in graphs and hypergraphs
• On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
• scientific article; zbMATH DE number 2086289 (Why is no real title available?)
• scientific article; zbMATH DE number 5818908 (Why is no real title available?)
• scientific article; zbMATH DE number 4201597 (Why is no real title available?)
• scientific article; zbMATH DE number 3949759 (Why is no real title available?)
• scientific article; zbMATH DE number 4049160 (Why is no real title available?)
• Equivalence between hypergraph convexities

This page was built for publication: A fast algorithm for query optimization in universal-relation databases

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