| A compiled database application consists of a collection of modules in a software system that interacts with a common database through a set of predefined transaction types. We will call a compiled database application an embedded control program (ECP) if quality of service requirements could be specified for some of the database operations in the different transaction types. Usually, the common database of an ECP is referred to as the control data. In this thesis we consider the problem of automating the physical design for the control data of an ECP. In particular, we show how to create, query, and update the data structures for the part of the database on which logarithmic time requirements are specified. Unlike the objectives of earlier works that aim to minimize the response time of the queries and updates in a workload, our goal is to minimize the storage requirements subject to the constraint that enough information is stored to allow for executing every database operation in the specified time-bound. Since not every SQL operation can be executed in logarithmic time, we introduce a subset of SQL that defines what constitutes a valid database operation on which a logarithmic time-bound requirement can be imposed.; We start by fixing the physical design space. In particular, we explore two novel physical design encodings. The first extends traditional indices by allowing records with different attributes to be indexed together. It also introduces branching ordering conditions (i.e., different orders can be specified on different disjoint subsets of indexed records) and it supports marking bits that can be used to efficiently traverse predefined subsets of indexed records. The second encoding consists of compact structures that have the capability of representing several indices with similar ordering conditions. Both physical designs have the desired compact representation property because both encodings can be used to reduce the need for storing redundant data.; We then construct a solution for each of the physical design models. Since the problem of finding the smallest possible encoding is NP-Hard for both physical designs, we present exponential time exact procedures and polynomial time approximate procedures for finding physical designs. |
