Clinical care generates an immense amount of patient data that has been archived and manipulated by computer-based information systems. Such computer-based medical record systems improved the accessibility of clinical information and made several studies of such information possible. Unfortunately, the care provider's task of retrieving, integrating, and interpreting only those portions of the patient's record that are relevant to a specific clinical problem is actually becoming increasingly difficult. This difficulty can be attributed primarily to the large variety of minimum data sets, the heterogeneous formats used to store the data, the heterogeneous data access methods and procedures, the varying granularity of access to data, the different rigid views of the data, and the lack of inter-operability among the information repositories of such data sets. Recognizing the aforementioned issues, we are engaged in a project to build a multi-database environment tailored for the interoperability of medical information systems. The main building blocks of such a system are a multi-disciplinary minimum data set and a catalogue for the support of interoperability and customization functions. In this paper, we report on the design approach used and describe the general architecture of the system.

Backtracking aigorithms solve problems by selecting a variable and assigning each possible value to the variable. The resulting subproblems are simplified and solved recursively. Simple backtracking selects variables in a fixed order. Clause order backtracking selects variables from the first nontrivial clause that has not yet been satisfied. Formulas are given for the average time used by clause order backtracking when solving random CNF satisfiability problems, where the problem sets have v variables, t clauses, and a probability p of a literal being in a clause. The average time for clause order backtracking is always less than that for simple backtracking. It leads to polynomial time under many conditions where simple backtracking uses exponential average time. Cases where clause order backtracking uses average time less than $v^n $ (in the limit of v going to infinity) include $p < {1 / {(2v)}}e^{{{[(n - 1)\ln v - \ln t]} / t}} $ and $p > \sqrt {[\ln t + {{{{(\ln v)} / 2}]} / v}} $. (The second result needs a slight increase in the coefficient of $\ln t$ when t increases faster than $v^{\ln v} $.)

This paper gives exponential lower bounds for the average time of an algorithm based on a simplified version of the pure literal rule from the Davis–Putnam procedure. It is shown that this algorithm requires an average time that is exponential in v, the number of variables, when p, the probability that a literal is in a clause, is proportional to $1/v$ and t, the number of clauses in the predicate, is at least a linear function of v. The time is greater than any polynomial in v over a somewhat larger range of parameters. For the two cases $t = \Theta (\ln v)$ and $p = O(\ln v/v^{3/2} )$, the results of this lower-bound analysis are the same (to within a constant factor) as the upper-bound results in [SIAM J. Comput., 14 (1985), pp. 943–953]. The results of this and other papers show that the fastest analyzed algorithm for random satisfiability problems depends on the parameters of the distribution. Backtracking, the pure literal rule, and the new algorithm of Iwama [Report KSU/ICS 88-01, Institute of Computer Science, Kayoto Sangyo University, Kyoto, Japan, 1988 each have a large region of parameter setting where it is exponentially faster than the other two.