Abstract
When data records are grouped into blocks in secondary storage, it is frequently necessary to estimate the number of blocks XD accessed for a given query. In a recent paper [1], Cardenas gave the expression XD = m(1 - (1 - 1/m)k), (1) assuming that there are n records divided into m blocks and that the k records satisfying the query are distributed uniformly among the m blocks. The derivation of the expression was left to the reader as an exercise.
- 1 Cardenas, A.F. Analysis and performance of inverted data base structures. Comm. ACM 18, 5 (May 1975), 253-263. Google ScholarDigital Library
- 2 Rothnie, J.B., and Lozano, T. Attribute based file organization in a paged memory environment. Comm. ACM 17, 2 (Feb. 1974), 63-69. Google ScholarDigital Library
- 3 Severance, D.G. Some generalized modeling structures for use in design of file organizations. Ph.D. Diss., U. of Michigan, Ann Arbor, Mich. 1972. Google ScholarDigital Library
- 4 Siler, K.F. A stochastic evaluation model for data base organizations in data retrieval systems. Comm. ACM 19, 2 (Feb. 1976), 84-95. Google ScholarDigital Library
- 5 Yao, S.B. Tree structures construction using key densities. Proc. ACM 1975 Nat. Conf., pp. 337-340. Google ScholarDigital Library
- 6 Yao, S.B. Evaluation and optimization of file organizations through analytic modeling. Ph.D~ Diss., U. of Michigan, Ann Arbor, Mich. 1974. Google ScholarDigital Library
- 7 Yao, S.B. An attribute based model for database access cost analysis. ACM Trans. Database Syst. 2, 1 (March 1977) 45-67. Google ScholarDigital Library
- 8 Yue, P.C., and Wong, C.K. Storage Cost Considerations in Secondary Index Selection. Int. J. Cptr. Inform. Sci. 4, 4 (1975), 307-327.Google Scholar
Recommendations
Query answering over ontologies specified via database dependencies
SIGMOD'14 PhD Symposium: Proceedings of the 2014 SIGMOD PhD symposiumIn this work we present a novel graph-based approach for studying the tractability of query answering over ontologies expressed by means of tuple-generating dependencies (TGDs). We do this by defining a new class of TGDs that subsumes all the other ...
Comments