×
Malvestuto, Francesco Mario; Moscarini, Marina

A fast algorithm for query optimization in universal-relation databases. (English) Zbl 0913.68060

J. Comput. Syst. Sci. 56, No. 3, 299-309 (1998).
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.
Reviewer: R.Beedgen (Mannheim)

Cited in 7 Documents

MSC:

68P15 Database theory

Keywords:

canonical connection; query processing; universal-relation databases
PDFBibTeX XMLCite
\textit{F. M. Malvestuto} and \textit{M. Moscarini}, J. Comput. Syst. Sci. 56, No. 3, 299--309 (1998; Zbl 0913.68060)
Full Text: DOI

References:

[1] Aho, A. V.; Sagiv, Y.; Ullman, J. D., Efficient optimization of a class of relational expressions, ACM-TODS, 4, 435-454 (1979) · Zbl 0412.68041
[2] Aho, A. V.; Sagiv, Y.; Ullman, J. D., Equivalences among relational expressions, SIAM. J. Comput., 8, 218-246 (1979) · Zbl 0412.68041
[3] Ausiello, G.; D’Atri, A.; Moscarini, M., Chordality properties on graphs and minimal conceptual connections in semantic data models, J. Comput. System Sci., 33, 179-202 (1986) · Zbl 0625.68076
[4] Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M., On the desirability of acyclic database schemes, J. ACM, 3, 479-513 (1983) · Zbl 0624.68087
[5] Berge, C., Hypergraphs (1989), North-Holland: North-Holland Amsterdam · Zbl 0674.05001
[6] D’Atri, A.; Moscarini, M., Recognition algorithms and design methodology for acyclic database schemes, Advances in Computing Research (1986), JAI Press: JAI Press Greenwich
[7] D’Atri, A.; Moscarini, M., On hypergraph acyclicity and graph chordality, Inf. Process. Lett., 29, 271-274 (1988) · Zbl 0662.68111
[8] Fagin, R., Degrees of acyclicity for hypergraphs and relational database schemes, J. ACM, 3, 514-550 (1983) · Zbl 0624.68088
[9] Goodman, N.; Shmueli, O.; Tay, Y. C., GYO reductions, canonical connections, tree and cyclic schemas, and tree projections, J. Comput. System Sci., 29, 338-358 (1984) · Zbl 0552.68083
[10] Gyssens, M.; Jeavons, P. G.; Cohen, D. A., Decomposing constraint satisfaction problems using database techniques, Artif. Intell., 66, 57-89 (1994) · Zbl 0803.68090
[11] Maier, D.; Rozenshtein, D.; Warren, D. S., Window functions, (Kanellakis, P.; Preparata, F., Advances in Computing Research (1986), JAI Press: JAI Press Greenwich)
[12] Maier, D.; Ullman, J. D., Connections in acyclic hypergraphs, Theor. Comput. Sci., 32, 185-199 (1984) · Zbl 0557.05054
[14] Malvestuto, F. M., A universal table model for categorical databases, Inform. Sci., 49, 203-223 (1989) · Zbl 0706.68040
[15] Malvestuto, F. M.; Moscarini, M., Research Report (1994)
[16] Sagiv, Y.; Shmueli, O., Solving queries by tree projections, ACM-TODS, 18, 487-511 (1993)
[17] Tarjan, R. E.; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13, 566-591 (1984) · Zbl 0545.68062
[18] Ullman, J. D., Principles of Database and Knowledge-Base Systems. Principles of Database and Knowledge-Base Systems, The New Technologies, II (1989), Computer Science Press: Computer Science Press Rockville
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.