Declarative Logic Programming. Michael Kifer
Чтение книги онлайн.
Читать онлайн книгу Declarative Logic Programming - Michael Kifer страница 13
Название: Declarative Logic Programming
Автор: Michael Kifer
Издательство: Ingram
Жанр: Компьютеры: прочее
Серия: ACM Books
isbn: 9781970001983
isbn:
Some authors put an explicit false proposition to the left of the arrow in denial form, to emphasize that satisfaction of the body should be regarded as inconsistency:
Typing information about predicates can also be represented in the same form as integrity constraints. For example, if isPersonID is a unary EDB predicate that contains all IDs of persons (viewing a type as a set of values), then we might require all participants in the ancestor predicate to be people:
or, in denial form,
Denial form for an integrity constrain suggests a direct way of enforcing it: simply execute is as a query and see if it succeeds. In that case, the constraint is violated and the answers to the query are the witnesses of that violation. However, the prospect of enforcing integrity constraints in this manner is not attractive, if it has to be done frequently (such as after each database update). It potentially involves a scan of the whole database, even if only a small part changes. That observation has led to the approaches that target constraint maintenance rather than constraint enforcement. Constraint maintenance assumes that before an update, all constraints are satisfied, so that any violations after the update must be the consequence of the values that were changed [Lloyd et al. 1987]. For example, assume the key constraint on area currently holds, and an update inserts the fact area(ss, 'Systems Science'). Then any violation of
must involve that new fact. The integrity constraint can be “reduced” [Martinenghi et al. 2006] by matching the new fact with the first subgoal, leaving
This clause is much quicker to check, especially if there is an index on area. Similarly, for the integrity constraint on ancestor, if we inserted advised(kr, jf), then we would only need to check whether
can be established or not.
There have been a range of constraint-maintenance approaches for logic languages, including forward-chaining updates to try to establish denials [Kowalski et al. 1987] and translating integrity constraints to SQL triggers on the EDB relations [Decker 1986]. Other methods are discussed in the survey by Martinenghi et al. [2006].
Constraint maintenance can still involve significant computation, especially for constraints on IDB predicates. For certain constraints, it may be possible to show statically that they must hold if other constraints are enforced. A particular situation where this approach is valuable (and generally feasible) is to show that typing constraints on IDB predicates hold if such constraints on EDB predicates are enforced. For example, for the typing constraint
on the EDB relation advised can be used to establish the typing constraint
essentially by proving a theorem on the IDB predicate ancestor. Richer type systems, including features such as subtyping and mutual exclusion, can also be statically checked [Reiter 1981]. However, there is a trade-off between the speed of checking and the completeness of the method [Zook et al. 2009]. There are other classes of constraints where the consistency of the IDB can be proved from the consistency of the EDB. For example, Wang and Yuan [1992] give a method for handling downward closed constraints—constraints that are preserved if tuples are removed from a predicate, such as functional dependencies.
Typing and constraints, as noted, can help prevent data corruption and programming errors, but they can also improve performance. In terms of low-level implementation, knowing the type of an argument, such as Integer, permits a specialized representation, and avoids checks for handling other possibilities. At a higher level, there is a long history of using constraints for semantic query optimization: rewriting queries into simpler or more efficient forms, based on constraints that hold. For example, Chakravarthy et al. [1990] introduce a method of residues that can variously remove redundant literals from a query or include additional ones that are more restrictive. Residues are produced by matching parts of an integrity constraint to subgoals in a rule. The unmatched part of the constraint (the residue) is attached to the rule and used during query evaluation. For example, consider the following rule for possible dissertation committee chairs for a student:
which says the possible chairs for a student are the tenured professors appointed in the department where the student is enrolled. If there is an integrity constraint
that says an adjunct professor cannot be tenured, then the residue of the constraint relative to the rule is
This residue could be used to simplify the query
by removing the second literal (if there is only one rule for possibleChair). Lee and Han [1988] adapted the residue method to handle recursive queries, and Lakshmanan and Missaoui [1992] focused on semantic query optimization for inclusion and context dependencies. (A context dependency is an extension of an inclusion dependency that involves algebraic expressions and not just individual relations.) Sagiv [1987] incorporates tuple-generating dependencies (such as multi-valued and join dependencies) into testing containment of Datalog programs, which thereby extends the earlier methods for query optimization [Johnson and Klug 1984]. (See Section 1.5.5 for the role of containment in optimization.) Levy and Sagiv [1995] look at optimizing recursive programs, using integrity constraints to avoid rule applications that will necessarily have empty results, as well as augmenting rules with additional restrictions.
1.4.6 Object-Oriented Logic Programming
Extending Datalog and Logic Programming in general with object-oriented features has been an active area in database and logic programming research since the late 1980s, and the most influential systems were developed in the 1990s and 2000s. Two main approaches can be identified among the variety of works on this subject.
The first can be called object-oriented Prolog or OOP. That approach takes Prolog, with its procedural semantics and extra-logical predicates, and adds the syntactic constructs to represent objects, classes, and so forth. The main idea is support for object-oriented programming in Prolog, rather than to develop new logical theories for a combination of these two paradigms. Prolog++ [Moss 1994] and SICStus [Carlsson et al. 2015] took this approach in the 1990s and more recently Jinni [Tarau 2004] СКАЧАТЬ