Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-03-16
2003-10-14
Homere, Jean R. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06633863
ABSTRACT:
1 BACKGROUND OF THE INVENTION
The aim of the invention is to support automatic modeling, analysis (verification) and real-time simulation of large-scale configuration problems on a standard computer (e.g. a personal computer). Mathematically speaking, such problems on finite domains or intervals can be expressed in terms of truth tables with M
N
combinations, each of which can assume either of the truth-values true or false (legal or non-legal). Here we are assuming N variables, each with M elements. Thus, binary variables are to be considered as a special case with M=2.
Obviously, M
N
combinations will cause “combinational explosion” and it is therefore not a trivial task to solve large configuration problems with a multitude of variables. Nevertheless, the present invention makes it possible to unify the seemingly contradictory requirements for completeness (all combinations must be accessible to ensure logical consistency) with compactness of representation and speed of simulation.
For example, interlocking systems for railway operation are controlled by several thousands variables representing signal values or switch positions. To illustrate, even a small interlocking system with 2000 binary variables will be characterized by the huge number of 2
2000
states or combinations. Some combinations are legal (allowed), while other combinations are clearly illegal because they would cause disasters. To handle these systems with conventional technology, it has been necessary to break down the system into subsystems of sufficiently small size to allow their validation, whereby not only illegal, but also a large number of legal combinations may be excluded, resulting in a less efficient utilization of the system. In general, the system variables will not be limited to binary values but will also include different data types on finite domains (e.g. multi-valued logic, integers, or finite sets of intervals). It is highly desirable to be able to handle configuration problems in systems of that size by means of computerized tools which could provide complete and correct responses almost instantaneously.
Another example is configuration of products or services (e.g. cars, computers or travels) on the Internet. Many products are available in a multitude of variants, which must be selected by the customer from a number of mutually dependent options. Thus, only some combinations of these options are possible or legal, while other combinations are illegal due to some technical or commercial constraints. It is therefore desirable to design e-commerce tools to enable the user to select interactively only the legal combinations, even from very complex product models.
While a number of computerized configuration tools have become available, e.g. the systems disclosed in WO 90/09001 and U.S. Pat. No. 5,515,524 there is still a demand for systems which fulfil the requirements for completeness and compactness and speed of response. In this context, the term “completeness” indicates the mathematical requirement that all combinations have been verified to ensure logical consistency.
The present invention provides an elegant solution to this problem without the problem of “combinational explosion”. As it will be understood from the following description, the crux of the invention is the establishment of a novel type of database, in the following termed an “array database”. While the database is an optimal tool for the complex configuration problems indicated above and described in greater in the following, it will be understood that due to its unique inherent advantages, it is also useful for a wide range of applications for which conventional database systems, typically relational databases, are used at present.
A scientific/mathematical discussion of principles relevant to the invention is given in Moller, Gert L.:
On the Technology of Array
-
based Logic
. Ph.D. thesis, Electric Power Engineering Department, Technical University of Denmark, January 1995.
2 BRIEF DISCLOSURE OF THE INVENTION
In one aspect, the invention relates to a method for generating a database useful for configuring and/or optimizing a system spanned by variables on finite domains and/or intervals, said method comprising generating and storing, in a memory or storage medium of a computer, an addressable configuration space of the entire system in terms of all legal Cartesian subspaces of states or combinations satisfying the conjunction of substantially all system constraints on all variables, with all interconnected legal Cartesian subspaces being addressable as legal combinations of indices of link variables, so as to establish a database in which substantially all legal solutions in the system are stored as nested arrays.
In the following, the database generated according to the invention will be termed an “array database”, this term reflecting the fact that all legal solutions are stored in the database as one or more nested arrays.
Definitions and explanations relevant to some of the terms used in the present specification and claims are as follows:
“Configuring” means establishing substantially all legal combinations of the variables satisfying substantially all the constraints on the system. Preferably, all legal combinations of the variables satisfying all the constraints on the system are established, in which preferred case the legal Cartesian subspaces of states or combinations will satisfy the conjunction of all system constraints on all interconnected variables.
“Optimizing” means applying a heuristic selection of combinations within a set of legal combinations.
The term “a system spanned by variables on finite domains and/or intervals” indicates that each variable of the system consists of a finite set of elements or state values (e.g., logical truth values) or a finite set of intervals.
The term “An addressable configuration space” indicates that substantially all legal combinations are explicitly represented; in the preferred case, all legal combinations are explicitly represented.
“A Cartesian subspace” is a compact representation of one or more legal combinations, all combinations being derivable/calculated/ as the Cartesian product of the elements or state values for each variable.
“System constraints” are the relations (propositional functions) on variables defined for the system.
“Interconnecting variables” indicates variables present in at least two relations.
“A link variable” means a variable generated by the method according to the invention and added to a given relation with a unique index which identifies one Cartesian subspace.
“Interconnected legal Cartesian subspaces” means legal Cartesian subspaces with at least one common variable.
It is a crucial feature of the invention that all illegal states or combinations violating the system constraints are excluded from the relations. Such exclusion of illegal states or combinations can preferably be performed while the database is generated by the method according to the invention, the illegal states or combinations being excluded whenever identified. A state of contradiction or inconsistency is present in a system if just one relation of the system has no legal combination or state. On the other hand, a system is said to be consistent if at least one state or combination is legal, i.e. satisfying all system constraints. If, in the generation of the database, just one relation of a system is found to have no legal combination or state, then that whole system is in a state of contradiction or inconsistency and must be excluded.
In the following, the process of colligating relations (that is, combining relations to arrive at a more complex subsystem or system) is discussed in greater detail. It will be understood that on each level of the colligation process, inconsistencies or contradictions will be identified and will, thus, result in exclusion of the colligated subsystem or system. Thus, when the generating process has been completed, the system will be consistent, as manifested by all relations having at least one legal Cartesian subspace.
I
Jensen Claus Erik
Sørensen Møller Gert Lykke
Ali Mohammed
Array Technology ApS
Homere Jean R.
LandOfFree
Database useful for configuring and/or optimizing a system... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Database useful for configuring and/or optimizing a system..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Database useful for configuring and/or optimizing a system... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3136798