M. Schkolnick
Abstract
In this paper, cost formulas are derived for the updates of data and indexes in a relational database. The costs depend on the data scan type and the predicates involved in the update statements. We show that update costs have a considerable influence, both in the context of the physical database design problem and in access path selection in query optimization for relational DBMSs.
- 1 ADABAS Reference Manual. Software AG, Sept. 1976.Google Scholar
- 2 ANDERSON, H. D., AND BERRA, P.B. Minimum cost selection of secondary indexes for formatted files. ACM Trans. Database Syst. 2, 1 (Mar. 1977), 68-90. Google ScholarDigital Library
- 3 ASTRAHAN, M. V., ET AL. System R, a relational approach to database management. ACM Trans. Database Syst. 1, 2 (June 1976), 97-137. Google ScholarDigital Library
- 4 ASTRAHAN, M.V., KIM, W., AND SCHKOLNICK, M. Evaluation of the System R access path selection mechanism. In Proceedings IFIP Conference (Tokyo, Melbourne, Oct. 1980), 487-491.Google Scholar
- 5 BLASOEN, M. W., AND ESWARAN K.P. Storage access in relational databases. IBM Syst. J 16, 4 (1977), 363-377.Google Scholar
- 6 BLEIER, R. T., AND VORHAUS, A.H. File organization in the SDC time-shared data management system (TDMS). In Proceedings IFIP Conference (Edinbourgh, Aug. 1968), 1245-1251.Google Scholar
- 7 BONFATTI, F., MAIO, D., AND TIBERIO, P. A separability-based method for secondary index selection in physical database design. In Methods and Tools for D.B. Design, S. Ceri, Ed., North- Holland, Amsterdam, 1983, 148-160.Google Scholar
- 8 CARDENAS, A.F. Analysis and performance of inverted database structures. Commun ACM 18, 5 (May 1975), 252-263. Google ScholarDigital Library
- 9 CHAMBERLIN, D. D., ET AL. SEQUEL2: A unified approach to data definition, manipulation, and control. IBM J. Res. Dev. 11, (Nov. 1976), 560-575.Google ScholarDigital Library
- 10 CHAMBERLIN, D. D., ET AL. A history and evaluation of System R. Commun. ACM 24, 10 (Oct. 1981), 632-646. Google ScholarDigital Library
- 11 CHRISTODOULAKIS, S. implication of certain assumptions in database performance evaluation. ACM Trans. Database Syst. 9, 2 (June 1984), 163-186. Google ScholarDigital Library
- 12 COMER, D. The uniquitous B-tree. ACM Comput. Surv. 11, 2 (June 1979), 397-434. Google ScholarDigital Library
- 13 Data Base 2. IBM Syst. J. 23, 2 (1984).Google ScholarDigital Library
- 14 FINKELSTEIN, S., SCHKOLNICK, M., AND TIBERIO, P. DBDSGN--a physical database design tool for System R. IEEE Database Eng. 5, 1 (1982).Google Scholar
- 15 HAMMER, M., AND CHAN, A. Index selection in a self-adaptive database management system. In Proceedings ACM SIGMOD Conference (Washington D.C., June 1976), 93-101. Google Scholar
- 16 KING, W.F. On the selection of indices for a file. IBM Rev. Rep. RJ1641, IBM Research Lab., San Jose, Calif., Jan. 1974.Google Scholar
- 17 KOLLIAS, J.G. A heuristic approach for determining the optimal degree of file inversion. Inf. Syst. 4 (1979), 307-318.Google ScholarCross Ref
- 18 MAIO, D., SCALAS, M. R., AND TIBERIO, P. On estimating access costs in relational databases. Inf. Proc. Lett. 19, 3 (1984), 157-161. Google ScholarDigital Library
- 19 PUTKONEN, A. On the selection of the access path in an inverted database organization. Inf. Syst. 4 (1979), 219-225.Google ScholarCross Ref
- 20 RDT: Relational design tool. IBM Ref. No. SH 20-6415, June 1984.Google Scholar
- 21 SCHKOLNICK, M. The optimal selection of secondary indices for files. Inf. Syst. I (1975), 141- 146.Google ScholarCross Ref
- 22 SCHKOLNICK, M., AND TmERIO, P. Considerations in developing a design tool for a relational DBMS. In Proceedings IEEE COMPSAC Conference (Chicago, Nov. 1979), 228-235.Google ScholarCross Ref
- 23 SELINGER, P. P., ET AL. Access path selection in a relational database system. In Proceedings A CM SIGMOD Conference (Boston, May 1979), 23-34. Google ScholarDigital Library
- 24 SQL/DS Application programming, IBM Rep. SH24-5018, May 1981.Google Scholar
- 25 STONEBRAKER, M. The choice of partial inversion and combined indices. Int. J. Comput. Inf. Sci. 3, 2 (June 1974), 167-188.Google ScholarCross Ref
- 26 WHANG, K. Y., WIEDERHOLD, G., AND SAGALOWlTZ, D. Separability--an approach to physical database design. In Proceedings Very Large Data Bases Conference (Cannes, Sept. 1981), 320- 332.Google Scholar
- 27 WHANG, K. Y., WIEDERHOLD, G., AND SAGALOWITZ, D. Estimating block accesses in database organizations--a closed noniterative formula. Commun ACM 26, 11 (Nov. 1983), 940-944. Google ScholarDigital Library
- 28 WIEDERHOLD, G. Data Base Design. McGraw-Hill, New York, 1983. Google ScholarDigital Library
- 29 YAO, S.B. Approximating block accesses in database organizations. Commun. ACM 20, 4 (Apr. 1977), 260-261. Google ScholarDigital Library
Index Terms
- Estimating the cost of updates in a relational database
Recommendations
A Method for Rough Relational Database Transformed into Relational Database
SSME '09: Proceedings of the 2009 IITA International Conference on Services Science, Management and EngineeringIt is decomposed the data of rough relational database and transformed into relational database according to the characteristic of rough relational database and relational database and in virtue of multiplication principle and Descartes of basic ...
Model Transformation From Object Relational Database to NoSQL Document Database
NISS '19: Proceedings of the 2nd International Conference on Networking, Information Systems & SecurityWith the high increase of data growing, NoSQL databases play a key role in storing large amount of data, to gain flexibility and scalability many industries are now replacing their relational and object relational databases by adopting NoSQL database ...
Reviews
Vasant B. Kaujalgi
This paper mainly deals with the tradeoff between the advantages offered by a given index in reducing the access cost against update cost. Based on the update cost, the optimal access path may be designed in the DBMS optimizer. The costs of updating (consisting of charging, deleting, and adding) are considered, along with costs of alternate access paths. The authors refer to charging as also being an updating operation. The costs are determined based on pages read and rewritten. No costs are associated with virtual memory techniques or utilization of CPU. The basic updating operations are Update, Delete, and Insert. Both Update and Delete require scanning. In this paper, costs associated with ordered scan and unordered scan have been considered. For Insert operation, there is no cost of searching but only the cost of writing in an appropriate page. Index update costs are considered under two cases. The first case is concerned with the modification of index in unsorted indices like secondary indices. Such condition may also arise when the primary index is modified, which forces changes in secondary indices. The other case is concerned with the modification to indices which are ordered, as in the case of primary indices or secondary indices which are used for scanning. Costs concerned with Update, Delete, and Insert are calculated for both the cases. The paper ends with a few examples to show the costs of various operations and possible application in a database software development. Consideration of cost for alternate accesses may lead to reduction in the access time for any updating instructions in a query language, and physical design of a database. This paper tries to quantify the costs of updating. Such considerations may be useful in the development of complex DBMS software. Hence, this paper may be of interest to professionals involved in development of such software, even though authors assume a System R type Relational DBMS in the paper.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments