Analysis for the end of block wasted space. (English) Zbl 0711.68014
Summary: The problem examined in this report is the calculation of the average wasted space at the end of the block when variable length records are inserted in the file. Previous efforts are based in approximations. Here, a detailed analysis based on Markov chains gives the exact solution. A framework is presented which shows the relations between the previous approaches. The proposed model includes the previous models as special limiting cases. Simulation results close to the analytic results are also presented.
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68P20 | Information storage and retrieval of data |
References:
| [1] | S. Christodoulakis,Estimating block selectivities, Information Systems, Vol. 9, No. 1, 1984. · Zbl 0536.68082 |
| [2] | S. Christodoulakis,Implications of certain assumptions in database performance evaluation, ACM Transactions on Database Systems, Vol. 9, No. 2, pp. 163–187, 1984. · Zbl 0542.68081 · doi:10.1145/329.318578 |
| [3] | S. Christodoulakis, Y. Manolopoulos and P. Å. Larson,Analysis of overflow handling for variable length records, Information Systems, Vol. 14, No. 1, pp. 151–162, 1989. · doi:10.1016/0306-4379(89)90043-4 |
| [4] | D. R. Cox,Renewal Theory, Methuen, London, 1967. |
| [5] | C. J. Date,Introduction to Database Systems, John Wiley, Vol. 1, 4th edition, 1988. · Zbl 0477.68004 |
| [6] | J. Hakola and A. Heiskanen,On the distribution of wasted space at the end of file blocks, BIT, Vol. 20, No. 2, pp. 145–156, 1980. · Zbl 0428.68048 · doi:10.1007/BF01933187 |
| [7] | G. U. Hubbard,Computer-assisted Database Design, Van Nostrand Reinhold Company, 1981. |
| [8] | L. Kleinrock:Queueing Systems, Vol. I: Theory, John Wiley, NY, 1975. · Zbl 0334.60045 |
| [9] | Y. Manolopoulos and S. Christodoulakis,File organizations with shared overflow blocks for variable length objects, submitted. · Zbl 0780.68032 |
| [10] | Y. Manolopoulos and N. Fistas,Algorithms for a hash based file with variable length records, Information Sciences, to appear. · Zbl 0767.68038 |
| [11] | T. Sellis,Global query optimization, ACM Transactions on Database Systems, Vol. 13, No. 1, pp. 23–53, 1988. · doi:10.1145/42201.42203 |
| [12] | T. J. Teorey and J. P. Fry,Design of Database Structures, Prentice Hall, NJ, 1982. · Zbl 0566.68077 |
| [13] | G. Wiederhold,File Organization for Database Design, McGraw-Hill, NY, 1987. |
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.
