INTRODUCTION: Existing record linkage methods do not handle missing linking field values in an efficient and effective manner. The objective of this study is to investigate three novel methods for improving the accuracy and efficiency of record linkage when record linkage fields have missing values. METHODS: By extending the Fellegi-Sunter scoring implementations available in the open-source Fine-grained Record Linkage (FRIL) software system we developed three novel methods to solve the missing data problem in record linkage, which we refer to as: Weight Redistribution, Distance Imputation, and Linkage Expansion. Weight Redistribution removes fields with missing data from the set of quasi-identifiers and redistributes the weight from the missing attribute based on relative proportions across the remaining available linkage fields. Distance Imputation imputes the distance between the missing data fields rather than imputing the missing data value. Linkage Expansion adds previously considered non-linkage fields to the linkage field set to compensate for the missing information in a linkage field. We tested the linkage methods using simulated data sets with varying field value corruption rates. RESULTS: The methods developed had sensitivity ranging from .895 to .992 and positive predictive values (PPV) ranging from .865 to 1 in data sets with low corruption rates. Increased corruption rates lead to decreased sensitivity for all methods. CONCLUSIONS: These new record linkage algorithms show promise in terms of accuracy and efficiency and may be valuable for combining large data sets at the patient level to support biomedical and clinical research.

We derive bounds on the probability of a goal node given a set of acquired input nodes. The bounds apply to decomposable networks; a class of Bayesian networks encompassing causal trees and causal polytrees. The difficulty of computing the bounds depends on the characteristics of the decomposable network. For directly connected networks with binary goal nodes, tight bounds can be computed in polynomial time. For other kinds of decomposable networks, the derivation of the bounds requires solving an integer program with a nonlinear objective function, a computationally intractable problem in the worst case. We provide a relaxation technique that computes looser bounds in polynomial time for more complex decomposable networks. We briefly describe an application of the probability bounds to a record linkage problem.

We study the sequential information acquisition problem for rule-based expert systems as follows: find the information acquisition strategy that minimizes the expected cost to operate the system while maintaining the same output decisions. This problem arises for rule-based expert systems when the cost or time to collect inputs is significant and the inputs are not known until the system operates. We develop several “optimistic” heuristics to generate information acquisition strategies and study their properties. The heuristics provide choices concerning precision (i.e., how optimistic) versus computational effort. The heuristics are embedded into an informed search algorithm (based on AO*) that produces an optimal strategy and a greedy search algorithm. The search strategies are designed for situations in which rules can overlap and the cost of collecting an input may depend on the set of inputs previously collected. We study the properties of these approaches and simulate their performance on a variety of synthetic expert systems. Our results indicate that the heuristics are very precise, leading to near optimal results for greedy search and moderate search effort for optimal search.

Sequential decision models are an important element of expert system optimization when the cost or time to collect inputs is significant and inputs are not known until the system operates. Many expert systems in business, engineering, and medicine have benefited from sequential decision technology. In this survey, we unify the disparate literature on sequential decision models to improve comprehensibility and accessibility. We separate formulation of sequential decision models from solution techniques. For model formulation, we classify sequential decision models by objective (cost minimization versus value maximization) knowledge source (rules, data, belief network, etc.), and optimized form (decision tree, path, input order). A wide variety of sequential decision models are discussed in this taxonomy. For solution techniques, we demonstrate how search methods and heuristics are influenced by economic objective, knowledge source, and optimized form. We discuss open research problems to stimulate additional research and development.

We propose a knowledge representation and operators for large, diverse model libraries. The knowledge representation distinguishes between model types that are classes of models defined by a collection of assumptions and model templates and instances that instantiate model types through decomposition and specialization of components. Underlying the knowledge representation are inheritance to represent the level of generalization and multiple levels of instantiation to represent the level of details among models. For inheritance, we define partial order relations for models and their components including domains, classes, units, assumptions, metrics, and constraints. For instantiation, we define constraints on transformations between model types, templates, and instances. The inexact search operators support content-based retrieval especially when it is difficult for a user to exactly specify the characteristics of models of interest. The operators use similarity functions to measure the closeness of a match between a search atom and the value of a model attribute. The explanation operators are designed to enhance users' understanding about the symbols, assumptions, components, and relationships among models. A prototype system has been implemented in Prolog to demonstrate the essential features of the model library system. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Extensions to database query languages for retrievals that involve inferencing on the nodes and edges of a graph are surveyed. Common types of inferencing are to find paths between two nodes, compute a value for a path such as a distance or an elapsed time, and to choose among alternative paths. The survey is based on the data model (relational or functional), method of extension (iteration, recursion, or special operators), interface style (string or tabular), and restrictions (data- and problem-oriented). The Quel, objected-oriented functional data, G-Whin, and Alpha languages are examined in detail with different values for these properties. The characteristics of other languages are summarized in several tables. The results of the survey indicate the diversity of language extensions and the need to provide data-model and query-language features to address such problems.>

The object-oriented functional data language (O/sup 2/FDL) is an interactive strongly typed database programming language that integrates the object-oriented and functional programming paradigms. It was designed for advanced applications that require a powerful and uniform database programming language supporting the software engineering principles of these tow paradigms. To this end, the O/sup 2/FDL supports inheritance and encapsulation of object-oriented languages, and an equational notation and strong typing of functional programming. Strong typing is extended with type restrictions to constrain the instantiations of type variables in function interfaces, while inheritance is augmented with a monotonic subtype rule for function redefinition. The O/sup 2/FDL also supports novel features. For the core of the O/sup 2/FDL, a denotational semantics based on an extended lambda -calculus is provided. For selected system-defined functions, operational semantics are provided and it is demonstrated that a subset of the O/sup 2/FDL is at least as expressive as the relational algebra.>

The Object-Oriented Functional Data Language (O/sup 2/FDL), an interactive, strongly typed database programming language, is discussed. It features inheritance and encapsulation of object-oriented languages and a functional notation for message expressions. The main contributions of the O/sup 2/FDL are: (1) functions of indefinite nesting levels that simplify nested list processing and form the basis of an efficient computation model; (2) path expressions that allow a flexible, graphical correspondence for database queries; (3) a type system featuring parametric and inclusion polymorphism, function restrictions, and type inferencing; and (4) system-defined functions that provide a concise and convenient notation for filtering aggregating, and combining objects. The versatility of the O/sup 2/FDL is demonstrated here for both relationally-complete expressions and more general computations.>

A form model and an expert database system that analyzes instances of the form model to derive a conceptual schema are proposed. The form model describes the properties of form fields such as their origin, hierarchical structure, and cardinality. The expert database design system creates a conceptual schema by incrementally integrating related collections of forms. The rules of the expert systems are divided into six phases form selection; entity identification; attribute attachment; relationship identification; cardinality identification; and integrity constraints. The rules of the first phase use knowledge about the form flow to determine the order in which forms are analyzed. The rules in other phases are used in conjunction with a designer dialog to identify the entities, relationships, and attributes of a schema that represents the collection of forms.>

New implementation techniques and new capabilities for database systems are being developed and proposed at a rapid rate. Novel file structures and improved algorithms for query optimization, buffer and recovery management, and transaction management have the potential of realizing significant gains in DBMS performance. The proposed integration of design objects, voice, text, rules, vector graphics, and images into databases promises exciting new capabilities for DBMSs. To accommodate advances in database technology and to support new classes of database applications, DBMSs must be extensible (i.e., customizable).

A global schema is an integrated view of heterogeneous databases. Identifying common types of information from the various local Schemas is an important part of designing a global schema. After matching the entity types and attributes, the designer constructs the global schema by applying a set of integration operators. In this paper, we propose two types of matching techniques and discuss their use in global schema design. Entity type matching partitions the entity types of the local Schemas into subsets with common information. Attributes within each entity type cluster are then matched according to the similarity of their meaning and scope. We define assertion types for both kinds of matching and provide an algorithm to check the consistency and completeness of attribute assertions.