Computation of stable models and its integration with logical queryprocessing

The well-founded semantics and the stable model semantics capture intuitions of the skeptical and credulous semantics in nonmonotonic reasoning, respectively. They represent the two dominant proposals for the declarative semantics of deductive databases and logic programs. However, neither semantics seems to be suitable for all applications. We have developed an efficient implementation of goal-oriented effective query evaluation under the well-founded semantics. It produces a residual program for subgoals that are relevant to a query, which contains facts for true instances and clauses with body literals for undefined instances. We present a simple method of stable model computation that can be applied to the residual program of a query to derive answers with respect to stable models. The method incorporates both forward and backward chaining to propagate the assumed truth values of ground atoms, and derives multiple stable models through backtracking. Users are able to request that only stable models satisfying certain conditions be computed. A prototype has been developed that provides integrated query evaluation under the well-founded semantics, the stable models, and ordinary Prolog execution. We describe the user interface of the prototype and present some experimental results     

A procedural semantics for stratified database updates

This paper investigates efficient evaluation of database updates and presents a procedural semantics for stratified update programs that extend stratified logic programs with bulk updates and hypothetical reasoning. Bulk rules with universal quantification in the body allow an arbitrary update to be applied simultaneously for every answer of an arbitrary query. Hypothetical reasoning is supported by testing the success or failure of an update. The procedural semantics offers efficient goal-oriented tabled evaluation of database updates. It guarantees termination for function-free stratified update programs and avoids repeated computation of identical subgoals. This revised version was published online in June 2006 with corrections to the Cover Date.     

Why nonmonotonic logic?

The motivation for nonmonotonic logic is to produce a machine representation for default reasoning, broadly construed. In this paper we argue that all nonmonotonic logics have (by definition) inference rules that fail to preserve truth, and this fact leads to several undesirable features. In response to these problems, but recognizing the importance of the original motivation for nonmonotonic logic, we propose an alternative to nonmonotonic logic, which achieves nonmonotonicity of reasoning without abandoning in any way truth preserving inferences. This approach is based on a possible worlds framework, which we illustrate with a small Prolog program. Motivating this approach is an important distinction, which we believe the advocates of nonmonotonic logic to be ignoring: that between inferencing and making decisions, or equivalently that between inferencing and theory construction.     

SLT-Resolution for the Well-Founded Semantics

Global SLS-resolution and SLG-resolution are two representative mechanisms for top-down evaluation of the well-founded semantics of general logic programs. Global SLS-resolution is linear for query evaluation but suffers from infinite loops and redundant computations. In contrast, SLG-resolution resolves infinite loops and redundant computations by means of tabling, but it is not linear. The principal disadvantage of a nonlinear approach is that it cannot be implemented by using a simple, efficient stack-based memory structure nor can it be easily extended to handle some strictly sequential operators such as cuts in Prolog. In this paper, we present a linear tabling method, called SLT-resolution, for top-down evaluation of the well-founded semantics. SLT-resolution is a substantial extension of SLDNF-resolution with tabling. Its main features are the following. First, it resolves infinite loops and redundant computations while preserving the linearity. Second, it is terminating and is sound and complete w.r.t. the well-founded semantics for programs with the bounded-term-size property with nonfloundering queries. Its time complexity is comparable with SLG-resolution and polynomial for function-free logic programs. Third, because of its linearity for query evaluation, SLT-resolution bridges the gap between the well-founded semantics and standard Prolog implementation techniques. It can be implemented by an extension to any existing Prolog abstract machines such as WAM or ATOAM.     

Transformational methodology for proving termination of logic programs

A methodology for proving the termination of well-moded logic programs is developed by reducing the termination problem of logic programs to that of term rewriting systems. A transformation procedure is presented to derive a term rewriting system from a given well-moded logic program such that the termination of the derived rewrite system implies the termination of the logic program for all well-moded queries under a class of selection rules. This facilitates applicability of a vast source of termination orderings proposed in the literature on term rewriting, for proving termination of logic programs. The termination of various benchmark programs has been established with this approach. Unlike other mechanizable approaches, the proposed approach does not require any preprocessing and works well, even in the presence of mutual recursion. The transformation has also been implemented as a front end to Rewrite Rule Laboratory (RRL) and has been used in establishing termination of nontrivial Prolog programs such as a prototype compiler for ProCoS, PL₀ language.     

An application of structural modeling and automated reasoning to real-time systems design

This paper presents an application of structural modeling and automated reasoning as a software development environment for real-time systems. This application satisfies two major requirements for such an environment: (1) to synthesize an absolutely correct program and, (2) to increase software productivity. The real-time systems, which consist of concurrent programs, are described by a Prolog based concurrent object-oriented language, called MENDEL/87. As a typical concurrent program consists of two parts: functional and synchronization parts; the functional part in the reusable component to be registered in a library will be generated by a structural modeling through the use of structuring functions with respect to data flows. The synchronization part will be synthesized from temporal logic specifications by the use of an automated reasoning mechanism. This paper also describes the MENDELS ZONE implemented on a Prolog machine, which is the working base for the presented application method.     

Dynamic reordering of alternatives for definite logic programs

Due to their highly declarative nature and efficiency, tabled logic programming systems have been applied to solving many complex problems. Tabled logic programming is essential for extending traditional logic programming with tabled resolution. In this paper, we propose a new tabled resolution scheme, called dynamic reordering of alternatives (DRA) resolution, for definite logic programs. The scheme keeps track of the type of the subgoals during resolution; if the subgoal in the current resolvent is a variant of a former tabled subgoal, tabled answers are used to resolve the subgoal; otherwise, program clauses are used similar to SLD resolution. Program clauses leading to variant subgoals at runtime are dynamically reordered for further computation until the subgoals are completely evaluated. DRA resolution allows query evaluation to be performed in a depth-first, left-to-right traversal order similar to Prolog-typed SLD resolution, thus yielding a simple technique for incorporating tabled resolution in traditional logic programming systems. We show the correctness of DRA resolution.     

Default logic as a query language

Research in nonmonotonic reasoning has focused largely on the idea of representing knowledge about the world via rules that are generally true but can be defeated. Even if relational databases are nowadays the main tool for storing very large sets of data, the approach of using nonmonotonic AI formalisms as relational database query languages has been investigated to a much smaller extent. In this work, we propose a novel application of Reiter's default logic by introducing a default query language (DQL) for finite relational databases, which is based on default rules. The main result of this paper is that DQL is as expressive as SO_∃∀ the existential-universal fragment of second-order logic. This result is not only of theoretical importance: We exhibit queries-which are useful in practice-that can be expressed with DQL and cannot with other query languages based on nonmonotonic logics such as DATALOG with negation under the stable model semantics. In particular, we show that DQL is well-suited for diagnostic reasoning     

Translating Multi-Agent Autoepistemic Logic into Logic Program

In order to develop a proof procedure of multi-agent autoepistemic Logic (MAEL), a natural framework to formalize belief and reasoning including inheritance, persistence, and causality, we introduce a method that translates a MAEL theory into a logic program with integrity constraints. It is proved that there exists one-to-one correspondence between extensions of a MAEL theory and stable models of a logic program translated from it. Our approach has the following advantages: (1) We can obtain all extensions of a MAEL theory if we compute all stable models of the translated logic program. (2) We can fully use efficient techniques or systems for computing stable models of a logic program. We also investigate the properties of reasoning in MAEL through this translation. The fact that the extension computing problem can be reduced to the stable model computing problem implies that there are close relationships between MAEL and other formalizations of nonmonotonic reasoning.     

The Prolog not-predicate and negation as failure rule

Clark’s query evaluation procedure for computing negative information in deductive databases using a “negation as failure” inference rule requires a safe computation rule which may only select negative literals if they are ground. This is a very restrictive condition, which weakens the usefulness of negation as failure in a query evaluation procedure. This paper studies the definition and properties of the “not” predicate defined in most Prolog systems which do not enforce the above mentioned condition of a safe computation rule. We show that the negation in clauses and the “not” Predicate of Prolog are not the same. In fact a Prolog program may not be in clause form. An extended query evaluation procedure with an extended safe computation rule is proposed to evaluate queries which involve the “not” predicate. The soundness and completeness of this extended query evaluation procedure with respect to a class of logic programs are proved. The implementation of such an extended query evaluation procedure in a Prolog system can be implemented by a preprocessor for executing range restricted programs and requires no modification to the interpreter/compiler of an existing Prolog system. We compare this proposed extended query evaluation procedure with the extended program proposed by Lloyd and Topor, and the negation constructs in NU-Prolog. The use of the “not” predicate for integrity constraint checking in deductive databases is also presented.     

Prology程序部分计算的研究与实现

部分计算是一种重要的程序变换方法和编译优化技术，Prolog程序特别适合于部分计算。目前，国际上已开始了几个Prolog程序部分计算的原理模型和专用工具，但其中存在以下若于问题:(1)关于Prolog程序部分计算的基本原理和特征缺乏系统的认识;(2)现有的两种检测逻辑程序中循环的方法，并没有最后解决部分计算的终止性问题》;(3)关于Prolog中内部谓词的处理不够究善，而且其中还隐含了许多语叉错误;(4)部分计算算法相当低效；(5)现有的部分计算器局限于各自的应用领域，缺乏通用性。本文结合我们研制GKD－Prolog编译系统[14]剖中一个实用源级部分计算器的工作实践，全面、系统地讨论了纯Prolog的部分计算、逻辑程序的循环检测以及全Prolog的内部谓词处理。     

Upside-down meta-interpretation of the model elimination theorem-proving procedure for deduction and abduction

Typical bottom-up, forward-chaining reasoning systems such as hyperresolution lack goaldirectedness, while typical top-down, backward-chaining reasoning systems like Prolog or model elimination repeatedly solve the same goals. Reasoning systems that are goal-directed and avoid repeatedly solving the same goals can be constructed by formulating the top-down methods meta-theoretically for execution by a bottom-up reasoning system (hence, we use the term upside-down meta-interpretation). This formulation also facilitates the use of flexible search strategies, such as merit-ordered search, that are common to bottom-up reasoning systems. The model elimination theorem-proving procedure, its extension by an assumption rule for abduction, and its restriction to Horn clauses are adapted here for such upside-down meta-interpretation. This work can be regarded as an extension of the magic-sets or Alexander method for query evaluation in deductive databases to both non-Horn clauses and abductive reasoning.This research was supported by the National Science Foundation under Grant CCT-8922330 and by the Defense Advanced Research Projects Agency under Office of Naval Research Contract N00014-90-C-0220. The views and conclusions contained herein are those of the author and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the National Science Foundation, the Defense Advanced Research Projects Agency, or the United States Government.     

Mixtus: An automatic partial evaluator for full Prolog

A partial evaluator for Prolog takes a program and a query and return a program specialized for all instances of that query. The intention is that the generated program will execute more efficiently than the original one for those instances. This paper presents “Mixtus”, an automatic partial evaluator forfull Prolog, i.e. including non-logical features such as cut, assert, var, write etc. willautomatically generate a program given only an input program and a query.     

使用选择函数的亚蕴涵询问求值

本提出了使用选择函数的亚蕴涵询问求值方法以及依据此方法建立的询问求值算法ＩＶＡＬ。这种方法比Ｂｏｓｓｕ和Ｓｉｅｇａｌ的算法ＶＡＬ简便，效率高。ＩＶＡＬ和ＶＡＬ同时在ＳＵＮ－４上用Ｃ－Ｐｒｏｌｏｇ语言实现。本给邮了ＩＶＡＬ的理论依据，并把两种算法的执行效果作了比较。     

An application of artificial intelligence to object-orientedperformance design for real-time systems

The paper describes an application of artificial intelligence technology to the implementation of a rapid prototyping method in object-oriented performance design (OOPD) for real-time systems. OOPD consists of two prototyping phases for real-time systems. Each of these phases consists of three steps: prototype construction, prototype execution, and prototype evaluation. We present artificial intelligence based methods and tools to be applied to the individual steps. In the prototype construction step, a rapid construction mechanism using reusable software components is implemented based on planning. In the prototype execution step, a hybrid inference mechanism is used to execute the constructed prototype described in declarative knowledge representation. MENDEL, which is a Prolog based concurrent object-oriented language, can be used as a prototype construction tool and a prototype execution tool. In the prototype evaluation step, an expert system which is based on qualitative reasoning is implemented to detect and diagnose bottlenecks and generate an improvement plan for them     

Graph-Based Parallel Query Processing and Optimization Strategies for Object-Oriented Databases

Much work has been accomplished in the past on the subject of parallel query processing and optimization in parallel relational database systems; however, little work on the same subject has been done in parallel object-oriented database systems. Since the object-oriented view of a database and its processing are quite different from those of a relational system, it can be expected that techniques of parallel query processing and optimization for the latter can be different from the former. In this paper, we present a general framework for parallel object-oriented database systems and several implemented query processing and optimization strategies together with some performance evaluation results. In this work, multiwavefront algorithms are used in query processing to allow a higher degree of parallelism than the traditional tree-based query processing. Four optimization strategies, which are designed specifically for the multiwavefront algorithms and for the optimization of single as well as multiple queries, are introduced. The query processing algorithms and optimization strategies have been implemented on a parallel computer, nCUBE2; and the results of a performance evaluation are presented in this paper. The main emphases and the intended contributions of this paper are (1) data partitioning, query processing and optimization strategies suitable for parallel OODBMSs, (2) the implementation of the multiwavefront algorithms and optimization strategies, and (3) the performance evaluation results.     

Formal Nonmonotonic Theories and Properties of Human Defeasible Reasoning

The knowledge representation and reasoning of both humans and artificial systems often involves conditionals. A conditional connects a consequence which holds given a precondition. It can be easily recognized in natural languages with certain key words, like “if” in English. A vast amount of literature in both fields, both artificial intelligence and psychology, deals with the questions of how such conditionals can be best represented and how these conditionals can model human reasoning. On the other hand, findings in the psychology of reasoning, such as those in the Suppression Task, have led to a paradigm shift from the monotonicity assumptions in human inferences towards nonmonotonic reasoning. Nonmonotonic reasoning is sensitive for information change, that is, inferences are drawn cautiously such that retraction of previous information is not required with the addition of new information. While many formalisms of nonmonotonic reasoning have been proposed in the field of Artificial Intelligence, their capability to model properties of human reasoning has not yet been extensively investigated. In this paper, we analyzed systematically from both a formal and an empirical perspective the power of formal nonmonotonic systems to model (i) possible explicit defeaters, as in the Suppression Task, and (ii) more implicit conditional rules that trigger nonmonotonic reasoning by the keywords in such rules. The results indicated that the classical evaluation for the correctness of inferences has to be extended in the three major aspects (i) regarding the inference system, (ii) the knowledge base, and (iii) possible assumed exceptions for the rule.     

分布式上下文敏感复杂事件处理方法

针对物联网事件云的复杂事件处理面临的海量事件规模、分布式数据处理、上下文相关等挑战,提出一种分布式的上下文敏感复杂事件处理方法。该方法基于模糊本体进行事件上下文的表示和推理,通过查询重写支持事件上下文处理,并基于查询规划和数据划分进行分布式处理与启发式优化。实验结果表明,该方法能够处理模糊事件上下文,对于大规模物联网事件云上下文敏感复杂事件的处理具有比一般方法更好的性能和可伸缩性。     

Handling redundant processing in OBDA query execution over relational sources

Redundant processing is a key problem in the translation of initial queries posed over an ontology into SQL queries, through mappings, as it is performed by ontology-based data access systems. Examples of such processing are duplicate answers obtained during query evaluation, which must finally be discarded, or common expressions evaluated multiple times from different parts of the same complex query. Many optimizations that aim to minimize this problem have been proposed and implemented, mostly based on semantic query optimization techniques, by exploiting ontological axioms and constraints defined in the database schema. However, data operations that introduce redundant processing are still generated in many practical settings, and this is a factor that impacts query execution. In this work we propose a cost-based method for query translation, which starts from an initial result and uses information about redundant processing in order to come up with an equivalent, more efficient translation. The method operates in a number of steps, by relying on certain heuristics indicating that we obtain a more efficient query in each step. Through experimental evaluation using the Ontop system for ontology-based data access, we exhibit the benefits of our method.