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’.

The Implication Problem for Functional and Multivalued Dependencies

Computation of the dependency basis is the fundamental step in solving the implication problem for 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 an MVD-lattice and develop an algebraic characterization of the inference basis using simple notions from lattice theory. We also establish several properties of MVD-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 implication problem for MVDs. Finally, we show that our results naturally extend to incorporate FDs also in a way that enables the solution of the implication problem for both FDs and MVDs put together.

Split-Freedom And Mvd-Intersection - A New Characterization Of Multivalued Dependencies Having Conflict-Free Covers

Sets of multivalued dependencies (MVDs) having conflict-free covers are important to the theory and design of relational databases [2,12,15,16]. Their desirable properties motivate the problem of testing a set M of MVDs for the existence of a confiict-free cover. In [8] Goodman and Tay have proposed an approach based on the possible equivalence of M to a single (acyclic) join dependency (JD). We remark that their characterization does not lend an insight into the nature of such sets of MVDs. Here, we use notions that are intrinsic to MVDs to develop a new characterization. Our approach proceeds in two stages. In the first stage, we use the notion of “split-free” sets of MVDs and obtain a characterization of sets M of MVDs having split-free covers. In the second, we use the notion of “intersection” of MVDs to arrive at a necessary and sufficient condition for a split-free set of MVDs to be conflict-free. Based on our characterizations, we also give polynomial-time algorithms for testing whether M has split-free and conflict-free covers. The highlight of our approach is the clear insight it provides into the nature of sets of MVDs having conflict-free covers. Less emphasis is given in this paper to the actual efficiency of the algorthms. Finally, as a bonus, we derive a desirable property of split-free sets of MVDs,thereby showing that they are interesting in their own right.

Reed-Muller Canonical Forms in Multivalued Logic

Canonical forms for m-valued functions referred to as m-Reed-Muller canonical (m-RMC) forms that are a generalization of RMC forms of two-valued functions are proposed. m-RMC forms are based on the operations ?m (addition mod m) and .m (multiplication mod m) and do not, as in the cases of the generalizations proposed in the literature, require an m-valued function for m not a power of a prime, to be expressed by a canonical form for M-valued functions, where M > m is a power of a prime. Methods of obtaining the m-RMC forms from the truth vector or the sum of products representation of an m-valued function are discussed. Using a generalization of the Boolean difference to m-valued logic, series expansions for m-valued functions are derived.

A Cellular Array for Multivalued Logic Functions

An algebraic generalization of the well-known binary q-function array to a multivalued q-function array is presented. It is possible to associate tree-structure realizations for binary q-functions and multivalued q-functions. Synthesis of multivalued functions using this array is very simple

Some Results on Fixed and Best Proximity Points of Multivalued

This paper is devoted to investigate the fixed points and best proximity points of multivalued cyclic self-mappings on a set of subsets of complete metric spaces endowed with a partial order under a generalized contractive condition involving a Hausdorff distance. The existence and uniqueness of fixed points of both the cyclic self-mapping and its associate composite self-mappings on each of the subsets are investigated, if the subsets in the cyclic disposal are nonempty, bounded and of nonempty convex intersection. The obtained results are extended to the existence of unique best proximity points in uniformly convex Banach spaces.

Fixed point results for multivalued contractions on graphs and their applications

Nous présentons dans cette thèse des théorèmes de point fixe pour des contractions multivoques définies sur des espaces métriques, et, sur des espaces de jauges munis d’un graphe. Nous illustrons également les applications de ces résultats à des inclusions intégrales et à la théorie des fractales. Cette thèse est composée de quatre articles qui sont présentés dans quatre chapitres. Dans le chapitre 1, nous établissons des résultats de point fixe pour des fonctions multivoques, appelées G-contractions faibles. Celles-ci envoient des points connexes dans des points connexes et contractent la longueur des chemins. Les ensembles de points fixes sont étudiés. La propriété d’invariance homotopique d’existence d’un point fixe est également établie pour une famille de Gcontractions multivoques faibles. Dans le chapitre 2, nous établissons l’existence de solutions pour des systèmes d’inclusions intégrales de Hammerstein sous des conditions de type de monotonie mixte. L’existence de solutions pour des systèmes d’inclusions différentielles avec conditions initiales ou conditions aux limites périodiques est également obtenue. Nos résultats s’appuient sur nos théorèmes de point fixe pour des G-contractions multivoques faibles établis au chapitre 1. Dans le chapitre 3, nous appliquons ces mêmes résultats de point fixe aux systèmes de fonctions itérées assujettis à un graphe orienté. Plus précisément, nous construisons un espace métrique muni d’un graphe G et une G-contraction appropriés. En utilisant les points fixes de cette G-contraction, nous obtenons plus d’information sur les attracteurs de ces systèmes de fonctions itérées. Dans le chapitre 4, nous considérons des contractions multivoques définies sur un espace de jauges muni d’un graphe. Nous prouvons un résultat de point fixe pour des fonctions multivoques qui envoient des points connexes dans des points connexes et qui satisfont une condition de contraction généralisée. Ensuite, nous étudions des systèmes infinis de fonctions itérées assujettis à un graphe orienté (H-IIFS). Nous donnons des conditions assurant l’existence d’un attracteur unique à un H-IIFS. Enfin, nous appliquons notre résultat de point fixe pour des contractions multivoques définies sur un espace de jauges muni d’un graphe pour obtenir plus d’information sur l’attracteur d’un H-IIFS. Plus précisément, nous construisons un espace de jauges muni d’un graphe G et une G-contraction appropriés tels que ses points fixes sont des sous-attracteurs du H-IIFS.

Multivalued adaptive neuro-fuzzy controller for robot vehicle - art. no. 1406

Robotic vehicle navigation in unstructured and uncertain environments is still a challenge. This paper presents the implementation of a multivalued neurofuzzy controller for autonomous ground vehicle (AGVs) in indoor environments. The control system consists of a hierarchy of mobile robot using multivalued adaptive neuro-fuzzy inference system behaviors.

Paraconsistent Multivalued Logic and Coincidentia Oppositorum: Evaluation with Complex Numbers

Paraconsistent logic admits that the contradiction can be true. Let p be the truth values and P be a proposition. In paraconsistent logic the truth values of contradiction is . This equation has no real roots but admits complex roots . This is the result which leads to develop a multivalued logic to complex truth values. The sum of truth values being isomorphic to the vector of the plane, it is natural to relate the function V to the metric of the vector space R2. We will adopt as valuations the norms of vectors. The main objective of this paper is to establish a theory of truth-value evaluation for paraconsistent logics with the goal of using in analyzing ideological, mythical, religious and mystic belief systems.

An algorithm for inferring multivalued dependencies that works also for a subclass of propositional logic /

"UILU-ENG 79 1714."

Subset dependencies as an alternative to embedded multivalued dependencies /

"UILU-ENG 79-1732."

Cerami (C) Condition and Mountain Pass Theorem for Multivalued Mappings

Partially supported by Sapientia Foundation.

Homogenization of the p-Laplacian with nonlinear boundary condition on critical size particles: Identifying the strange term for the some non smooth and multivalued operators

We extend previous papers in the literature concerning the homogenization of Robin type boundary conditions for quasilinear equations, in the case of microscopic obstacles of critical size: here we consider nonlinear boundary conditions involving some maximal monotone graphs which may correspond to discontinuous or non-Lipschitz functions arising in some catalysis problems.

Binary decompositions and acyclic schemes

It is well known that the notions of normal forms and acyclicity capture many practical desirable properties for database schemes. The basic schema design problem is to develop design methodologies that strive toward these ideals. The usual approach is to first normalize the database scheme as far as possible. If the resulting scheme is cyclic, then one tries to transform it into an acyclic scheme. In this paper, we argue in favor of carrying out these two phases of design concurrently. In order to do this efficiently, we need to be able to incrementally analyze the acyclicity status of a database scheme as it is being designed. To this end, we propose the formalism of "binary decompositions". Using this, we characterize design sequences that exactly generate theta-acyclic schemes, for theta = agr,beta. We then show how our results can be put to use in database design. Finally, we also show that our formalism above can be effectively used as a proof tool in dependency theory. We demonstrate its power by showing that it leads to a significant simplification of the proofs of some previous results connecting sets of multivalued dependencies and acyclic join dependencies.

Instability Of Plane Poiseuille Flow In A Fluid-Porous System

The instability of Poiseuille flow in a fluid-porous system is investigated. The system consists of a fluid layer overlying porous media and is subjected to a horizontal plane Poiseuille flow. We use Brinkman's model instead of Darcy's law to describe the porous layer. The eigenvalue problem is solved by means of a Chebyshev collocation method. We study the influence of the depth ratio (d) over cap and the Darcy number delta on the instability of the system. We compare systematically the instability of Brinkman's model with the results of Darcy's model. Our results show that no satisfactory agreement between Brinkman's model and Darcy's model is obtained for the instability of a fluid-porous system. We also examine the instability of Darcy's model. A particular comparison with early work is made. We find that a multivalued region may present in the (k, Re) plane, which was neglected in previous work. Here k is the dimensionless wavenumber and Re is the Reynolds number. (C) 2008 American Institute of Physics. [DOI: 10.1063/1.3000643]