Improving Predictability of Transaction Execution Times in Real-time Databases | Real-Time Systems Skip to main content
Springer Nature Link
Log in

Improving Predictability of Transaction Execution Times in Real-time Databases

  • Published:
Real-Time Systems Aims and scope Submit manuscript

Abstract

We present a design for multi-versionconcurrency control and recovery in a main memory database, anddescribe logical and physical versioning schemes that allowread-only transactions to execute without obtaining data itemlocks or system latches. Our schemes enable a system to providethe guarantee that updaters will never interfere with read-onlytransactions, and read-only transactions will not be delayeddue to data contention. Consequently, transaction executionsbecome more predictable—this partially alleviates a majorproblem in real-time database system (RTDBS) scheduling, namely,significant unpredictability in transaction execution times.As a result, in addition to a transaction's deadline, a moreaccurate estimate of its execution time can also be taken intoaccount, thus facilitating better scheduling decisions. Our contributionsinclude several space saving techniques for the main-memory implementation,including improved methods for logical aging of data items andthe introduction of physical aging for low-level structures.Some of these schemes have been implemented on a widely-usedsoftware platform within Lucent, and the full scheme is implementedin the Dalí main-memory storage manager.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Abbott, R., and Garcia-Molina, H. 1988. Scheduling real-time transactions: A performance evaluation. In Procs. of the International Conf. on Very Large Databases.

  • Abbott, R., and Garcia-Molina, H. 1989. Scheduling real-time transactions with disk-resident data. In Procs. of the International Conf. on Very Large Databases.

  • Agrawal, D., and Sengupta, S. 1989. Modular synchronization in multiversion databases: Version control and concurrency control. ACM SIGMOD Conf. on the Management of Data 89, (Portland OR), -Jun May.

  • Aho, A., Hopcroft, J., and Ullman, J. D. 1974. The Design and Analysis of Computer Algorithm. Addison-Wesley.

  • Bayer, R., Heller, H., and Reiser, A. 1980. Parallelism and recovery in database systems. ACMTrans. on Database Systems 5(2): 139–156. June.

    Google Scholar 

  • Bernstein, P. A., and Goodman, N. 1983. Multiversion concurrency control — theory and algorithms. ACM Transactions on Database Systems 8(4): 465–483. December.

    Google Scholar 

  • Bober, P., and Carey, M. 1992. On mixing queries and transactions via multiversion locking. In Proc. IEEE CS Intl. Conf. on Data Engineering 8, Tempe, AZ. February.

  • Bober, P., and Carey, M. 1992. Multiversion query locking. In Proceedings of the Conference on Very Large Databases 18, Vancouver. Los Altos, CA: Morgan Kaufman. August.

    Google Scholar 

  • Bohannon, P., Leinbaugh, D., Rastogi, R., Seshadri, S., Silberschatz, A., and Sudarshan, S. 1995. Logical and physical versioning in main memory databases. Technical Report 113880-951031-12, AT&T Bell Laboratories, Murray Hill.

    Google Scholar 

  • Chan, A., Fox, S., Lin, W-T.K., Nori, A., and Ries, D. R. 1982. The implementation of an integrated concurrency control and recovery scheme. In ACM SIGMOD Conf. on the Management of Data 82, Orlando FL, pp. 184–191. June.

  • DeWitt, D. J., Katz, R., Olken, F., Shapiro, D., Stonebraker, M., and Wood, D. 1984. Implementation techniques for main memory database systems. Proc. ACM-SIGMOD 1984 Int'l Conf. on Management of Data. pp. 1–8. June.

  • Gottemukkala, V., and Lehman, T. 1992. Locking and latching in a memory-resident database system. In Proceedings of the Eighteenth International Conference on Very Large Databases, Vancouver, pp. 533–544. August.

  • Hadzilacos, T. 1988. Serialization graph algorithms for multiversion concurrency control. In Proceedings of the ACM SIGACT-SIGART-SIGMOD Symposium on Principles of Database Systems. pp. 135–141. March.

  • Haritsa, J., Carey, M., and Livny, M. 1990. Dynamic real-time optimistic concurrency control. In Proceedings of the IEEE Real-Time Systems Symposium.

  • Haritsa, J., Carey, M., and Livny, M. 1990. On being optimistic about real-time constraints. In Proceedings of the ACM SIGACT-SIGART-SIGMOD Symposium on Principles of Database Systems.

  • Haritsa, J., Carey, M., and Livny, M. 1993. Value-based scheduling in real-time database systems. VLDB Journal 2(2): 117–152.

    Google Scholar 

  • Huang, J., Stankovic, J., Ramamritham, K., and Townsley, D. 1989. Experimental evaluation of real-time transaction processing. In Proceedings of the IEEE Real-Time Systems Symposium.

  • Huang, J., Stankovic, J., Ramamritham, K., and Townsley, D. 1991. On using priority inheritance in real-time databases. In Proceedings of the IEEE Real-Time Systems Symposium.

  • Ibaraki, T., Kameda, T., and Katoh, N. 1990. Multiversion cautious schedulers for database concurrency control. IEEE Transactions on Software Engineering (SE),; ACM Computing Reviews 9012-0981. 16(3). March.

  • Jagadish, H. V., Liuwen, D., Rastogi, R., Silberschatz, A., and Sudarshan, S. 1994. Dali: A high performance main-memory storage manager. In Procs. of the International Conf. on Very Large Databases.

  • Kim, Y., and Son, S. H. 1996. Supporting predictability in real-time database systems. In Proceedings of the IEEE Real-Time Technology and Applications Symposium.

  • Kung, H. T., and Lehman, P. L. 1980. Concurrent manipulation of binary search trees. ACM Transactions on Database Systems 5(3): 354–382. September.

    Google Scholar 

  • Lam, K., Son, S. H., Lee, V., and Hung, S. 1998. Using separate algorithms to process read-only transactions in real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium.

  • Lehman, T. J., and Carey, M. J. 1986. A study of index structures for main memory database management systems. In Proceedings of the Conference on very Large Databases 12, Kyoto, pp. 294–303. Los Altos, CA: Morgan Kaufman. August.

    Google Scholar 

  • Lehman, T., Shekita, E. J., and Cabrera, L. 1992. An evaluation of Starburst's memory resident storage component. IEEE Transactions on Knowledge and Data Engineering 4(6): 555–566. December.

    Google Scholar 

  • Manber, U., and Ladner, G. D. 1982. Concurrency control in dynamic search structures. ACM Proc. on Database Systems, Boston, pp. 268–282. April.

  • Mohan, C., and Levine, F. 1992. Aries/im an efficient and high concurrency index management method using write-ahead logging. In ACM SIGMOD Conf. on the Management of Data 92, San Diego, June.

  • Mohan, C., Pirahesh, H., and Lorte, R. 1992. Efficient and flexible methods for transient versioning of records to avoid locking by read-only transactions. In ACM SIGMOD Conf. on the Management of Data 92, San Diego, June.

  • Ramamritham, K. 1993. Real-time databases. International Journal of Distributed and Parallel Databases 1: 199–226.

    Google Scholar 

  • Reed, D. P. 1978. Naming and synchronization in a decentralized computer system. Technical Report MIT-LCSTR-205. Cambridge: Massachusetts Institute of Technology. September.

    Google Scholar 

  • Salem, K., and Garcia-Molina, H. 1990. System M: A transaction processing testbed for memory resident data. IEEE Transactions on Knowledge and Data Engineering 2(1): 161–172. March.

    Google Scholar 

  • Shasha, D., and Goodman, N. 1988. Concurrent search structure algorithms. ACM Transactions on Database Systems 13(1): 53–90, March.

    Google Scholar 

  • Stankovic, J., and Zhao, W. 1988. On real-time transactions. ACM Sigmod Record 17(1): 4–18.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ, 07974-0636

    Rajeev Rastogi, S. Seshadri, Philip Bohannon, Dennis Leinbaugh & Avi Silberschatz

  2. Computer Science and Engineering Dept., Indian Institute of Technology, Bombay, India

    S. Sudarshan

Authors
  1. Rajeev Rastogi
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. S. Seshadri
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Philip Bohannon
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Dennis Leinbaugh
    View author publications

    You can also search for this author inPubMed Google Scholar

  5. Avi Silberschatz
    View author publications

    You can also search for this author inPubMed Google Scholar

  6. S. Sudarshan
    View author publications

    You can also search for this author inPubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Rastogi, R., Seshadri, S., Bohannon, P. et al. Improving Predictability of Transaction Execution Times in Real-time Databases. Real-Time Systems 19, 283–302 (2000). https://doi.org/10.1023/A:1008143228351

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008143228351