Effective patch management is critical to ensure the security of information systems that modern organizations count on today. Facing numerous patch releases from vendors, an information technology (IT) manager must weigh the costs of frequent patching against the security risks that can arise from delays in patch application. To this end, we develop a rigorous quantitative framework to analyze and compare several patching policies that are of practical interest. Our analyses of pure policies—policies that rely on a single metric such as elapsed time or patch severity level—show that certain policies are never optimal and no single policy may fit all information systems uniformly well. Depending on the context parameters, particularly the setup and business disruption costs for patching, either a time-based approach or an approach based on the cumulative severity level may be effective. To develop a more complete guideline for policy selection, we decipher hybrid policies that combine multiple metrics. Finally, we conduct extensive numerical experiments to verify the robustness of our analytical results. Overall, our paper establishes a comprehensive framework for analyzing various patching policies and furnishes useful insights for IT managers.

The need to consolidate the information contained in heterogeneous data sources has been widely documented in recent years. In order to accomplish this goal, an organization must resolve several types of heterogeneity problems, especially the entity heterogeneity problem that arises when the same real-world entity type is represented using different identifiers in different data sources. Statistical record linkage techniques could be used for resolving this problem. However, the use of such techniques for online record linkage could pose a tremendous communication bottleneck in a distributed environment (where entity heterogeneity problems are often encountered). In order to resolve this issue, we develop a matching tree, similar to a decision tree, and use it to propose techniques that reduce the communication overhead significantly, while providing matching decisions that are guaranteed to be the same as those obtained using the conventional linkage technique. These techniques have been implemented, and experiments with real-world and synthetic databases show significant reduction in communication overhead.

Although pricing communication services has received attention, there has been little work where quality-of-service (QoS) guarantees are incorporated into ex ante pricing of communication links. In recent years, however, data networks providing services with QoS guarantees have become quite popular. We study optimal pricing for communication links provided over packet-switching networks with explicit QoS guarantees in terms of an expected per-packet delay. We first develop a pricing scheme for multiple classes of service when the delay guarantees are fixed and exogenously determined and analyze this scheme with one and two classes. Subsequently, we extend this analysis to the case where a provider can choose her own QoS parameters. We also examine long-run pricing and capacity planning for one and two classes of service. Finally, we consider other QoS guarantees such as jitter, packet-loss ratio and maximum delay.

The notion of a data warehouse for integrating operational data into a single repository is rapidly becoming popular in modern organizations. An important issue in this context is how often one should synchronize the data warehouse to reflect the changes in the constituent operational data sources. If the synchronization is performed very frequently, the associated cost might be quite high, although the data warehouse would only have a small amount of stale data. On the other hand, if the data warehouse is synchronized infrequently, it might result in costly errors in business decisions arising from the stale data. This paper examines the trade-off between the synchronization and staleness costs and derives the optimal synchronization frequency.

Several approaches have been proposed for representing uncertain data in a database. These approaches have typically extended the relational model by incorporating probability measures to capture the uncertainty associated with data items. However, previous research has not directly addressed the issue of normalization for reducing data redundancy and data anomalies in probabilistic databases. We examine this issue. To that end, we generalize the concept of functional dependency to stochastic dependency and use that to extend the scope of normal forms to probabilistic databases. Our approach is a consistent extension of the conventional normalization theory and reduces to the latter.

In modern organizations, decision makers must often be able to quickly access information from diverse sources in order to make timely decisions. A critical problem facing many such organizations is the inability to easily reconcile the information contained in heterogeneous data sources. To overcome this limitation, an organization must resolve several types of heterogeneity problems that may exist across different sources. We examine one such problem called the entity heterogeneity problem, which arises when the same real-world entity type is represented using different identifiers in different applications. A decision-theoretic model to resolve the problem is proposed. Our model uses a distance measure to express the similarity between two entity instances. We have implemented the model and tested it on real-world data. The results indicate that the model performs quite well in terms of its ability to predict whether two entity instances should be matched or not. The model is shown to be computationally efficient. It also scales well to large relations from the perspective of the accuracy of prediction. Overall, the test results imply that this is certainly a viable approach in practical situations.

Although database design tools have been developed that attempt to automate (or semiautomate) the design process, these tools do not have the capability to capture common sense knowledge about business applications and store it in a context-specific manner. As a result, they rely on the user to provide a great deal of "trivial" details and do not function as well as a human designer who usually has some general knowledge of how an application might work based on his or her common sense knowledge of the real world. Common sense knowledge could be used by a database design system to validate and improve the quality of an existing design or even generate new designs. This requires that context-specific information about different database design applications be stored and generalized into information about specific application domains (e.g., pharmacy, daycare, hospital, university, manufacturing). Such information should be stored at the appropriate level of generality in a hierarchically structured knowledge base so that it can be inherited by the subdomains below. For this to occur, two types of learning must take place. First, knowledge about a particular application domain that is acquired from specific applications within that domain are generalized into a domain node (e.g., entities, relationships, and attributes from various hospital applications are generalized to a hospital node). This is referred to as within domain learning. Second, the information common to two (or more) related application domain nodes is generalized to a higher-level node; for example, knowledge from the car rental and video rental domains may be generalized to a rental node. This is called across domain learning. This paper presents a methodology for learning across different application domains based on a distance measure. The parameters used in this methodology were refined by testing on a set of representative cases; empirical testing provided further validation.

Much of the work on conceptual modeling involves the use of an entity-relationship model in which binary relationships appear as associations between two entities. Relationships involving more than two entities are considered rare and, therefore, have not received adequate attention. This research provides a general framework for the analysis of relationships in which binary relationships simply become a special case. The framework helps a designer to identify ternary and other higher-degree relationships that are commonly represented, often inappropriately, as either entities or binary relationships. Generalized rules are also provided for representing higher-degree relationships in the relational model. This uniform treatment of relationships should significantly ease the burden on a designer by enabling him or her to extract more information from a real-world situation and represent it properly in a conceptual design.

Although it is possible to encode a great deal of process knowledge about database design into a system, experience has shown that the contribution of a human designer extends beyond his or her knowledge of database design techniques. The next step in the evolution of automated database design tools is to incorporate knowledge and reasoning capabilities to support this higher level of participation. Doing so requires some understanding of what different terms mean. This paper presents an ontology that can be used as a surrogate for the meaning of words in a database design system to simulate the contributions that a designer would make based on his or her general knowledge. The ontology classifies a term into one or more categories such as person, abstract good or tradable document. It is comprised of a semantic network, a knowledge base containing information on the meaning of terms that have been classified, an expert system knowledge-acquisition component, and a distance measure for assessing the distance between the meanings of terms. The ontology was tested by different types of users on a variety of problems and was shown to be quite effective.

A database allows its users to reduce uncertainty about the world. However, not all properties of all objects can always be stored in a database. As a result, the user may have to use probabilistic inference rules to estimate the data required for his decisions. A decision based on such estimated data may not be perfect. The authors call the costs associated with such suboptimal decisions the cost of incomplete information. This cost can be reduced by expanding the database to contain more information; such expansion will increase the data-related costs because of more data collection, manipulation, storage, and retrieval. A database designer must then consider the trade-off between the cost of incomplete information and the data-related costs, and choose a design that minimizes the overall cost to the organization. In temporal databases, the sheer volume of the data involved makes such a trade-off at design time all the more important. They develop probabilistic inference rules that allow one to infer missing values in spatial, as well as temporal, dimension. They then use the framework for developing guidelines for designing and reorganizing temporal databases, which explicitly includes a trade-off between the incomplete information and the data-related costs.

Automated database design systems embody knowledge about the database design process. However, their lack of knowledge about the domains for which databases are being developed significantly limits their usefulness. A methodology for acquiring and using general world knowledge about business for database design has been developed and implemented in a system called the Common Sense Business Reasoner, which acquires facts about application domains and organizes them into a a hierarchical, context-dependent knowledge base. This knowledge is used to make intelligent suggestions to a user about the entities, attributes, and relationships to include in a database design. A distance function approach is employed for integrating specific facts, obtained from individual design sessions, into the knowledge base (learning) and for applying the knowledge to subsequent design problems (reasoning).

Although the relational model for databases provides a great range of advantages over other data models, it lacks a comprehensive way to handle incomplete and uncertain data. Uncertainty in data values, however, is pervasive in all real-world environments and has received much attention in the literature. Several methods have been proposed for incorporating uncertain data into relational databases. However, the current approaches have many shortcomings and have not established an acceptable extension of the relational model. In this paper, we propose a consistent extension of the relational model. We present a revised relational structure and extend the relational algebra. The extended algebra is shown to be closed, a consistent extension of the conventional relational algebra, and reducible to the latter.

Although widely advocated as a tool for the conceptual modelling of data, the Entity-Relationship (E-R) model [4] and its extensions are generally lacking in constructs to model the dynamic nature of the real world, making them inadequate for designing temporal databases. This research first extends the E-R model to a Temporal Event-Entity-Relationship Model (TEERM), by introducing events as an additional construct. Second, a method is proposed for mapping this conceptual model into a temporal relational model for the logical design of temporal relational databases with a corresponding set of integrity constraints. The model is illustrated with an example and evaluated using a set of criteria proposed by ^B^a^t^i^n^i^ ^e^t^ ^a^l^.^ ^[^2^]. The model appears to be expressive, simple and easy to use, and should, therefore, aid the temporal database design process significantly.