Appropriate inferences of data dependencies in relational databases

We study inference systems for the combined class of functional and full hierarchical dependencies in relational databases. Two notions of implication are considered: the original notion in which a dependency is implied by a given set of dependencies and the underlying set of attributes, and the alternative notion in which a dependency is implied by a given set of dependencies alone. The first main result establishes a finite axiomatisation for the original notion of implication which clarifies the role of the complementation rule in the combined setting. In fact, we identify inference systems that are appropriate in the following sense: full hierarchical dependencies can be inferred without use of the complementation rule at all or with a single application of the complementation rule at the final step of the inference only; and functional dependencies can be inferred without any application of the complementation rule. The second main result establishes a finite axiomatisation for the alternative notion of implication. We further show how inferences of full hierarchical dependencies can be simulated by inferences of multivalued dependencies, and vice versa. This enables us to apply both of our main results to the combined class of functional and multivalued dependencies. Furthermore, we establish a novel axiomatisation for the class of non-trivial functional dependencies.     

Incorporating top-down information into bottom-up hypothetical reasoning

Both bottom-up and top-down approaches have been presented for hypothetical reasoning. However, both have merits and demerits, which are complementary. Thus, hypothetical reasoners combining those approaches are promising. Here, we concern about a bottom-up hypothetical reasoner incorporating top-down information. In order to simulate top-down reasoning on bottom-up reasoners, we can apply the upside-down meta-interpretation method, which is similar to Magic Set and Alexander methods, by transforming a set of Horn clauses into a program incorporating goal information. Unfortunately, it does not achieve speedups for bottom-up hypothetical reasoning because checking consistencies of solutions by negative clauses should be globally evaluated. This paper presents a new method to reduce the consistency checking cost for bottom-up hypothetical reasoning based on the upside-down meta-interpretation. In the transformation algorithm, logical dependencies between a goal and negative clauses are analyzed to find irrelevant negative clauses, so that bottom-up hypothetical reasoning based on the upside-down meta-interpretation can restrict consistency checking of negative clauses to those relevant clauses.     

A sound and complete chase procedure for constrained tuple-generating dependencies

We present a chase procedure for solving the implication problem of constrained tuple-generating dependencies (ctgds), a general class of database dependencies that is also able to handle data and predicates on interpreted domains. Current chase procedures for ctgds are sound but not complete, in the sense that they are unguaranteed to stop successfully whenever implication is true. The procedure we present is sound and complete, the first to our knowledge. It follows a linear reasoning over constraint domains that have the Independence of Negative Constraints property. We then soundly extend this procedure by a disjunctive reasoning over unrestricted constraint domains. To achieve these results, we used a different approach. Previous chases act like a closure operator, whereas we used a goal-directed design.     

Characterisations of multivalued dependency implication over undetermined universes

In relational databases the original definition of a multivalued dependency is dependent on the underlying relation schema. In this context, the implication of multivalued dependencies has been characterised from multiple perspectives. Logically, it is equivalent to the logical implication of certain material implications in Boolean propositional logic. Proof-theoretically, the Chase procedure offers a convenient tool to decide implication. And algebraically, the implication can be characterised by the notion of closed attribute sets with respect to multivalued dependencies. The assumption of having a fixed underlying relation schema is not always feasible in practice, and also distinguishes multivalued dependencies from other classes of data dependencies. In this paper, we establish logical, proof-theoretical and algebraic characterisations for Biskup?s notion of multivalued dependency implication over undetermined universes. That is, we unburden the current theory of the assumption of having a fixed underlying relation schema. From the perspective of probability theory this means that is unnecessary to fix the set of discrete probabilistic variables in order to utilise conditional independencies.     

On the Undecidability of Implications between Embedded Multivalued Database Dependencies

The implication and finite implication problems for embedded multivalued database dependencies are both shown to be algorithmically undecidable. The proof is by an interpretation of semigroup word problems via systems of permuting equivalence relations into database dependencies. In contrast, it is shown that for each fixed premise H one has a decision procedure for implications H F.     

Digital media adoption in schools: Bottom-up,top-down,complementary or optional?

Past research has suggested that innovation processes in schools are more successful when they are participatory and voluntary. To examine this notion, we categorized schools into one of four different innovation-process types, based on group interviews with school staff: complementary bottom-up and top-down development (type 1), top-down development that is not supported bottom-up (type 2), bottom-up development that is not supported top-down (type 3) and optional development with neither strong bottom-up nor top-down initiatives (type 4). Based on this typology, analysis of variance was then conducted on survey response data from 357 teachers and 1051 9th grade students from these schools. In contrast with some of our expectations, we found that teachers in schools with a complementary top-down and bottom-up strategy as well as schools with a top-down strategy only showed better ICT-resources and a more intensive use of educational technology than those in bottom-up- or optional-innovation-type schools. Additionally, teachers' ICT-use in type 1 and 2 schools is predicted to a higher degree by the number of computers in the classroom than in schools where ICT-integration is bottom-up or optional. Our findings suggest that bottom-up innovation strategies are likely to fall short without top-down support, especially when funds for technology installations are missing.     

Arguments and Misunderstandings: Fuzzy Unification for Negotiating Agents

In this paper, we develop the notion of fuzzy unification and incorporate it into a novel fuzzy argumentation framework for extended logic programming. We make the following contributions: The argumentation framework is defined by a declarative bottom-up fixpoint semantics and an equivalent goal-directed top-down proofprocedure for extended logic programming. Our framework allows one to represent positive and explicitly negative knowledge, as well as uncertainty. Both concepts are used in agent communication languages such as KQML and FIPA ACL. One source of uncertainty in open systems stems from mismatches in parameter and predicate names and missing parameters. To this end, we conservatively extend classical unification and develop fuzzy unification based on normalised edit distance over trees.     

On goal-directed provability in classical logic

One of the key features of logic programming is the notion of goal-directed provability. In intuitionistic logic, the notion of uniform proof has been used as a proof-theoretic characterization of this property. Whilst the connections between intuitionistic logic and computation are well known, there is no reason per se why a similar notion cannot be given in classical logic. In this paper we show that there are two notions of goal-directed proof in classical logic, both of which are suitably weaker than that for intuitionistic logic. We show the completeness of this class of proofs for certain fragments, which thus form logic programming languages. As there are more possible variations on the notion of goal-directed provability in classical logic, there is a greater diversity of classical logic programming languages than intuitionistic ones. In particular, we show how logic programs may contain disjunctions in this setting. This provides a proof-theoretic basis for disjunctive logic programs, as well as characterising the “disjunctive” nature of answer substitutions for such programs in terms of the provability properties of the classical connectives Λ and Λ.     

A semi-dependent decomposition approach to learn hierarchical classifiers

In hierarchical classification, classes are arranged in a hierarchy represented by a tree or a forest, and each example is labeled with a set of classes located on paths from roots to leaves or internal nodes. In other words, both multiple and partial paths are allowed. A straightforward approach to learn a hierarchical classifier, usually used as a baseline method, consists in learning one binary classifier for each node of the hierarchy; the hierarchical classifier is then obtained using a top-down evaluation procedure. The main drawback of this naive approach is that these binary classifiers are constructed independently, when it is clear that there are dependencies between them that are motivated by the hierarchy and the evaluation procedure employed. In this paper, we present a new decomposition method in which each node classifier is built taking into account other classifiers, its descendants, and the loss function used to measure the goodness of hierarchical classifiers. Following a bottom-up learning strategy, the idea is to optimize the loss function at every subtree assuming that all classifiers are known except the one at the root. Experimental results show that the proposed approach has accuracies comparable to state-of-the-art hierarchical algorithms and is better than the naive baseline method described above. Moreover, the benefits of our proposal include the possibility of parallel implementations, as well as the use of all available well-known techniques to tune binary classification SVMs.     

Learning to Combine Bottom-Up and Top-Down Segmentation

Bottom-up segmentation based only on low-level cues is a notoriously difficult problem. This difficulty has lead to recent top-down segmentation algorithms that are based on class-specific image information. Despite the success of top-down algorithms, they often give coarse segmentations that can be significantly refined using low-level cues. This raises the question of how to combine both top-down and bottom-up cues in a principled manner. In this paper we approach this problem using supervised learning. Given a training set of ground truth segmentations we train a fragment-based segmentation algorithm which takes into account both bottom-up and top-down cues simultaneously, in contrast to most existing algorithms which train top-down and bottom-up modules separately. We formulate the problem in the framework of Conditional Random Fields (CRF) and derive a feature induction algorithm for CRF, which allows us to efficiently search over thousands of candidate fragments. Whereas pure top-down algorithms often require hundreds of fragments, our simultaneous learning procedure yields algorithms with a handful of fragments that are combined with low-level cues to efficiently compute high quality segmentations.     

Full hierarchical dependencies in fixed and undetermined universes

Full hierarchical dependencies (FHDs) constitute a large class of relational dependencies. A relation exhibits an FHD precisely when it is the natural join over at least two of its projections that all share the same join attributes. Therefore, FHDs generalise multivalued dependencies (MVDs) in which case the number of these projections is precisely two. The implication of FHDs has originally been defined in the context of some fixed finite universe. This paper identifies a sound and complete set of inference rules for the implication of FHDs. This axiomatisation is very reminiscent of that for MVDs. Then, an alternative notion of FHD implication is introduced in which the underlying set of attributes is left undetermined. The first main result establishes a finite axiomatisation for FHD implication in undetermined universes. It is then formally clarified that the complementation rule is only a mere means for database normalisation. In fact, the second main result establishes a finite axiomatisation for FHD implication in fixed universes which allows to infer FHDs either without using the complementation rule at all or only in the very last step of the inference. This also characterises the expressiveness of an incomplete set of inference rules in fixed universes. The results extend previous work on MVDs by Biskup.     

Duality for Goal-Driven Query Processing in Disjunctive Deductive Databases

Bottom-up query-answering procedures tend to explore a much larger search space than what is strictly needed. Top-down processing methods use the query to perform a more focused search that can result in more efficient query answering. Given a disjunctive deductive database, DB, and a query, Q, we establish a strong connection between model generation and clause derivability in two different representations of DB and Q. This allows us to use a bottom-up procedure for evaluating Q against DB in a top-down fashion. The approach requires no extensive rewriting of the input theory and introduces no new predicates. Rather, it is based on a certain duality principle for interpreting logical connectives. The duality transformation is achieved by reversing the direction of implication arrows in the clauses representing both the theory and the negation of the query. The application of a generic bottom-up procedure to the transformed clause set results in top-down query answering. Under favorable conditions efficiency gains are substantial, as shown by our preliminary testing. We give the logical meaning of the duality transformation and point to the conditions and sources of improved efficiency. We show how the duality approach can be used for refined query answering by specifying the minimal conditions (weakest updates) to DB under which Q becomes derivable. This is shown to be useful for view updates in disjunctive deductive databases as well as for other interesting applications.     

Charting the completeness frontier of inference systems for multivalued dependencies

The implication of multivalued dependencies in relational databases has originally been defined in the context of some fixed finite universe. While axiomatisability and implication problems have been intensely studied with respect to this notion almost no research has been devoted towards the alternative notion of implication in which the underlying universe of attributes is left undetermined. Based on a set of common inference rules we establish all axiomatisations in undetermined universes, and all axiomatisations in fixed universes that indicate the role of the complementation rule as a means of database normalisation. This characterises the expressiveness of several incomplete sets of inference rules. We also establish relationships between axiomatisations in fixed and undetermined universes, and study the time complexity of the implication problem in undetermined universes. The results of this paper establish a foundation for reasoning about multivalued dependencies without the assumption of a fixed underlying universe.     

Proof Pearl: A Formal Proof of Dally and Seitz’ Necessary and Sufficient Condition for Deadlock-Free Routing in Interconnection Networks

Avoiding deadlock is crucial to interconnection networks. In ’87, Dally and Seitz proposed a necessary and sufficient condition for deadlock-free routing. This condition states that a routing function is deadlock-free if and only if its channel dependency graph is acyclic. We formally define and prove a slightly different condition from which the original condition of Dally and Seitz can be derived. Dally and Seitz prove that a deadlock situation induces cyclic dependencies by reductio ad absurdum. In contrast we introduce the notion of a waiting graph from which we explicitly construct a cyclic dependency from a deadlock situation. Moreover, our proof is structured in such a way that it only depends on a small set of proof obligations associated to arbitrary routing functions and switching policies. Discharging these proof obligations is sufficient to instantiate our condition for deadlock-free routing on particular networks. Our condition and its proof have been formalized using the ACL2 theorem proving system.     

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.     

The Neutrality of Money Revisited with a Bottom-Up Approach: Decentralisation,Limited Information and Bounded Rationality

In the mainstream top-down approach, money is neutral except with special assumptions. Intending to make money “essential”, random-matching models introduced decentralisation by considering pair-wise transactions. Nevertheless, in both cases top-level equilibrium constrains agents’ behaviour. Instead, here we use a bottom-up approach. In a competitive market, decentralised autonomous agents meet and exchange a commodity for money. Their decisions use minimal information. They are triggered by simple rules founded on a “satisficing” procedure and on a random decision process that simulates bounded rationality. The conclusions are, first, that non-monetary costs are essential to avoid collapse of the economy. Second, mainly “price setters” who are adequately satisfied achieve equilibrium protecting themselves by evolving advantages to avoid competition that is too tough. Third, and the most important conclusion is that money ceases to be neutral as soon as competition arises between individual firms.     

Combined top-down/bottom-up segmentation

We construct a segmentation scheme that combines top-down with bottom-up processing. In the proposed scheme, segmentation and recognition are intertwined rather than proceeding in a serial manner. The top-down part applies stored knowledge about object shapes acquired through learning, whereas the bottom-up part creates a hierarchy of segmented regions based on uniformity criteria. Beginning with unsegmented training examples of class and non-class images, the algorithm constructs a bank of class-specific fragments and determines their figure-ground segmentation. This bank is then used to segment novel images in a top-down manner: the fragments are first used to recognize images containing class objects, and then to create a complete cover that best approximates these objects. The resulting segmentation is then integrated with bottom-up multi-scale grouping to better delineate the object boundaries. Our experiments, applied to a large set of four classes (horses, pedestrians, cars, faces), demonstrate segmentation results that surpass those achieved by previous top-down or bottom-up schemes. The main novel aspects of this work are the fragment learning phase, which efficiently learns the figure-ground labeling of segmentation fragments, even in training sets with high object and background variability; combining the top-down segmentation with bottom-up criteria to draw on their relative merits; and the use of segmentation to improve recognition.     

General <Emphasis Type="Italic">E</Emphasis>-unification with Eager Variable Elimination and a Nice Cycle Rule

We present a goal-directed E-unification procedure with eager Variable Elimination and a new rule, Cycle, for the case of collapsing equations – that is, equations of the type x ≈ v where x ∈Var(v). Cycle replaces Variable Decomposition (or the so-called Root Imitation) and thus removes possibility of some obviously unnecessary infinite paths of inferences in the E-unification procedure. We prove that, as in other approaches, such inferences into variable positions in our goal-directed procedure are not needed. Our system is independent of selection rule and complete for any E-unification problem.     

The implication problem for ‘closest node’ functional dependencies in complete XML documents

With the growing use of XML as a format for the permanent storage of data, the study of functional dependencies in XML (XFDs) is of fundamental importance in a number of areas such as understanding how to effectively design XML databases without redundancy or update problems, and data integration. In this article we investigate a particular type of XFD, called a weak ‘closest node’ XFD, that has been shown to extend the classical notion of a functional dependency in relational databases. More specifically, we investigate the implication problem for weak ‘closest node’ XFDs in the context of XML documents with no missing information. The implication problem is the most important one in dependency theory, and is the problem of determining if a set of dependencies logically implies another dependency. Our first, and main, contribution is to provide an axiom system for XFD implication. We prove that our axiom system is both sound and complete, and we then use this result to develop a sound and complete quadratic time closure algorithm for XFD implication. Our second contribution is to investigate the implication problem for XFDs in the presence of a Document Type Definition (DTD). We show that for a class of DTDs called structured DTDs, the implication problem for a set of XFDs and a structured DTD can be converted to the implication problem for a set of XFDs alone, and so is axiomatizable and efficiently solvable by the first contribution. We do this by augmenting the original set of XFDs with additional XFDs generated from the structure of the DTD.     

An algebraic theory of functional and multivalued dependencies in relational databases

Computation of the dependency basis is the fundamental step in solving the membership problem for functional dependencies (FDs) and multivalued dependencies (MVDs) in relational database theory. We examine this problem from an algebraic perspective. We introduce the notion of the inference basis of a set M of MVDs and show that it contains the maximum information about the logical consequences of M. We propose the notion of a dependency-lattice and develop an algebraic characterization of inference basis using simple notions from lattice theory. We also establish several interesting properties of dependency-lattices related to the implication problem. Founded on our characterization, we synthesize efficient algorithms for (a): computing the inference basis of a given set M of MVDs; (b): computing the dependency basis of a given attribute set w.r.t. M; and (c): solving the membership problem for MVDs. We also show that our results naturally extend to incorporate FDs also in a way that enables the solution of the membership problem for both FDs and MVDs put together. We finally show that our algorithms are more efficient than existing ones, when used to solve what we term the ‘generalized membership problem’.