We present a full system integration of a thermoelectric energy harvesting system as an on-chip component into a 3D IC. Our system incorporates a lithographically patterned bi-metallic thin-film thermocouple network with a switched capacitor power converter and a charge buffer capacitor to harvest thermal energy produced by temperature gradients in typical 3D IC structures. Through heat transfer and transistor-level circuit simulations we demonstrate the energy harvesting potential of our system to power a low energy circuit component. Our proposed thin film based harvester does not require package re-design, since it is integrated on-chip using low cost CMOS compatible material. We evaluated integration of our proposed system into a 3D stacking of processor cores and DRAM memory. Even when operating at a conservative thermal bound of 84°C sufficient energy is harvested to continuously sustain a low-power adder for 29,640 cycles of single bit additions or 463 cycles of 64-bit additions with 12usec charging delay. Effectively we can run the adder continuously with less than 0.80% delay between bursts of operations.

With the explosive growth of the size of databases, many knowledge discovery applications deal with large quantities of data. There is an urgent need to develop methodologies which will allow the applications to focus search to a potentially interesting and relevant portion of the data, which can reduce the computational complexity of the knowledge discovery process and improve the interestingness of discovered knowledge. Previous work on semantic query optimization, which is an approach to take advantage of domain knowledge for query optimization, has demonstrated that significant cost reduction can be achieved by reformulating a query into a less expensive yet equivalent query which produces the same answer as the original one. In this paper, we introduce a method to utilize three types of domain knowledge in reducing the cost of finding a potentially interesting and relevant portion of the data while improving the quality of discovered knowledge. In addition, we propose a method to select relevant domain knowledge without an exhaustive search of all domain knowledge. The contribution of this paper is that we lay out a general framework for using domain knowledge in the knowledge discovery process effectively by providing guidelines.

We motivate and define subimplication completion of a relational calculus query and of a general deductive database. Subimplication completion not only avoids getting unexpected answers, but also makes some domain dependent queries and databases domain independent. We define a new recursive subclass of domain independent formulas, called weakly range-restricted formulas, which is strictly larger than the class of range-restricted formulas. We also define admissible and deductive databases and show that under the subimplication completion they are domain independent and safe.>

In order to extend the expressive power of deductive databases, a formula that can have existential quantifiers in prenex normal form in a restricted way is defined as an extended rule. With the extended rule, we can easily define a virtual view that requires a division operation of relational algebra to evaluate. The paper addresses a recursive query evaluation where at least one formula in a recursive rule set is of an extended rule. We investigate transformable recursions as well as four cases of non-transformable recursions of transitive-closure-like and linear type. The work reveals that occurrence of an existentially quantified variable in the extended recursive body predicate might dramatically limit the level of recursive search. In particular, the number of iterations to answer extended queries can be determined, independently of database contents.>

The paper describes an object-oriented system that smoothly integrates procedural function invocation and declarative rule reasoning into a single homogeneous system. This allows efficient computations expressed as external functions to be incorporated into rule systems to improve computational efficiency and extensibility of intelligent systems. We first discuss the differences between declarative rules and procedural functions. We then describe an object-oriented model that incorporates both of these. The model has a translation phase and an execution phase. We also discuss problems arising from the different ways that data are represented (terms in rules vs. data objects in functions), from the existence of user-defined types in functions and the necessary argumentations to the unification process in the rule system.>

We introduce an inference scheme, based on the compilation approach, that can answer "true," provable-false," "indefinite," or "assumable-false" to a closed query in an indefinite deductive database under the generalized closed world assumption. The inference scheme proposed in this paper consists of a representation scheme and an evaluation process that uses one of two groups of positive indefinite ground clauses (PIGC's) derivable from the database for a given query. These two groups of PIGC's are base-PIGC's and descendants of base-PIGC's. We prove that the set of base-PIGC's derivable from the database is sufficient to infer the indefiniteness of a query. This newly proposed method offers many advantages over the existing compilation method. This new method outperforms the existing one in terms of the cost of compilation, ease in the handling of updates, and efficiency in query evaluation.>

The authors address an enforcement technique of integrity constraints against transaction updates in a relational database system. Transition axioms have been used effectively in checking integrity constraints for single update statements. The authors extend the idea of transition axioms to a transaction which is a sequence of read and update statements. Integrity constraints in this scheme are simplified without database access before the actual operations are performed avoiding the need to undo an illegal transaction. Transaction partitioning, which can reduce the overhead of checking integrity constraints significantly, is proposed. Partitioning a transaction becomes crucial when a transaction is associated with multiple integrity constraints.>

The use of negative information and the unrestricted use of quantifiers in the body of a rule enhances the expressive power of deductive database systems. The authors introduce a more relaxed version of conventional (Skolem) function-free databases, called acceptable databases which generalize the class of allowed databases by accepting occurrences of universal quantifiers for variables occurring in positive literals and existential quantifiers for variables occurring in negative literals in the body of an IDB rule. The compilation technique suitable for compiling acceptable IDB rules based on the substitution rule is addressed. They show the correctness of the substitution-based compilation by proving completeness and soundness of the substitution rule.>

Real-time logic (RTL) has been successful in specifying and verifying a class of timing requirements in real-time systems. The authors propose a graph proof procedure for RTL formulae. First, they represent the RTL formulae in a connection graph-like structure. Based on this graph, they have found some useful deduction rules and reduction rules. From some preliminary experiments, they show that their proof procedure is very efficient.>

Because of increasing needs and requirements for the use of databases, one always looks for more efficient ways to handle database access. Parallel computing environments draw more attention to achieve the high processing speed and the less expensive processing method. This paper proposes the possibility of using a connectionist model by treating every datum as an active processing unit cooperating with other such units via messages in getting answers in a deductive database, especially with recursion. It uses query compilation and iteration to process the recursive case. The notion of the reverse-compilation which is essential to get the correct answers is introduced in handling recursive cases. It introduces the recursive controller which is dedicated to processing the recursive cases as a sublayer to a central database controller.>

The authors present a graph model which is powerful in classifying and compiling linear recursive formulas in deductive databases. The graph model consists of two kinds of graphs: I-graph and resolution graph. Essential properties of a recursive formula can be extracted from its I-graph, and the compiled formula and the query evaluation plan of the recursive formulas can be determined from its resolution graph. It is demonstrated that based on the graph model all the linear recursive formulas can be classified into a taxonomy of classes and each class shares common characteristics in query compilation and query processing. The compiled formulas and the corresponding query evaluation plans can be derived based on the study of the compilation of each class.>

An algorithm is presented for transforming a mutual recursive program in Prolog, which contains the list data structure as a term of the predicate, into an iterative program using a while loop in a procedural language like PASCAL. The purpose of this study is a part of the long-range project to use general logic programming as a software specification tool. The PASCAL program generated by the algorithm obtains the same result as the Prolog program, but without unification and backtracking. In this algorithm the recursive programs are classified into two cases, the determined programs and the undetermined programs, according to the conditions of the variables in the program. The unification process is transformed into a set of assignment and conditional statements by analyzing the variables of the rules in the program.>

A method is proposed for identifying relevant integrity constraints (ICs) for queries involving joins/unions of base relations and defined relations by use of graphs. The method does not rely on heavy preprocessing or redundancy. To effectively select those ICs that are relevant to a given query, the relationship between the predicates in the query is identified using an AND/OR tree where an AND mode represents a join operation and an OR node represents a union operation. Ways of collecting ICs are described that are not directly related to the query but can be useful in query optimization.>

The performances of several algorithms suitable for processing an important class of recursive queries called the instantiated transitive closure (TC) queries are studied and compared. These algorithms are the wavefront, delta -wavefront, and a generic algorithm called super-TC. During the evaluation of a TC query, the first two algorithms may read a given disk page more than once, whereas super-TC reads the disk page at most once. A comprehensive performance evaluation of these three algorithms using rigorous analytical and simulation models is presented. The study reveals that the relative performance of the algorithms is a strong function of the parameters which characterize the processed TC query and the relation referenced by that query. The superiority of one of the super-TC variants over all of the other presented algorithms is shown.>

The authors present an algorithm for transforming a linear recursive program in Prolog which contains the list data structure as a term of the predicate into an iterative program using a while loop in a procedural language like Pascal. This algorithm obtains the same result as Prolog without unification and backtracking. In this algorithm, the recursive programs are classified into two cases, the determined programs and the undetermined programs, according to the conditions of the variables in the program. The unification process is transformed into the set of assignment and conditional statements by analyzing the variables of the rules in the program. Backtracking is accomplished by a traversal of a tree whose nodes contain instantiated predicates.>

If a relational database is required to satisfy a set of integrity constraints, then when the database is updated, one must ensure that it continues to satisfy the constraints. It is desirable not to have to evaluate each constraint after each update. A method is described that takes a constraint C and a class of updates, and either proves that an update in the class cannot violate C , or produces a formula C' (a complete test) that is satisfied before the update if and only if C would continue to be satisfied were the update to occur. C' is frequently much easier to evaluate than C . In addition, a formula D (a sufficient test) is sometimes produced such that if D is satisfied before the update, then C would continue to be satisfied were the update to occur. The method is proved correct. The method is substantially more general than other reported techniques for this problem. The method has been implemented, and a number of experiments with the implementation are presented.

The chase procedure, for determining if a given dependency must hold in any relation where a set of dependencies is known to hold, operates bottom-up by constructing a hypothetical relation know as a tableau. A top-down counterpart, based on resolution theorem proving techniques, is introduced in which, through factoring, resolvents which contain function terms may be avoided. A literal numbering technique, which limits the number of resolvents, is also examined.

Redundancy may exist in the processing of recursive database queries at four different levels precompilation level, iteration level, tuple processing level and file accessing level. Techniques for reducing redundant work at each level are studied. In the precompilation level, the optimization techniques include removing redundant parts in a rule cluster, simplifying recursive clusters and sharing common subexpressions among rules. At the iteration level, the techniques discussed are the use of frontier relations and the counting method. At the tuple processing level, we use merging and filtering methods to exclude processed drivers from database reaccessing. Finally, at the file accessing level, I/O cost can be further reduced by level relaxation. We conclude that even for complex recursion, redundant database processing can be considerably reduced or eliminated by developing appropriate algorithms.

A first-order database ~s defined as a function-free first-order theory in which the ground units serve as the extensional database and the proper noniogical axioms serve as the intensional database.The following problem is addressed: "Given a recurswe nonlogical axiom and the form of a potential query, can one describe a set of database retrieval requests that gives the correct answers and is guaranteed to terminate."The solution uses resolution-proof techmques over connection graphs to derive a program of relational database operations that gives all the answers to a query and has a welldefined termmatton condiUon.

This paper presents a reformulation of Gilmore's approach Rather than generate instances by saturation, the authors start with a few instances, convert to a nonredundant disjunctive normal form (DNF), and then use that DNF to help grade the choice of further instances The DNF in essence represents m a convenient form all the Boolean relations of the hteral instances Viewed differently, the DNF provides a concise description of clauses which, ffadded, would produce unsatlsfiablhty Thus the mare activity in the theorem-proving process Js analyzing possible new instances of input clauses and their relationship to the already present instances Some examples from an interactive program are given

Automated theorem proving involves the programming of computers to perform logical (mathematical) deduction. This should not be confused with numerical calculation, in which operations that need to be performed can be exactly specified ahead of time as, for example, in Gaussian elimination. Rather, theorem provers search for proofs of statements given axioms describing the basic assumptions such as would occur in a modern algebra text on group theory. There are many theorem-proving programs that are based on ad hoc data representations and manipulations;many such techniques are derived by the programmer analyzing how he himself proves theorems. However, the most widely studied and best understood general method is based on the resolution principle for first-order logic of Robinson [9]. Indeed, all the papers in this issue have resolution as a starting point.

A new resolution strategy for Horn sets of clauses, each clause of which contains no more-than one positive literal, is presented which requires that in each resolution either one ancestor be a false positive unit or that one ancestor and the resolvent both be false. This strategy emphasizes "relevant" positive units while controlling the explosive nonunit resolution. Some properties of interpretations for Horn sets are reviewed and used to significantly reduce the computation and storage required to implement semantic resolution for Horn sets.

The key concepts for this automated theorem-proving paper are those of Horn set and strictly-unit refutation. A Horn set is a set of clauses such that none of its members contains more than one positive literal. A strictly-unit refutation is a proof by contradiction in which no step is justified by applying a rule of inference to a set of clauses all of which contain more than one literal. Horn sets occur in many fields of mathematics such as the theory of groups, rings, Moufang loops, and Henkin models. The usual translation into first-order predicate calculus of the axioms of these and many other fields yields a set of Horn clauses. The striking feature of the Horn property for finite sets of clauses is that its presence or absence can be determined by inspection. Thus, the determination of the applicability of the theorems and procedures of this paper is immediate. In Theorem 1 it is proved that, if S is an unsatisfiable Horn set, there exists a strictly-unit refutation of S employing binary resolution alone, thus eliminating the need for factoring; moreover, one of the immediate ancestors of each step of the refutation is in fact a positive unit clause. A theorem similar to Theorem 1 for paramodulation-based inference systems is proven in Theorem 3 but with the inclusion of factoring as an inference rule. In Section 3 two reduction procedures are discussed. For the first, Chang's splitting, a rule is provided to guide both the choice of clauses and the way in which to split. The second reduction procedure enables one to refute a Horn set by refuting but one of a corresponding family of simpler subproblems.