Representing and answering the queries about the dynamic behavior of processes in knowledge base systems has become a challenging research area in the eld of logic programming and knowledge representation systems. In this report, we are going to show how transaction logic can be used to e ciently represent dynamic behavior embedded in di erent domains. The ability of properly representing state changes in transaction logic enables us to express dynamic behavior of processes in di erent domains. The use of transaction logic to represent dynamic behavior decreases the size of knowledge bases and the query response time in comparison with other existing approaches. The e ciency of our method along with other features of transaction logic and its theoretical basis makes it an appropriate approach to represent dynamic behavior of processes in various domains.
In many real world applications of knowledge representations systems, e ective representation of processes embedded in the domain knowledge enables the knowledge base system to answer a wide range of queries about those processes. For example, in the medical domain, physiology explains di erent processes by showing how di erent organs and parts of a human body interacts with each other while anatomy discusses the structure of the human body and its organs. A medical knowledge base system needs to represent both of the physiological and anatomical knowledge in order to be able to answer the queries about diseases and medical experiments.
Let us illustrate this concept via an example. Consider the process of myocardial infarction (MI) or acute myocardial infarction (AMI) in medical science, which is commonly known as a heart attack. Basically, myocardial infarction results from the interruption of blood supply to a part of the heart, causing heart cells to die. This is most commonly due to occlusion (blockage) of a coronary artery following the rupture of a vulnerable atherosclerotic plaque, which is an unstable collection of lipids (cholesterol and fatty acids) and white blood cells (especially macrophages) in the wall of an artery. The resulting ischemia (restriction in bloood supply) and ensuing oxygen shortage, if left untreated for a su cient period of time, can cause damage or death (infarction) of heart muscle tissue (myocardium) [?]. The process starts with the step of increasing cholesterol and other lipids in the blood. This step is followed by the step of lipid dysregulation. After the step of lipid dysregulatoin, the formation of atherosclerotic plaque happens. The formation of atherosclerotic plaque causes narrowing of the coronary arteries and narrow coronary arteries leads to have to have insu cient blood supply for myocardial muscles. Finally, insu cient blood supply for myocardial muscles results in myocardial infarction. Representation of such process in a knowledge base system needs various features to exist in the system. The system needs to represent a process in terms of di erent steps. Each of those steps can be de ned as an abstract process as well. Each process de nes a set of potential dynamic changes in the system over the set of knowledge base facts. The execution of each step also depends on the various logical formulas evaluated at the di erent states of the knowledge base which are created during the course of the execution. It is apparent that those dynamic and static de nitions of changes and terms are tightly connected to each other.
This example shows that we need to explicitly represent processes in the knowledge base systems as they are associated with some features which may be involved in query answering. For example, time duration of execution of a process or the name of a process may be queried. However, explicit representation of processes may raise other issues. For example, treating processes as rst class entities of a knowledge base system may require us to express di erent relationships between those entities.
There are several logic programming frameworks which can be used to address the process representation problem in knowledge base systems. Situation calculus [1] provides a representation for state changes in logic. The basic concepts in the situation calculus are situations, actions, and uents. To describe a dynamic domain in the situation calculus, one speci es a set of actions describing what changes the situations. A set of uents is also required to describe the changing situations. Like the situation calculus, the event calculus [2] has actions, which are called events. It also has changing properties or uents. But unlike the standard situation calculus in which an exact sequence of hypothetical actions is represented, the event calculus is based on possibly incomplete specication of a set of actual event occurrences. Di erent event calculus extensions addressed the frame problem in di erent ways [3].
A class of action languages has been developed that is independent of a speci c axiomatization [4] [5] [6]. These languages try to provide high expressiveness, natural-language-like syntax, and clear formal semantics, which are important in procedural knowledge representation. [7] uses a modular action language, ALM in order to represent procedural knowledge. It was used to formalize of biological processes, including cell division, in ALM. [8] also uses an action modeling scripting language to represent and reason about signaling networks. [9] is also an variation of action language A[10] to represent procedural knowledge in biological networks. [11] also can be used to represent dynamic behavior in domain knowledge base systems.
Both of the above mentioned approaches are facing di culties when it comes to process representation. Since situation calculus is using monotonic reasoning and scienti c knowledge representation which usually involves non-monotonic reasoning, situation calculus is not suitable for process representation in scienti c domain. Process representation in event calculus has several problems. This formalization of events is intended as a formal analysis of the concepts rather than as a program or even as a program speci cation [2]. As updates in event calculus are additive and do not delete information about events, execution of a large number of process steps may be impractical. Explicit declaration of relation between processes also requires a large number of auxiliary predicates and rules. For example, to represent a containment relation between two processes, several rules and facts may be required. Although action modeling languages can represent processes in terms of action execution sequences, they are not scalable knowledge representation languages. Since they don't support features required for e cient knowledge representation such as object orientation and higher orderness, scienti c knowledge representation using this type of languages is harder and less reusable. Action and process de nition syntax in action modeling languages is usually di erent than regular logic programming syntax. That di erence makes the integration of dynamic behavior and static speci cation of domain knowledge di cult using action modeling languages.
Transaction Logic is an extension of classical predicate logic that accounts in a clean and declarative fashion for the phenomenon of state changes in logic programs and databases [12]. Our case study shows that T R eases the expression of dynamic behavior of the processes embedded in di erent domains. The logic of state changes provided by T R facilitates the inference about processes represented in T R. That representation of state changes within the logic formulas provides non-monotonic reasoning for procedural knowledge in scienti c domains. Since T R is a declarative formalism for specifying and executing procedures that update a logical theory, it can naturally express both the static knowledge and the dynamic behaviors in di erent scienti c domains. We can also combine T R with other logical formalism such as F-logic and HiLog in order to have object oriented and higher order formalisms. Those logical formalisms simplify the representation between processes. As dynamic behavior representation in T R does not need to have any axiomatization in order to address the frame problem, the process representation in T R is more scalable in comparison with other logical formulations of processes.
T R includes a Horn-like fragment which supports logic programming. This logic programming framework simpli es the integration of dynamic behavior with other components of knowledge base systems. Speci cation of processes in the language used for speci cation of logical terms and rules makes the expressiveness of logical formulas and terms available for process representation. This logic programming framework also helps us to easily express a wide range of queries about the dynamic behavior of processes. T R is also implemented in Flora [13], which is a perfect system for knowledge representation and reasoning.
Our process representation approach using T R shows that other features of T R can also help to have a very expressive and robust process speci cation in a knowledge base systems. For example, we took advantage of hypothetical queries to represent the concept of fault tolerant processes in the knowledge base systems. Incremental tabling and other developments in our implementation framework also may help us to improve query answering time.
We will explain our process representation technique in the next section. Section 3 will describe our case study experiments. We will also have a brief analysis of our results in section 3, and section 4 will conclude our study. 2
The over all representation of processes in T R is simple and natural. We classify processes into two groups: complex processes and primitive processes. A complex process is a sequence of complex or primitive processes and a primitive process is a single step of execution. The relationships between processes can be represented by simple logical predicates. For example, suppose process p1 is a sequence of processes p1; p2; p3. We use complex process=1 and primitive process=1 to indicate the type of process. f irst step(p; p1) says that process p1 is the rst step of process p. next step(p; p1; p2) and next step(p; p2; p3) show that p1 in p is followed by p2 and p2 in p is followed by p3. We do not provide the formal explanation of these concepts due to space limit.
To keep track of the execution of complex processes, we need a structure maintaining the execution status of the complex process. The current step of a process, current step(P; SP ), is an example of such a structure. A primitive process does not have internal structure.
Sequential execution of subprocesses can be de ned recursively as shown
below.
advance(P; CS) in (
Execution of primitive processes can be de ned in terms of elementary
transactions insert and delete. We also can extend the transition oracle and de ne
a speci c primitive process execution as a elementary transaction. For example,
assume the transaction doit(P ) executes the elementary transaction associated
to the primitive process P . We can show the successful and failed execution of
P as in (
Execution of primitive process may also include some conditional statements.
We can use such precondition and postcondition statements to guard the
execution of a primitive process. precondition(P ) and postcondition(P ) predicates
can simply express those postcondition and precondition statements for a
primitive process P . Now, we can show the successful and failed execution of P as
in (
g ^ result(p1; success):
postcondition(p3)
true:
(
Serial conjunctions used in our formulas allow sequential execution of
subprocesses. Note that in (
As shown in Figure 1, the comparison of systems in terms of lines of code shows that T R provides a more succinct representation by far. Generating auxiliary rules for inertia axioms, completeness of states, and execution possiblity, complicates ALd programs. We should also mention that the ALd program is including just one test query but T R and the event calculus based solutions responds to 7 queries. This means that for the equal test conditions, the size of ALd program would be much more than 707 lines.
As shown in Figures 2 and 3, via a set of sample queries, we considered
the response time of above mentioned implementations. The execution time also
shows that, T R is much faster than ALd. Moving to T R from event calculus,
(
T R
Method Lines of Code event calculus 1196 707 490 the overhead of transactional updates leads to decrease in the response time to test queries, which we are yet to understand. Our solution in T R also su ered from a bug in XSB which prevented us from taking advantages of incremental tabling. Because of that we had to refresh several tables after each transactional update. Fixing that bug will improve T R's response time.
This example apparently shows that T R is promising candidate for representing processes in knowledge base systems.
There are other features in Flora-2, which we used in our development. Object orientated syntax and higher order rules are examples of these features. As those features are beyond the scope of this report, we do not consider them here. 4
In this paper, we discussed several methods for representing processes, which are included in knowledge representation systems as part of domain knowledge. As mentioned before, dynamic domain languages require a large number of auxiliary rules and axioms, which complicates knowledge representation. They also lack many features that facilitate knowledge representation and process speci cation such as higher order rules and object orientation. T R allows de nitions of processes as rst class entities. Through an experiment, we showed that, it also simpli es programs and makes them more extensible and reusable. It also apparently improves the response time in comparison with methods based on action modeling languages.
We are planning to investigate T R's scalability in terms of size and complexity of process descriptions. Expansion of elementary updates to domain speci c updates are useful. In addition, we are planning to consider other capabilities of T R as a process representation tool. For example, we can study how T R can represent concurrent behaviors. In this way, we should consider how T R can encode other process speci cation conventions such as process algebra. For example, encoding process algebra's concepts and operational structural semantics in T R would enable it to act as a a theorem prover engine in the process algebra's domain.