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.

Karnaugh map analysis and synthesis of threshold functions

A unate function can easily be identified on a Karnaugh map from the well-known property that it cons ist s only ofess en ti al prime implicante which intersect at a common implicant. The additional property that the plot of a unate function F(x, ... XII) on a Karnaugh map should possess in order that F may also be Ivrealizable (n';:; 6) has been found. It has been sh own that the I- realizability of a unate function F corresponds to the ' compac tness' of the plot of F. No resort to tho inequalities is made, and no pre-processing such as positivizing and ordering of the given function is required.

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.

The potential of certification for conservation and management of wild MAP resources

Medicinal and aromatic plants (MAPs) are an integral part of our biodiversity. In majority of MAP rich countries, wild collection practices are the livelihood options for a large number of rural peoples and MAPs play a significant role in socio-economic development of their communities. Recent concern over the alarming situation of the status of wild MAP resources, raw material quality, as well as social exploitation of rural communities, leads to the idea of certification for MAP resource conservation and management. On one hand, while MAP certification addresses environmental, social and economic perspectives of MAP resources, on the other hand, it ensures multi-stakeholder participation in improvement of the MAP sector. This paper presents an overview of MAP certification encompassing its different parameters, current scenario (Indian background), implementation strategies as well as stakeholders’ role in MAP conservation. It also highlights Indian initiatives in this direction.

Analysis of the MAP/G(a,b)/1/N queue with multiple vacations

This paper deals with a batch service queue and multiple vacations. The system consists of a single server and a waiting room of finite capacity. Arrival of customers follows a Markovian arrival process (MAP). The server is unavailable for occasional intervals of time called vacations, and when it is available, customers are served in batches of maximum size ‘b’ with a minimum threshold value ‘a’. We obtain the queue length distributions at various epochs along with some key performance measures. Finally, some numerical results have been presented.

Critical lattice size limit for synchronized chaotic state in one- and two-dimensional diffusively coupled map lattices

We consider diffusively coupled map lattices with P neighbors (where P is arbitrary) and study the stability of the synchronized state. We show that there exists a critical lattice size beyond which the synchronized state is unstable. This generalizes earlier results for nearest neighbor coupling. We confirm the analytical results by performing numerical simulations on coupled map lattices with logistic map at each node. The above analysis is also extended to two-dimensional P-neighbor diffusively coupled map lattices.

Hot deformation behaviour of Mg–3Al alloy—A study using processing map

The hot deformation behaviour of Mg–3Al alloy has been studied using the processing-map technique. Compression tests were conducted in the temperature range 250–550 °C and strain rate range 3 × 10−4 to 102 s−1 and the flow stress data obtained from the tests were used to develop the processing map. The various domains in the map corresponding to different dissipative characteristics have been identified as follows: (i) grain boundary sliding (GBS) domain accommodated by slip controlled by grain boundary diffusion at slow strain-rates (<10−3 s−1) in the temperature range from 350 to 450 °C, (ii) two different dynamic recrystallization (DRX) domains with a peak efficiency of 42% at 550 °C/10−1 s−1 and 425 °C/102 s−1 governed by stress-assisted cross-slip and thermally activated climb as the respective rate controlling mechanisms and (iii) dynamic recovery (DRV) domain below 300 °C in the intermediate strain rate range from 3 × 10−2 to 3 × 10−1 s−1. The regimes of flow instability have also been delineated in the processing map using an instability criterion. Adiabatic shear banding at higher strain rates (>101 s−1) and solute drag by substitutional Al atoms at intermediate strain rates (3 × 10−2 to 3 × 10−1 s−1) in the temperature range (350–450 °C) are responsible for flow instability. The relevance of these mechanisms with reference to hot working practice of the material has been indicated. The processing maps of Mg–3Al alloy and as-cast Mg have been compared qualitatively to elucidate the effect of alloying with aluminum on the deformation behaviour of magnesium.

Quantitative photoacoustic tomography from boundary pressure measurements: noniterative recovery of optical absorption coefficient from the reconstructed absorbed energy map

We describe a noniterative method for recovering optical absorption coefficient distribution from the absorbed energy map reconstructed using simulated and noisy boundary pressure measurements. The source reconstruction problem is first solved for the absorbed energy map corresponding to single- and multiple-source illuminations from the side of the imaging plane. It is shown that the absorbed energy map and the absorption coefficient distribution, recovered from the single-source illumination with a large variation in photon flux distribution, have signal-to-noise ratios comparable to those of the reconstructed parameters from a more uniform photon density distribution corresponding to multiple-source illuminations. The absorbed energy map is input as absorption coefficient times photon flux in the time-independent diffusion equation (DE) governing photon transport to recover the photon flux in a single step. The recovered photon flux is used to compute the optical absorption coefficient distribution from the absorbed energy map. In the absence of experimental data, we obtain the boundary measurements through Monte Carlo simulations, and we attempt to address the possible limitations of the DE model in the overall reconstruction procedure.

Analysis of connectivity map: Control to glutamate injured and phenobarbital treated neuronal network

We study the responses of a cultured neural network when it is exposed to epileptogenesis glutamate injury causing epilepsy and subsequent treatment with phenobarbital by constructing connectivity map of neurons using correlation matrix. This study is particularly useful in understanding the pharmaceutical drug induced changes in the neuronal network properties with insights into changes at the systems biology level. (C) 2010 American Institute of Physics. [doi:10.1063/1.3398025]

Low-Complexity Near-MAP Decoding of Large Non-Orthogonal STBCs Using PDA

Non-orthogonal space-time block codes (STBC) from cyclic division algebras (CDA) are attractive because they can simultaneously achieve both high spectral efficiencies (same spectral efficiency as in V-BLAST for a given number of transmit antennas) as well as full transmit diversity. Decoding of non-orthogonal STBCs with hundreds of dimensions has been a challenge. In this paper, we present a probabilistic data association (PDA) based algorithm for decoding non-orthogonal STBCs with large dimensions. Our simulation results show that the proposed PDA-based algorithm achieves near SISO AWGN uncoded BER as well as near-capacity coded BER (within 5 dB of the theoretical capacity) for large non-orthogonal STBCs from CDA. We study the effect of spatial correlation on the BER, and show that the performance loss due to spatial correlation can be alleviated by providing more receive spatial dimensions. We report good BER performance when a training-based iterative decoding/channel estimation is used (instead of assuming perfect channel knowledge) in channels with large coherence times. A comparison of the performances of the PDA algorithm and the likelihood ascent search (LAS) algorithm (reported in our recent work) is also presented.

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

Karnaugh map synthesis of multigate threshold networks

It has been shown in an earlier paper that I-realizability of a unate function F of up to six variables corresponds to ' compactness ' of the plot of F on a Karnaugh map. Here, an algorithm has been presented to synthesize on a Karnaugh map a non-threahold function of up to Bix variables with the minimum number of threshold gates connected in cascade. Incompletely specified functions can also be treated. No resort to inequalities is made and no pre-processing (such as positivizing and ordering) of the given switching function is required.

Processing map for hot working of alpha-zirconium

The hot deformation characteristics of alpha-zirconium in the temperature range of 650 °C to 850 °C and in the strain-rate range of 10-3 to 102 s-1 are studied with the help of a power dissipation map developed on the basis of the Dynamic Materials Model.[7,8,9] The processing map describes the variation of the efficiency of power dissipation (η =2m/m + 1) calculated on the basis of the strain-rate sensitivity parameter (m), which partitions power dissipation between thermal and microstructural means. The processing map reveals a domain of dynamic recrystallization in the range of 730 °C to 850 °C and 10−2 to 1−1 with its peak efficiency of 40 pct at 800 °C and 0.1 s-1 which may be considered as optimum hot-working parameters. The characteristics of dynamic recrystallization are similar to those of static recrystallization regarding the sigmoidal variation of grain size (or hardness) with temperature, although the dynamic recrystallization temperature is much higher. When deformed at 650 °C and 10-3 s-1 texture-induced dynamic recovery occurred, while at strain rates higher than 1 s-1, alpha-zirconium exhibits microstructural instabilities in the form of localized shear bands which are to be avoided in processing.