Typescript, etc. / Digitized by Kansas Correctional Industries

Thesis (Ph. D.)--University of Texas at Austin, 1999. / Vita. Includes bibliographical references (leaves 152-155) and index. Available also in a digital version from Dissertation Abstracts.

Thesis--Bonn. / Extra t.p. with thesis statement inserted. Includes bibliographical references (p. 39-41).

Thesis--Bonn. / Extra t.p. with thesis statement inserted. Includes bibliographical references (p. 39-41).

Thesis (Ph. D.)--University of Wisconsin--Madison, 1982. / Typescript. Vita. Includes bibliographical references (leaf 145).

Typescript (photocopy). / Digitized by Kansas Correctional Industries

Call number: LD2668 .T4 1985 J63 / Master of Science

In this thesis we propose the use of Dijkstra's concept of a predicate transformer [Dij75] for the determination of database transaction safety [SS89] and the generation of simple conditions to check that a transaction will not violate the integrity constraints in the case that it is not safe. The generation of this simple condition is something that can be done statically, thus providing a mechanism for generating safe transactions. Our approach treats a database as state, a database transaction as a program, and the database's integrity constraints as a postcondition in order to use a predicate transformer [Dij75] to generate a weakest precondition. We begin by introducing a set-oriented update language for relational databases for which a predicate transformer is then defined. Subsequently, we introduce a more powerful update language for deductive databases and define a new predicate transformer to deal with this language and the more powerful integrity constraints that can be expressed using recursive rules. Next we introduce a data model with object-oriented features including methods, inheritance and dynamic overriding. We then extend the predicate transformer to handle these new features. For each of the predicate transformers, we prove that they do indeed generate a weakest precondition for a transaction and the database integrity constraints. However, the weakest precondition generated by a predicate transformer still involves much redundant checking. For several general classes of integrity constraint, including referential integrity and functional dependencies, we prove that the weakest precondition can be substantially further simplified to avoid checking things we already know to be true under the assumption that the database currently satisfies its integrity con-straints. In addition, we propose the use of the predicate transformer in combination with meta-rules that capture the exact incremental change to the database of a particular transaction. This provides a more general approach to generating simple checks for enforcing transaction safety. We show that this approach is superior to known existing previous approaches to the problem of efficient integrity constraint checking and transaction safety for relational, deductive, and deductive object-oriented databases. Finally we demonstrate several further applications of the predicate transformer to the problems of schema constraints, dynamic integrity constraints, and determining the correctness of methods for view updates. We also show how to support transactions embedded in procedural languages such as C.

This work investigates the use of formal logic as a practical tool for describing the syntax and semantics of a subset of English, and building a computer program to answer data base queries expressed in that subset. To achieve an intimate connection between logical descriptions and computer programs, all the descriptions given are in the definite clause subset of the predicate calculus, which is the basis of the programming language Prolog. The logical descriptions run directly as efficient Prolog programs. Three aspects of the use of logic in natural language analysis are covered: formal representation of syntactic rules by means of a grammar formalism based on logic, extraposition grammars;. formal semantics for the chosen English subset, appropriate for data base queries; informal semantic and pragmatic rules to translate analysed sentences into their formal semantics. On these three aspects, the work improves and extends earlier work by Colmerauer and others, where the use of computational logic in language analysis was first introduced.

In this dissertation we prove the Completeness, Soundness and Compactness of the Monadic Hybrid Calculus MHC and we prove its expressive equivalence to the Monadic Predicate Calculus MPC. The Monadic Hybrid Calculus MHC is a new system that is based on the (propositional) modal logic S5. It is “Hybrid” in the sense that it includes quantifier free MPC and therefore, unlike S5, allows free individual constants. The main innovation in this system is the elimination of bound variables. In MHC, upper case letters denote properties and lower case letters denote individuals. Universal quantification is represented by square brackets, [], and existential quantification is represented by angled brackets, 〈〉. Thus, All Athenians are Greek and mortal is formalized as [A](G∧M), Some mortal Greeks are Athenians as 〈M∧G〉A, and Socrates is mortal and Athenian as s(M∧A). We give the formal syntax and the formal semantics of [MHC] and give Beth-style Tableau Rules (Inference Rules). In these rules, if [P]Q is on the right then we select a new constant [v] and we add [vP] on left, vQ on the right, and we cancel the formula. If [P]Q is on the left then we select a pre-used constant p and split the tree. We add pP on the right of one branch and pQ on the left of the other branch. We treat 〈P〉Q similarly. Our Completeness proof uses induction on formulas down a path in the proof tree. Our Soundness proof uses induction up a path. To prove that MPC is logically equivalent to the Monadic Predicate Calculus, we present algorithms that transform formulas back and forth between these two systems. Compactness follows immediately. Finally, we examine the pragmatic usage of the Monadic Hybrid Calculus and we compare it with the Monadic Predicate Calculus using natural language examples. We also examine the novel notions of the Hybrid Predicate Calculus along with their pragmatic implications. / Graduate / 0800 / 0984