Browsing by Author "Minker, Jack"
Now showing 1 - 4 of 4
Results Per Page
Sort Options
Item Computing Stable and Partial Stable Models of Extended Disjunctive Logic Programs(1998-10-15) Ruiz, Carolina; Minker, JackIn [Prz91], Przymusinski introduced the partial (or 3-valued) stable model semantics which extends the (2-valued) stable model semantics defined originally by Gelfond and Lifschitz [GL88]. In this paper we describe a procedure to compute the collection of all partial stable models of an extended disjunctive logic program. This procedure consists in transforming an extended disjunctive logic program into a constrained disjunctive program free of negation-by-default whose set of 2-valued minimal models corresponds to the set of partial stable models of the original program. (Also cross-referenced as UMIACS-TR-95-49)Item Model Generation and State Generation for Disjunctive Logic Programs(1998-10-15) Seipel, Dietmar; Minker, Jack; Ruiz, CarolinaThis paper investigates two fixpoint approaches for minimal model reasoning with disjunctive logic programs DB. The first one, called model generation [4], is based on an operator TI defined on sets of Herbrand interpretations, whose least fixpoint is logically equivalent to the set of minimal Herbrand models of the program. The second approach, called state generation [12], uses a fixpoint operator TS based on hyperresolution. It operates on disjunctive Herbrand states and its least fixpoint is the set of logical consequences of DB, the so--called minimal model state of the program. We establish a useful relationship between hyperresolution by TS and model generation by TI. Then we investigate the problem of continuity of the two operators TS and TI. It is known that the operator TS is continuous [12], and so it reaches its least fixpoint in at most omega steps. On the other hand, the question of whether TI is continuous has been open. We show by a counterexample that TI is not continuous. Nevertheless, we prove that it converges towards its least fixpoint in at most omega steps too, as follows from the relationship that we show exists between hyperresolution and model generation. We define an iterative version of TI that computes the perfect model semantics of stratified disjunctive logic programs. On each stratum of the program, this operator converges in at most omega steps. Model generations for the stable semantics and the partial stable (and so the well--founded semantics) are respectively achieved by using this iterative operator together with the evidential transformation [3] and the 3-S transformation [16]. (Also cross-referenced as UMIACS-TR-95-99)Item Semantic Query Optimization for Bottom-Up Evaluation(1998-10-15) Godfrey, Parke; Gryz, J.; Minker, JackSemantic query optimization uses semantic knowledge in databases (represented in the form of integrity constraints) to rewrite queries and logic programs for the purpose of more efficient query evaluation. Much work has been done to develop various techniques for optimization. Most of it, however, is only applicable to top-down query evaluation strategies. Moreover, little attention has been paid to the cost of the optimization itself. In this paper, we address the issue of semantic query optimization for bottom-up query evaluation strategies with an emphasis on overall efficiency. We restrict our attention to a single optimization technique, join elimination. We discuss various factors that influence the cost of semantic optimization, and present two abstract algorithms for different optimization approaches. The first one pre-processes a query statically before it is evaluated; the second approach combines query evaluation with semantic optimization using heuristics to achieve the largest possible savings. (Also cross-referenced as UMIACS-TR-95-109)Item Updating Disjunctive Datbases via Model Trees(1998-10-15) Grant, John; Gryz, J.; Minker, JackIn this paper we study the problem of updating disjunctive databases, which contain indefinite data given as positive injunctive closes. We give correct algorithms for the insertion of a clause into and the deletion of a clause from such databases. Although the algorithms presented here are oriented towards model trees, they apply to any representation of minimal models. (Also cross-referenced as UMIACS-TR-95-11)