Robust heuristics for scalable optimization of complex SQL queries

Modern database systems incorporate a query optimizer to identify the most efficient "query execution plan" for executing the declarative SQL queries submitted by users. A dynamic-programming-based approach is used to exhaustively enumerate the combinatorially large search space of plan alternatives and, using a cost model, to identify the optimal choice. While dynamic programming (DP) works very well for moderately complex queries with up to around a dozen base relations, it usually fails to scale beyond this stage due to its inherent exponential space and time complexity. Therefore, DP becomes practically infeasible for complex queries with a large number of base relations, such as those found in current decision-support and enterprise management applications. To address the above problem, a variety of approaches have been proposed in the literature. Some completely jettison the DP approach and resort to alternative techniques such as randomized algorithms, whereas others have retained DP by using heuristics to prune the search space to computationally manageable levels. In the latter class, a well-known strategy is "iterative dynamic programming" (IDP) wherein DP is employed bottom-up until it hits its feasibility limit, and then iteratively restarted with a significantly reduced subset of the execution plans currently under consideration. The experimental evaluation of IDP indicated that by appropriate choice of algorithmic parameters, it was possible to almost always obtain "good" (within a factor of twice of the optimal) plans, and in the few remaining cases, mostly "acceptable" (within an order of magnitude of the optimal) plans, and rarely, a "bad" plan. While IDP is certainly an innovative and powerful approach, we have found that there are a variety of common query frameworks wherein it can fail to consistently produce good plans, let alone the optimal choice. This is especially so when star or clique components are present, increasing the complexity of th- e join graphs. Worse, this shortcoming is exacerbated when the number of relations participating in the query is scaled upwards.

A network representation of protein structures: Implications for protein stability

This study views each protein structure as a network of noncovalent connections between amino acid side chains. Each amino acid in a protein structure is a node, and the strength of the noncovalent interactions between two amino acids is evaluated for edge determination. The protein structure graphs (PSGs) for 232 proteins have been constructed as a function of the cutoff of the amino acid interaction strength at a few carefully chosen values. Analysis of such PSGs constructed on the basis of edge weights has shown the following: 1), The PSGs exhibit a complex topological network behavior, which is dependent on the interaction cutoff chosen for PSG construction. 2), A transition is observed at a critical interaction cutoff, in all the proteins, as monitored by the size of the largest cluster (giant component) in the graph. Amazingly, this transition occurs within a narrow range of interaction cutoff for all the proteins, irrespective of the size or the fold topology. And 3), the amino acid preferences to be highly connected (hub frequency) have been evaluated as a function of the interaction cutoff. We observe that the aromatic residues along with arginine, histidine, and methionine act as strong hubs at high interaction cutoffs, whereas the hydrophobic leucine and isoleucine residues get added to these hubs at low interaction cutoffs, forming weak hubs. The hubs identified are found to play a role in bringing together different secondary structural elements in the tertiary structure of the proteins. They are also found to contribute to the additional stability of the thermophilic proteins when compared to their mesophilic counterparts and hence could be crucial for the folding and stability of the unique three-dimensional structure of proteins. Based on these results, we also predict a few residues in the thermophilic and mesophilic proteins that can be mutated to alter their thermal stability.

Effect of impulsive change of wall velocity and wall temperature in viscous heat-conducting gas

A study of compression waves produced in a viscous heat-conducting gas by the impulsive start of a one-dimensional piston and by the inpulsive change of piston wall temperature is made using Laplace Transform Technique for Prandt1 number unity. Expressions for velocity, temperature and density have also been obtained using small-time expansion procedure in this case. For arbitrary Prandt1 number solutions have been developed using large-time expansion procedure. A number of graphs exhibiting the distribution of the fluid velocity, temperature and density have been drawn.

Harmonic and anharmonic oscillations of a cylindrical plasma in the presence of a uniform axial magnetic field and a steady axial current

In the present note we have studied the harmonic and anharmonic oscillations of cylindrical plasma using Lagrangian formalism. In order to study the harmonic oscillations, the equations are linearized and the resulting equation for the displacement has been numerically solved. For situations present in thermonuclear reactors, the presence of axial magnetic field is found necessary to make the periods of oscillation to become comparable with the time required for the thermonuclear reactions to set in. A detailed analysis of the anharmonic oscillations reveals that the significant interaction is between the first and the second mode. The fundamental period of anharmonic oscillation is more than the corresponding period of harmonic oscillations by 9·2%. Graphs have been drawn for the amplitudes of relative variations in density and magnetic field and of the time-varying part of anharmonic oscillation.

Vibration of simply-supported trapezoidal plates I. Symmetric trapezoids

A detailed investigation of the natural frequencies and mode shapes of simply supported symmetric trapezoidal plates is undertaken in this paper. For numerical calculations, the relationship that exists between the eigenvalue problem of a polygonal simply supported plate and the eigenvalue problem of polygonal membrane of the same shape is utilized with advantage. The deflection surface is expressed in terms of a Fourier sine series in transformed coordinates and the Galerkin method is used. Results are presented in the form of tables and graphs. Several features like the crossing of frequency curves and the metamorphosis of some of the nodal patterns are observed. By a suitable interpretation of the modes of those symmetric trapezoidal plates which have the median as the nodal line, the results for some of the modes of unsymmetrical trapezoidal plates are also deduced.

On compressible boundary layer on a flat plate with uniform suction

A quartic profile in terms of the normal distance from the wall has been taken and coefficients are evaluated by satisfying one more boundary condition on the wall than the usual one. By doing so, the limitations about the Reynolds number of the quartic profile adopted by Lew (1949) has been removed. The Kármán (1921) Momentum Integral Equation has been used to evaluate the various characteristics of the flow. A comparative study of Lew's quartic profile and exponential profile together with the quartic profile of the present paper has been undertaken and the graphs for the various characteristics of the flow for a number of Mach numbers and suction coefficients have been drawn. At the end, certain conclusions of general nature about the velocity profiles have been recorded.

Incremental attribute evaluation through recursive procedures

Incremental semantic analysis in a programming environment based on Attribute Grammars is performed by an Incremental Attribute Evaluator (IAE). Current IAEs are either table-driven or make extensive use of graph structures to schedule reevaluation of attributes. A method of compiling an Ordered Attribute Grammar into mutually recursive procedures is proposed. These procedures form an optimal time Incremental Attribute Evaluator for the attribute grammar, which does not require any graphs or tables.

Max-Coloring Paths: Tight Bounds and Extensions

The max-coloring problem is to compute a legal coloring of the vertices of a graph G = (V, E) with a non-negative weight function w on V such that Sigma(k)(i=1) max(v epsilon Ci) w(v(i)) is minimized, where C-1, ... , C-k are the various color classes. Max-coloring general graphs is as hard as the classical vertex coloring problem, a special case where vertices have unit weight. In fact, in some cases it can even be harder: for example, no polynomial time algorithm is known for max-coloring trees. In this paper we consider the problem of max-coloring paths and its generalization, max-coloring abroad class of trees and show it can be solved in time O(vertical bar V vertical bar+time for sorting the vertex weights). When vertex weights belong to R, we show a matching lower bound of Omega(vertical bar V vertical bar log vertical bar V vertical bar) in the algebraic computation tree model.

Experimental and Computational Characterization of Alloy--Spinel--Corundum Equilibrium in the System Fe--Co--Al--O at 1873K

The three-phase equilibrium between alloy, spinel solid solution and alpha -Al sub 2 O sub 3 in the Fe--Co--Al--O system at 1873k was fully characterized as a function of alloy composition using both experimental and computational methods. The equilibrium oxygen content of the liquid alloy was measured by suction sampling and inert gas fusion analysis. The O potential corresponding to the three-phase equilibrium was determined by emf measurements on a solid state galvanic cell incorporating (Y sub 2 O sub 3 )ThO sub 2 as the solid electrolyte and Cr + Cr sub 2 O sub 3 as the reference electrode. The equilibrium composition of the spinel phase formed at the interface between the alloy and alumina crucible was measured by electron probe microanalysis (EPMA). The experimental results were compared with the values computed using a thermodynamic model. The model used values for standard Gibbs energies of formation of pure end-member spinels and Gibbs energies of solution of gaseous O in liquid Fe and cobalt available in the literature. The activity--composition relationship in the spinel solid solution was computed using a cation distribution model. The variation of the activity coefficient of O with alloy composition in the Fe--Co--O system was estimated using both the quasichemical model of Jacob and Alcock and Wagner's model along with the correlations of Chiang and Chang and Kuo and Chang. The computed results of spinel composition and O potential are in excellent agreement with the experimental data. Graphs. 29 ref.--AA

Outward spherical solidification of a superheated melt with time dependent boundary flux

Short-time analytical solutions of solid and liquid temperatures and freezing front have been obtained for the outward radially symmetric spherical solidification of a superheated melt. Although results are presented here only for time dependent boundary flux, the method of solution can be used for other kinds of boundary conditions also. Later, the analytical solution has been compared with the numerical solution obtained with the help of a finite difference numerical scheme in which the grid points change with the freezing front position. An efficient method of execution of the numerical scheme has been discussed in details. Graphs have been drawn for the total solidification times and temperature distributions in the solid.

The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

A k-dimensional box is the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval oil the real line of the form a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-cubes. The threshold dimension of a graph G(V, E) is the smallest integer k such that E can be covered by k threshold spanning subgraphs of G. In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on n vertices with factor O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is NP-complete to determine whether a given split graph has boxicity at most 3. (C) 2010 Elsevier B.V. All rights reserved.

Thermodynamic Stability of Potassium-beta-Alumina

The activity of K sub 2 O in a mixture of alpha -alumina and potassium beta -alumina has been determined using a solid state galvanic cell in the temperature range 600-1000K. The cell is written such that the right hand electrode is positive. The solid electrolyte consisted of a dispersion of alpha -alumina ( approx 15 vol.%) in a matrix of K beta -alumina. The emf of the cell was found to be reversible and to vary linearly with temperature. From the emf and auxiliary data on In sub 2 O sub 3 and K sub 2 O from the literature, the activity of K sub 2 O in the two-phase mixture is obtained. The standard free energy of formation of K beta -alumina from component oxides is given. Graphs.

Design of nonequivalent self-routing networks based on a matrix model

In earlier work, nonisomorphic graphs have been converted into networks to realize Multistage Interconnection networks, which are topologically nonequivalent to the Baseline network. The drawback of this technique is that these nonequivalent networks are not guaranteed to be self-routing, because each node in the graph model can be replaced by a (2 × 2) switch in any one of the four different configurations. Hence, the problem of routing in these networks remains unsolved. Moreover, nonisomorphic graphs were obtained by interconnecting bipartite loops in a heuristic manner; the heuristic nature of this procedure makes it difficult to guarantee full connectivity in large networks. We solve these problems through a direct approach, in which a matrix model for self-routing networks is developed. An example is given to show that this model encompases nonequivalent self-routing networks. This approach has the additional advantage in that the matrix model itself ensures full connectivity.

Mixed Convection Induced in a Gas Flowing Past a Hot Horizontal Flat Plate

A boundary layer analysis of mixed convective motion over a hot horizontal flat plate is performed under the conditions of steady flow and low speed. Use of the Howarth-Dorodnytsyn transformation makes it possible to dispense with the usual Boussinesq approximation, and variable gas properties are accounted for via the assumption that dynamic viscosity and thermal conductivity are proportional to the absolute temperature. The formulation presented enables the entire mixed convection regime to be described by a single set of equations. Finite difference solutions when the Prandtl number is 0.72 are obtained over the entire range of the mixed convection parameter ξ from 0 (free convection) to 1 (forced convection) and heating parameter ▵ values from 2 to 12. The effects of both ξ and ▵on the velocity profiles, the temperature profiles, and the variation of skin friction and heat transfer functions are clearly illustrated in tables and graphs.

Inelastic response of beams under sinusoidal and random loads

A new analytical model has been suggested for the hysteretic behaviour of beams. The model can be directly used in a response analysis without bothering to locate the precise point where the unloading commences. The model can efficiently simulate several types of realistic softening hysteretic loops. This is demonstrated by computing the response of cantilever beams under sinusoidal and random loadings. Results are presented in the form of graphs for maximum deflection, bending moment and shear