Document (#6726)

Author

Omiecienski, E.

Title

¬An analytical comparison of two secondary indexing schemes : physical versus logical addresses

Source

Information systems. 18(1993) no.5, S.319-328

Year

1993

Abstract

The use of indexes improves the performance of queries but degrades the performance of updates, inserts and deletes. Focuses on reducing the cost of index maintenance when tuples are inserted or deleted. Presents a scheme where secondary indexes contain logical as opposed to physical pointers. Develops an analytical model for the total cost of processing queries, updates, inserts and deletes, for this scheme, and compares it with the cost of the typical secondary indexing scheme that uses physical pointers. Finds that by modifying the parameters that reduce the query cost, such as reducing the probability of occurrence of a query or reducing the average selectivity of a secondary key that the local pointer scheme can achieve a better performance than the physical pointer scheme. However, selecting one scheme over the other is highly dependent on a number of parameters that are germane to the particular database application environment

Similar documents (content)

1. Gillenson, M.L.; Frost, R.D.; Kilpatrick, M.G.: Database pointers in navigational and object-oriented database management systems : a comparison (1995) 0.15

   0.14938422 = sum of:
     0.14938422 = product of:
       0.74692106 = sum of:
         0.02533027 = weight(abstract_txt:query in 3838) [ClassicSimilarity], result of:
           0.02533027 = score(doc=3838,freq=1.0), product of:
             0.085242406 = queryWeight, product of:
               1.3818815 = boost
               4.754492 = idf(docFreq=1039, maxDocs=44421)
               0.012974206 = queryNorm
             0.29715574 = fieldWeight in 3838, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.754492 = idf(docFreq=1039, maxDocs=44421)
               0.0625 = fieldNorm(doc=3838)
         0.10940917 = weight(abstract_txt:tuples in 3838) [ClassicSimilarity], result of:
           0.10940917 = score(doc=3838,freq=1.0), product of:
             0.17944098 = queryWeight, product of:
               1.4177145 = boost
               9.755557 = idf(docFreq=6, maxDocs=44421)
               0.012974206 = queryNorm
             0.6097223 = fieldWeight in 3838, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               9.755557 = idf(docFreq=6, maxDocs=44421)
               0.0625 = fieldNorm(doc=3838)
         0.013498509 = weight(abstract_txt:that in 3838) [ClassicSimilarity], result of:
           0.013498509 = score(doc=3838,freq=3.0), product of:
             0.05272614 = queryWeight, product of:
               1.7184066 = boost
               2.3649352 = idf(docFreq=11344, maxDocs=44421)
               0.012974206 = queryNorm
             0.25601172 = fieldWeight in 3838, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               2.3649352 = idf(docFreq=11344, maxDocs=44421)
               0.0625 = fieldNorm(doc=3838)
         0.13997114 = weight(abstract_txt:pointers in 3838) [ClassicSimilarity], result of:
           0.13997114 = score(doc=3838,freq=1.0), product of:
             0.2664331 = queryWeight, product of:
               2.4430764 = boost
               8.405631 = idf(docFreq=26, maxDocs=44421)
               0.012974206 = queryNorm
             0.52535194 = fieldWeight in 3838, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               8.405631 = idf(docFreq=26, maxDocs=44421)
               0.0625 = fieldNorm(doc=3838)
         0.45871195 = weight(abstract_txt:pointer in 3838) [ClassicSimilarity], result of:
           0.45871195 = score(doc=3838,freq=4.0), product of:
             0.3703132 = queryWeight, product of:
               2.8802326 = boost
               9.909708 = idf(docFreq=5, maxDocs=44421)
               0.012974206 = queryNorm
             1.2387135 = fieldWeight in 3838, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               9.909708 = idf(docFreq=5, maxDocs=44421)
               0.0625 = fieldNorm(doc=3838)
       0.2 = coord(5/25)
   

2. Chan, H.C.; Wei, K.K.; Siau, K.L.: ¬An empirical study on end-users' update performance for different abstraction levels (1994) 0.13

   0.13148244 = sum of:
     0.13148244 = product of:
       0.6574122 = sum of:
         0.053733617 = weight(abstract_txt:query in 1830) [ClassicSimilarity], result of:
           0.053733617 = score(doc=1830,freq=2.0), product of:
             0.085242406 = queryWeight, product of:
               1.3818815 = boost
               4.754492 = idf(docFreq=1039, maxDocs=44421)
               0.012974206 = queryNorm
             0.6303625 = fieldWeight in 1830, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.754492 = idf(docFreq=1039, maxDocs=44421)
               0.09375 = fieldNorm(doc=1830)
         0.08280087 = weight(abstract_txt:logical in 1830) [ClassicSimilarity], result of:
           0.08280087 = score(doc=1830,freq=1.0), product of:
             0.14328198 = queryWeight, product of:
               1.7915905 = boost
               6.1641335 = idf(docFreq=253, maxDocs=44421)
               0.012974206 = queryNorm
             0.57788754 = fieldWeight in 1830, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.1641335 = idf(docFreq=253, maxDocs=44421)
               0.09375 = fieldNorm(doc=1830)
         0.09055838 = weight(abstract_txt:performance in 1830) [ClassicSimilarity], result of:
           0.09055838 = score(doc=1830,freq=3.0), product of:
             0.1207195 = queryWeight, product of:
               2.0140827 = boost
               4.619759 = idf(docFreq=1189, maxDocs=44421)
               0.012974206 = queryNorm
             0.7501554 = fieldWeight in 1830, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               4.619759 = idf(docFreq=1189, maxDocs=44421)
               0.09375 = fieldNorm(doc=1830)
         0.21191807 = weight(abstract_txt:updates in 1830) [ClassicSimilarity], result of:
           0.21191807 = score(doc=1830,freq=2.0), product of:
             0.21278302 = queryWeight, product of:
               2.18329 = boost
               7.5118127 = idf(docFreq=65, maxDocs=44421)
               0.012974206 = queryNorm
             0.9959351 = fieldWeight in 1830, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               7.5118127 = idf(docFreq=65, maxDocs=44421)
               0.09375 = fieldNorm(doc=1830)
         0.21840128 = weight(abstract_txt:secondary in 1830) [ClassicSimilarity], result of:
           0.21840128 = score(doc=1830,freq=1.0), product of:
             0.3446263 = queryWeight, product of:
               3.9294536 = boost
               6.759825 = idf(docFreq=139, maxDocs=44421)
               0.012974206 = queryNorm
             0.63373363 = fieldWeight in 1830, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.759825 = idf(docFreq=139, maxDocs=44421)
               0.09375 = fieldNorm(doc=1830)
       0.2 = coord(5/25)
   

3. Heinz, S.; Zobel, J.: Efficient single-pass index construction for text databases (2003) 0.09

   0.08656899 = sum of:
     0.08656899 = product of:
       0.43284494 = sum of:
         0.055579003 = weight(abstract_txt:indexes in 2678) [ClassicSimilarity], result of:
           0.055579003 = score(doc=2678,freq=1.0), product of:
             0.12404035 = queryWeight, product of:
               1.6669571 = boost
               5.735321 = idf(docFreq=389, maxDocs=44421)
               0.012974206 = queryNorm
             0.44807196 = fieldWeight in 2678, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.735321 = idf(docFreq=389, maxDocs=44421)
               0.078125 = fieldNorm(doc=2678)
         0.01377686 = weight(abstract_txt:that in 2678) [ClassicSimilarity], result of:
           0.01377686 = score(doc=2678,freq=2.0), product of:
             0.05272614 = queryWeight, product of:
               1.7184066 = boost
               2.3649352 = idf(docFreq=11344, maxDocs=44421)
               0.012974206 = queryNorm
             0.2612909 = fieldWeight in 2678, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.3649352 = idf(docFreq=11344, maxDocs=44421)
               0.078125 = fieldNorm(doc=2678)
         0.043569922 = weight(abstract_txt:performance in 2678) [ClassicSimilarity], result of:
           0.043569922 = score(doc=2678,freq=1.0), product of:
             0.1207195 = queryWeight, product of:
               2.0140827 = boost
               4.619759 = idf(docFreq=1189, maxDocs=44421)
               0.012974206 = queryNorm
             0.36091867 = fieldWeight in 2678, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.619759 = idf(docFreq=1189, maxDocs=44421)
               0.078125 = fieldNorm(doc=2678)
         0.1620822 = weight(abstract_txt:reducing in 2678) [ClassicSimilarity], result of:
           0.1620822 = score(doc=2678,freq=1.0), product of:
             0.28982985 = queryWeight, product of:
               3.1207583 = boost
               7.1581726 = idf(docFreq=93, maxDocs=44421)
               0.012974206 = queryNorm
             0.55923223 = fieldWeight in 2678, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.1581726 = idf(docFreq=93, maxDocs=44421)
               0.078125 = fieldNorm(doc=2678)
         0.15783696 = weight(abstract_txt:cost in 2678) [ClassicSimilarity], result of:
           0.15783696 = score(doc=2678,freq=2.0), product of:
             0.24874917 = queryWeight, product of:
               3.338403 = boost
               5.743043 = idf(docFreq=386, maxDocs=44421)
               0.012974206 = queryNorm
             0.63452256 = fieldWeight in 2678, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               5.743043 = idf(docFreq=386, maxDocs=44421)
               0.078125 = fieldNorm(doc=2678)
       0.2 = coord(5/25)
   

4. Ren, P.; Chen, Z.; Ma, J.; Zhang, Z.; Si, L.; Wang, S.: Detecting temporal patterns of user queries (2017) 0.09

   0.085050985 = sum of:
     0.085050985 = product of:
       0.4252549 = sum of:
         0.05484165 = weight(abstract_txt:query in 4315) [ClassicSimilarity], result of:
           0.05484165 = score(doc=4315,freq=3.0), product of:
             0.085242406 = queryWeight, product of:
               1.3818815 = boost
               4.754492 = idf(docFreq=1039, maxDocs=44421)
               0.012974206 = queryNorm
             0.6433611 = fieldWeight in 4315, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               4.754492 = idf(docFreq=1039, maxDocs=44421)
               0.078125 = fieldNorm(doc=4315)
         0.11063716 = weight(abstract_txt:queries in 4315) [ClassicSimilarity], result of:
           0.11063716 = score(doc=4315,freq=8.0), product of:
             0.098143116 = queryWeight, product of:
               1.4827669 = boost
               5.1015973 = idf(docFreq=734, maxDocs=44421)
               0.012974206 = queryNorm
             1.1273043 = fieldWeight in 4315, product of:
               2.828427 = tf(freq=8.0), with freq of:
                 8.0 = termFreq=8.0
               5.1015973 = idf(docFreq=734, maxDocs=44421)
               0.078125 = fieldNorm(doc=4315)
         0.0097417105 = weight(abstract_txt:that in 4315) [ClassicSimilarity], result of:
           0.0097417105 = score(doc=4315,freq=1.0), product of:
             0.05272614 = queryWeight, product of:
               1.7184066 = boost
               2.3649352 = idf(docFreq=11344, maxDocs=44421)
               0.012974206 = queryNorm
             0.18476056 = fieldWeight in 4315, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.3649352 = idf(docFreq=11344, maxDocs=44421)
               0.078125 = fieldNorm(doc=4315)
         0.043569922 = weight(abstract_txt:performance in 4315) [ClassicSimilarity], result of:
           0.043569922 = score(doc=4315,freq=1.0), product of:
             0.1207195 = queryWeight, product of:
               2.0140827 = boost
               4.619759 = idf(docFreq=1189, maxDocs=44421)
               0.012974206 = queryNorm
             0.36091867 = fieldWeight in 4315, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.619759 = idf(docFreq=1189, maxDocs=44421)
               0.078125 = fieldNorm(doc=4315)
         0.20646447 = weight(abstract_txt:scheme in 4315) [ClassicSimilarity], result of:
           0.20646447 = score(doc=4315,freq=2.0), product of:
             0.3405779 = queryWeight, product of:
               4.7842274 = boost
               5.4868593 = idf(docFreq=499, maxDocs=44421)
               0.012974206 = queryNorm
             0.60621804 = fieldWeight in 4315, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               5.4868593 = idf(docFreq=499, maxDocs=44421)
               0.078125 = fieldNorm(doc=4315)
       0.2 = coord(5/25)
   

5. Cheng, C.-S.; Chung, C.-P.; Shann, J.J.-J.: Fast query evaluation through document identifier assignment for inverted file-based information retrieval systems (2006) 0.08

   0.08215953 = sum of:
     0.08215953 = product of:
       0.34233138 = sum of:
         0.038396128 = weight(abstract_txt:probability in 1979) [ClassicSimilarity], result of:
           0.038396128 = score(doc=1979,freq=1.0), product of:
             0.08927793 = queryWeight, product of:
               6.881186 = idf(docFreq=123, maxDocs=44421)
               0.012974206 = queryNorm
             0.43007413 = fieldWeight in 1979, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.881186 = idf(docFreq=123, maxDocs=44421)
               0.0625 = fieldNorm(doc=1979)
         0.06701759 = weight(abstract_txt:query in 1979) [ClassicSimilarity], result of:
           0.06701759 = score(doc=1979,freq=7.0), product of:
             0.085242406 = queryWeight, product of:
               1.3818815 = boost
               4.754492 = idf(docFreq=1039, maxDocs=44421)
               0.012974206 = queryNorm
             0.78620017 = fieldWeight in 1979, product of:
               2.6457512 = tf(freq=7.0), with freq of:
                 7.0 = termFreq=7.0
               4.754492 = idf(docFreq=1039, maxDocs=44421)
               0.0625 = fieldNorm(doc=1979)
         0.031292915 = weight(abstract_txt:queries in 1979) [ClassicSimilarity], result of:
           0.031292915 = score(doc=1979,freq=1.0), product of:
             0.098143116 = queryWeight, product of:
               1.4827669 = boost
               5.1015973 = idf(docFreq=734, maxDocs=44421)
               0.012974206 = queryNorm
             0.31884983 = fieldWeight in 1979, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.1015973 = idf(docFreq=734, maxDocs=44421)
               0.0625 = fieldNorm(doc=1979)
         0.015586738 = weight(abstract_txt:that in 1979) [ClassicSimilarity], result of:
           0.015586738 = score(doc=1979,freq=4.0), product of:
             0.05272614 = queryWeight, product of:
               1.7184066 = boost
               2.3649352 = idf(docFreq=11344, maxDocs=44421)
               0.012974206 = queryNorm
             0.2956169 = fieldWeight in 1979, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               2.3649352 = idf(docFreq=11344, maxDocs=44421)
               0.0625 = fieldNorm(doc=1979)
         0.060372256 = weight(abstract_txt:performance in 1979) [ClassicSimilarity], result of:
           0.060372256 = score(doc=1979,freq=3.0), product of:
             0.1207195 = queryWeight, product of:
               2.0140827 = boost
               4.619759 = idf(docFreq=1189, maxDocs=44421)
               0.012974206 = queryNorm
             0.5001036 = fieldWeight in 1979, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               4.619759 = idf(docFreq=1189, maxDocs=44421)
               0.0625 = fieldNorm(doc=1979)
         0.12966576 = weight(abstract_txt:reducing in 1979) [ClassicSimilarity], result of:
           0.12966576 = score(doc=1979,freq=1.0), product of:
             0.28982985 = queryWeight, product of:
               3.1207583 = boost
               7.1581726 = idf(docFreq=93, maxDocs=44421)
               0.012974206 = queryNorm
             0.4473858 = fieldWeight in 1979, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.1581726 = idf(docFreq=93, maxDocs=44421)
               0.0625 = fieldNorm(doc=1979)
       0.24 = coord(6/25)