Deductive Databases and P Systems

Deductive Databases and P Systems Miguel Angel GUTI´ ERREZ-NARANJO Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: [email protected] Vladimir ROGOZHIN The State University of Moldova 60 Mateevich str., MD-2009 Chi¸sin˘au, Moldova E-mail: [email protected] Abstract. In computational processes based on backwards chaining, a rule of the type A←B1, . . . , Bnis seen as a procedure which points that the problem Acan be split into the problems B1, . . . , Bn. In classical devices, the subproblems B1, . . . , Bnare solved sequentially. In this paper we present some questions that circulated during the Second Brainstorming Week related to the application of the parallelism of P systems to computation based on backwards chaining, and we illustrate them with the example of inferential deductive process. 1 Introduction In computational processes based on backwards chaining, a rule of the type A← B1, . . . , Bnis usually seen as a procedure which points that the problem Acan be split into the problems B1, . . . , Bnwith the hope that B1, . . . , Bnare simpler than A. In the case of getting B1, . . . , Bnsolved, we also have a solution for Avia this rule. This is the case of pure Prolog [2, 10] where A←B1, . . . , Bnis a definite clause and A, B1, . . . , Bnare positive literals. Prolog uses SLD resolution to find an answer to the goal A, with SLD coming from Linear resolution for Definite clauses with Selection function. This selection function considers sequentially the list of current subgoals B1, . . . , Bnand chooses one of them (in standard Prolog the selection function always takes the leftmost literal). The process of finding an answer for the chosen subgoals generates new subgoals, hopefully simpler than the previous one. The computation ends when trivial subgoals are reached. The selection mapping is necessary because classic computational devices work sequentially, so we need to fix an order between the tasks. In this paper we present some questions that circulated during the Second Brainstorming Week related to the application of the parallelism of P systems to the computation based on backwards chaining. 258 2 Logic Programming Although the computation based on backwards chaining is a general procedure in computer science, we focus our attention on Deductive Databases and Logic Programming. The way of representing information in Logic Programming (see, e.g., [1, 3, 6, 8, 4]) is via a set of clauses. These sets of clauses are logic programs. Roughly speaking, a clause is a first-order rule, where both sides of the rule consists of atoms, i.e., a predicate applied to some arguments. Formally, a clause is a formula ∀x1. . . ∀xsA1∨. . . Ak∨ ¬B1∨ · · · ∨ ¬Bn, where x1, . . . , xsare all the variables that occur in the atoms A1, . . . , Ak, B1, . . . , Bn. A clause 1is a Horn clause if it contains at most one positive literal (atom) and it is a definite clause if it contains exactly one positive literal. For example ∀X∀Y daughter(X, Y )∨ ¬female(X)∨ ¬mother(Y, X) is a definite clause. This universally quantified formula is usually written as daughter(X, Y )←female(X), mother(Y, X). The positive literal, i.e. the conclusion of the implication is usually called the head of the clause. The rest of the literals, the premises, is known as the body or the tail of the clause. Definite clauses can consist on a single positive literal. They can be considered as rules with no tail or no conditional sentences, such as female(anne)← mother(mary, anne)← These clauses are facts. A substitution θ={V1/t1, . . . , Vn/tn}is an assignment of terms ti to variables Vi. If a substitution is applied to a clause, then we get an instantiated clause, where all occurrences of the variable Viis replaced by the term ti. For example, if the substitution θ={X/anne}is applied to the clause C: daughter(X, Y )←female(X), mother(Y, X), then we get the clause Cθ: daughter(anne, Y )←female(anne), mother(Y, anne). A substitution θis a unifier of the atoms Aand Bif Aθ =Bθ. Logic programs compute through a combination of two mechanisms: unification and resolution. From any two clauses with complementary literals Aand ¬Athe inference rule of resolution derives a new clause as consequence. For example, from daughter(anne, Y )←female(anne), mother(Y, anne) female(anne)← we obtain the clause daughter(anne, Y )←mother(Y, anne). The deduction process is goal driven in the following way. If we have the program daughter(X, Y )←female(X), mother(Y, X) female(anne)← mother(mary, anne)← 1The basic difference between program clauses and database clauses is the use of types. 259 and we want to know if daughter(anne, mary) is true, first we build the goal ←daughter(anne, mary), i.e., the one-literal clause ¬daughter(anne, mary). The atoms daughter(anne, mary) and daughter(X, Y ) unifies with the substitution θ={X/anne, Y/mary}. By using resolution with the first clause of the program and the unifier θwe get the new goal ←female(anne), mother(mary, anne). As we saw before, this step can be seen in a procedural mode. The problem of deciding if daughter(anne, mary) is true has been split into two subproblems: Decide if female(anne) and mother(mary, anne) are true or not. But they are true because they are claimed by our program, so daughter(anne, mary) is true. When the reasoning system solves the goal Qit gives us an answer. There are two types of outputs given by the system with respect to the type of the goal Q: 1. If the goal does not contain variables, then we have a decision problem, and the possible answers are Yes or No. In this case the system decides if the goal can be or not derived form the program. 2. If the goal contains variables, then the system outputs the unifier θsuch that the instantiated goal Qθ can be derived from the problem. This unifier represents the answer to the question, and obviously several unifications θthat make the goal Qθ true can exist. In our example, we deal with a decision problem. After the first step the subgoals female(anne) and mother(mary, anne) have to be solved. This is done sequentially in classical devices with only one processor. We wonder whether it is possible to use P systems for these problems. We think that it would be very interesting to use the parallelism of P systems to solve all subgoals in a parallel manner. 3 P Systems Now we are going to give some hints about a general representation of a set of typed definite clauses (Deductive Database) and of the inferential deductive process in the frame of hierarchical P systems [9] with active membranes [5]. Let us consider a Deductive Database (DDB) Q1←P11, P12, . . . , P1m Q2←P21, P22, . . . , P2m . . . . . . . . . . . . . . . Qn←Pn1, Pn2, . . . , Pnm We assume for simplicity that we have the same set of parameters {x1, . . . , xs} ∈ Dsfrom the same domain Dfor all literals Qi, i ∈ {1, . . . , n}, Pij, i ∈ {1, . . . , n}, j ∈ {1, . . . , m}, and the same order of parameters (x1, . . . , xs) for the heads of all rules. The literals from tails are allowed to have any order of parameters. We can ask goals presented as literals with constant terms and/or variables in the set of parameters to the inferential deductive machine. The constants will be denoted by ciand 260 variables will be denoted by vi. We assume that goal have the same order of parameters (x1, . . . , xs) as the heads of DDB clauses. Now we will give the general model of logic inferential deductive machine and some ideas how it can be represented in the framework of P systems. Consider the DDB described above and the goal Q. The logic inferential deduction process will be performed recursively according to the following steps: ALGORITHM: SOLVE INPUT: Q PART 1: From the goal to the axioms: Step 1 Head unification: Unification of Qwith all heads Qifrom DDB in parallel. As a result, every head Qifor which the unification process succeeded will get the set of unifiers θi. Step 2 Body unification: For every head Qifor which step 1 succeeded and the tail is not empty, body unification process will be performed with all subgoals Pij in parallel, that is, the algorithm SOLV E will be launched in parallel for every subgoal Pij with input Pijθi. In the case of facts (rules with empty tail), the system returns the unifier θi of the head Qi. PART 2: From the axioms to the goal Step 3 Atom unification: For every rule for which step 2 succeeded, the unification of results of all subgoals is performed. Step 4 Union of the results: Since every particular rule from the DDB gives us some set of unifiers (solutions), one should consider the union of all these sets as a solution of Q. OUTPUT: There are possible two cases: 1. The result to be the set of all unifiers Θ = {θ|DDB `Qθ}. In other words, the result will be the set of all unifiers θfor which Qθ could be derived from DDB 2. The result to be Yes in the case Θ = {θ}, Q =Qθ and No in the case Θ = ∅ In this way we have got two types of parallelism here: 1. For each head Qia process which unifies it with Qand which unifies results of subgoals Pij is created; 2. For each subgoal Pij of Qithe solving process is created. In Figure 1 the general scheme of the deduction process and of the parallel processes interactions is presented. For each process from the scheme a membrane is created. In this way one can treat the tree of the processes interaction as a hierarchy of membranes of the P system solving the problem. One can define two general types of membranes: 1. Membranes which stay for goals and subgoals representation. Membranes of this type perform steps 1 and 4. In Step 1 they create submembranes which stay for the heads of the clauses. In Step 4 it collects results of the inferential rules execution. 261 Figure 1: The general scheme of the deduction process and of the processes interaction 2. Membranes which stay for clause’s heads representation. They perform steps 2 and 3. For this type of membranes there are possible two cases: The tail is not empty: the membranes complete the term unification of the head and goal, create submembranes which stay for the subgoals, and perform term unification with all subgoals. The tail is empty: the membranes complete the term unification. All these ideas need to be specified, formalized, and developed, and we hope to return to this topic in a forthcoming research. 4 Final Remarks In this work-in-progress paper we describe some preliminary ideas born from discussions about this topic during the Second Brainstorming Week. This is only the beginning and a lot of work have to be done. A first step is to fix the backwards chaining formalism that we want to study in P systems. Function-free clauses, i.e., clauses which contains only variables as terms can be a good starting points, but to handle relevant information Datalog [11] clauses can be more suitable. Datalog clauses are definite clauses that contains 262 no functions symbols of non-zero arity. As we have mentioned, we have a long path to walk. Acknowledgment. Miguel A. Guti´errez Naranjo is partially supported by the project TIC2002-04220-C03-01 of the Ministerio de Ciencia y Tecnolog´ıa of Spain, cofinanced by FEDER funds, while Vladimir Rogozhin is supported by ”MolCoNet” project IST-2001- 32008. References [1] Apt, K.R.: Logic Programming, Handbook of Theoretical Computer Science. Elsevier Science Publishers B.V., 1990 [2] Bratko, I.: PROLOG Programming for Artificial Intelligence, Third edition. Addison- Wesley, 2001. [3] Doets K.: From Logic to Logic Programming. The MIT Press, 1994. [4] Dzeroski, S., Lavrac N.: An Introduction to Inductive Logic Programming in Relational Data Mining, Springer, Berlin 2001. pp.:48-73 [5] Krishna S.N., Rama R.: A Variant of P Systems with Active Membranes: Solving NP-Complete Problems. Romanian Journal of Information Science and Technology, 2, 4 (1999), 357–367. [6] Lloyd J.W.: Foundations of Logic Programming. (2nd ed.) Springer, Berlin, 1987 [7] Metakides G., Nerode A.: Principles of Logic and Logic Programming, Studies in Computer Science nd Artificial Intelligence, 1996. [8] Nienhuys-Cheng S.H., de Wolf R.: Foundations of Inductive Logic Programming, LNAI 1228. Springer 1997. [9] P˘aun, Gh.: Computing with Membranes, Journal of Computer and System Sciences, 61, 1 (2000), 108–143. [10] Logic Programming: http://www.afm.sbu.ac.uk/logic-prog/ [11] Deductive Databases: The DATALOG Approach: http://goanna.cs.rmit.edu.au/ zahirt/Teaching/subj-datalog.html 263