Index selection for compiled database applications in embedded control programs

ABSTRACT

A compiled database application is a collection of modules in a software system that interact with a common database through a set of predefined transaction types. We call a compiled database application an embedded control program (ECP) if it is reasonable to consider the execution time of each transaction type to be either critical or non-critical. Usually, the common database for an ECP is referred to as the control data. In this paper, we consider the index selection problem for the control data of an ECP. We believe this is a novel problem because of the presence of real-time requirements. Unlike the objective of earlier work in index selection that aims to reduce the response time of queries, ours is to reduce storage requirements in a way that ensures efficient execution time for the critical query and update workload. We propose a solution that abstracts and manipulates the result requirements of the query component of the critical workload. The experiments we have conducted show that this approach can produce small physical structures that support fast execution of a workload with many updates.

REFERENCES

• 1: Surajit Chaudhuri , Vivek R. Narasayya, An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server, Proceedings of the 23rd International Conference on Very Large Data Bases, p.146-155, August 25-29, 1997
• 2: Surajit Chaudhuri , Vivek Narasayya, AutoAdmin “what-if” index analysis utility, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.367-378, June 01-04, 1998, Seattle, Washington, United States
• 3: S. Finkelstein , M. Schkolnick , P. Tiberio, Physical database design for relational databases, ACM Transactions on Database Systems (TODS), v.13 n.1, p.91-128, March 1988 [doi>10.1145/42201.42205]
• 4: {4} David Toman and Grant Weddell. On Attributes, Roles, and Dependencies in Description Logics and the Ackerman Case of Decision Problem. Proc. Description Logics, 2001.
• 5: {5} Transaction processing performance Council, http://www.tpc.org. TPC-C OLTP.
• 6: Alan Skelley, DB2 Advisor: An Optimizer Smart Enough to Recommend its own Indexes, Proceedings of the 16th International Conference on Data Engineering, p.101, February 28-March 03, 2000
• 7: G. E. Weddell, Selection of Indexes to Memory-Resident Entities for Semantic Data, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.274-284, June 1989 [doi>10.1109/69.87966]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
      H.2.4 Systems
          Subjects: Transaction processing; Query processing

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory