Optimization of Join-Type Queries in Nested Relational Databases
Summary :
Nested relational models were proposed as natural extensions of the relational model to support new emerging database applications. Prototype implementations of nested relational database systems (NRDBSs) have been done by some research groups. However, there remain many research issues on nested relations. One important issue is query processing, in particular query optimization. In NRDBSs, efficient execution of queries involving hierarchical data structures inherent in nested relations is required. In this paper, we focus on two join-type operations on nested relations: nested join and embed, and propose an algorithm to derive a cost optimal execution sequence of nested joins and embeds for a given query graph. The cost optimality of the derived sequence is formally proved. The complexity of the algorithm is proved to be O(N 2), when N nested relations are included in the query graph.
- Publication
- IEICE TRANSACTIONS on Information Vol.E77-D No.6 pp.648-659
- Publication Date
- 1994/06/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Databases
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yaxin LI, Hiroyuki KITAGAWA, Nobuo OHBO, "Optimization of Join-Type Queries in Nested Relational Databases" in IEICE TRANSACTIONS on Information,
vol. E77-D, no. 6, pp. 648-659, June 1994, doi: .
Abstract: Nested relational models were proposed as natural extensions of the relational model to support new emerging database applications. Prototype implementations of nested relational database systems (NRDBSs) have been done by some research groups. However, there remain many research issues on nested relations. One important issue is query processing, in particular query optimization. In NRDBSs, efficient execution of queries involving hierarchical data structures inherent in nested relations is required. In this paper, we focus on two join-type operations on nested relations: nested join and embed, and propose an algorithm to derive a cost optimal execution sequence of nested joins and embeds for a given query graph. The cost optimality of the derived sequence is formally proved. The complexity of the algorithm is proved to be O(N 2), when N nested relations are included in the query graph.
URL: https://global.ieice.org/en_transactions/information/10.1587/e77-d_6_648/_p
Copy
@ARTICLE{e77-d_6_648,
author={Yaxin LI, Hiroyuki KITAGAWA, Nobuo OHBO, },
journal={IEICE TRANSACTIONS on Information},
title={Optimization of Join-Type Queries in Nested Relational Databases},
year={1994},
volume={E77-D},
number={6},
pages={648-659},
abstract={Nested relational models were proposed as natural extensions of the relational model to support new emerging database applications. Prototype implementations of nested relational database systems (NRDBSs) have been done by some research groups. However, there remain many research issues on nested relations. One important issue is query processing, in particular query optimization. In NRDBSs, efficient execution of queries involving hierarchical data structures inherent in nested relations is required. In this paper, we focus on two join-type operations on nested relations: nested join and embed, and propose an algorithm to derive a cost optimal execution sequence of nested joins and embeds for a given query graph. The cost optimality of the derived sequence is formally proved. The complexity of the algorithm is proved to be O(N 2), when N nested relations are included in the query graph.},
keywords={},
doi={},
ISSN={},
month={June},}
Copy
TY - JOUR
TI - Optimization of Join-Type Queries in Nested Relational Databases
T2 - IEICE TRANSACTIONS on Information
SP - 648
EP - 659
AU - Yaxin LI
AU - Hiroyuki KITAGAWA
AU - Nobuo OHBO
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E77-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 1994
AB - Nested relational models were proposed as natural extensions of the relational model to support new emerging database applications. Prototype implementations of nested relational database systems (NRDBSs) have been done by some research groups. However, there remain many research issues on nested relations. One important issue is query processing, in particular query optimization. In NRDBSs, efficient execution of queries involving hierarchical data structures inherent in nested relations is required. In this paper, we focus on two join-type operations on nested relations: nested join and embed, and propose an algorithm to derive a cost optimal execution sequence of nested joins and embeds for a given query graph. The cost optimality of the derived sequence is formally proved. The complexity of the algorithm is proved to be O(N 2), when N nested relations are included in the query graph.
ER -
English
