Search

Given a database fed by two alternative data sources using a common but not identical classification criterion, if we are able to state precisely the semantical connection between the two classification systems, we can derive new and more detailed summary data. Therefore, the question whether an aggregate information is derivable or not, is fundamental to a query-processing system. We state a necessary and sufficient condition which leads to a simple procedure for deciding the answerability of a summary query and evaluating it, if answerable. Surprisingly, the condition of derivability is independent of the database instance and is dependent only on the topological properties of the graph modelling the semantical connection of the classification systems adopted.

In an on-line statistical database, the query-answering system should prevent answers to statistical queries from leading to disclosure of confidential data. On the other hand, a statistical user is inclined to data mining, that is, to disclose pieces of information that are implicit in the (explicit) answers to his queries. A key task for both is to find data that is derivable from given summary statistics. We show that this task is easy if data is additive and the set of given summary statistics can be modelled by a graph.

When answering queries that ask for summary statistics, the query-system of a multidimensional database should guard confidential data, that is, it should avoid revealing (directly or indirectly) individual data, which could be exactly calculated or accurately estimated from the values of answered queries. In order to prevent the disclosure of confidential data, the query-system should be provided with an auditing procedure which, each time a new query is processed, checks that its answer does not allow a (knowledgeable) user to disclose any sensitive data. A promising approach consists in keeping track of (or auditing) answered queries by means a dynamic graphical data structure, here called the answer map, whose size increases with the number of answered queries and with the number of dimensions of the database, so that the problem of the existence of an efficient auditing procedure naturally arises. This chapter reviews recent results on this problem for “additive” queries (such as COUNT and SUM queries) by listing some polynomially solvable problems as well as some hard problems, and suggests directions for future work.

An implementation of the auditing strategy is presented to avoid both exact and approximate disclosure. The key data structure is a query map, which is a graphical summary of answered queries. Since the size of a query map may be exponential in the number of answered queries, a query-restriction criterion is introduced to make every query map a graph. An auditing procedure on such a graph is presented and the computational issues connected with its implementation are discussed. All the computational tasks can be carried out efficiently but one, which is a provably intractable problem.

Given an edge-weighted graph where all weights are nonnegative reals, an edge reweighting is an assignment of nonnegative reals to edges such that, for each vertex, the sums of given and new weights assigned to the edges incident on the vertex do coincide. An edge is then said to be invariant if its weight is the same for any edge reweighting. We show that the set of invariant edges of an arbitrary edge-weighted graph can be determined in time linear in the size of the underlying graph. Moreover, an application to the security of statistical data is discussed.

The notion of vertex separability by partial edges for a simple hypergraph is introduced and the related structural properties of the hypergraph are analyzed in terms of maximal (with respect to set-theoretic inclusion) compacts and of dividers, where a compact is a vertex set in which every two vertices are separated by no partial edge, and a divider is a partial edge X for which there exists a pair of vertices that are separated by X and by no proper subset of X. It is proven that, given a hypergraph H, the hypergraph (called the compaction of H) made up of maximal compacts of H is acyclic and coincides with H if and only if H is acyclic; furthermore, it has the same dividers as H, and can be characterized as being the unique acyclic hypergraph that has the same compacts as H. Polynomial algorithms for finding maximal compacts and dividers of a given hypergraph are provided. Finally, an application to the problem of computing the maximum-entropy extension of a system of marginals over a hypergraph is discussed.

A good strategy to save computational time in a model-search problem consists in endowing the search procedure with a mechanism of logical inference, which sometimes allows a loglinear model to be accepted or rejected on logical grounds, without resorting to the numeric test. In principle, the best inferential mechanism should based on a complete axiomatization of loglinear models. We present a (probably incomplete) axiomatization, which can be translated into a graphical inference procedure working with directed acyclic graphs, and show how it can be applied to find an efficient solution to the model-search problem.

Let G be a connected graph. A subset X of V(G) is g-convex (m-convex) if it contains all vertices on shortest (induced) paths between vertices in X. We state characteristic properties of graphs in which every g-convex set is m-convex, based on which we show that such graphs can be recognized in polynomial time. Moreover, we state a new convexity-theoretic characterization of Ptolemaic graphs.

Submodels of a loglinear probabilistic model are characterized by means of a graph theoretic property suitable for an efficient computation.

We propose a method to protect sensitive information in a two-dimensional statistical table based on the suppression of certain marginal cells. A sensitive cell set is considered unprotected if its exact value can be computed from the values of nonsensitive cells and unsuppressed marginal cells. We provide efficient algorithms to solve the following problems: deciding whether the sensitive cell sets are protected, identifying and evaluating all unprotected cell sets, suppressing the fewest marginal cells to protect all the sensitive cells.

A (hierarchical) loglinear model is said to be collapsible onto a set of variables if the corresponding marginal totals can be drawn from the tables of marginal totals formed by summing the sufficient marginals of the model over the remaining variables. Collapsibility has important consequences for hypothesis testing and model selection, and can be useful in data reduction. We shall present a procedure for computing marginal totals for arbitrary sets of variables; as a by-product, a simple algorithm for testing collapsibility is obtained.

It is shown that the formal system for binary decompositions of database relations applies successfully to binary decompositions of probability distributions and graphs too. As an application, the problem of determining the binary decompositions of a given information system (no matter if a relation, a probability distribution, or a graph) is discussed, and a number of search procedures using the derivation rules of the proposed formal system are presented and compared on a sample relation.

Given a statistical database consisting of two summary tables based on a common but not identical classification criterion (e.g., two geographical partitionings of a country) there are additional summary tables that are derivable in the sense that they are uniquely (i.e., with no uncertainty) determined by the tables given. Derivable tables encompass not only, of course, “less detailed” tables (that is, aggregated data) but also “more detailed” tables (that is, disaggregated data). Tables of the second type can be explicitly constructed by using a “procedure of data refinement” based on the graph representation of the correspondences between the categories of the two classification systems given in some cases, that is, when such a graph representation meets the acyclicity condition, the underlying database is “equivalent” to a single table (called representative table ) and then a necessary and sufficient condition for a table to be derivable can be stated.

The maximum-entropy extension of given discrete probability distributions over a “fully reducible” set class admits a closed-form expression, which makes its computation direct. In the remaining cases the computation of the maximum-entropy extension is carried out using the standard procedure of iterative proportional fitting, whose costs can often be reduced by applying the graph-theoretical techniques of reduction and decomposition . By making joint use of these techniques, we present a computation policy which limits the application of the iterative proportional fitting procedure to computing the marginals of a maximum-entropy distribution corresponding to the nonseparable components (in the graph-theoretical sense) of the underlying set class.

We introduce a statistical data-base model, based on the representation of the attributes by random observables . This is shown to form a conceptual framework for the description both of the data-base contents and of the data-base dependencies. Besides, the application of the information theory to our model allows a high-level data language, suitable for a statistical data analysis, to be developed. Finally, it is shown that such a language has the same deductive power as the formal theories of functional dependencies and of multivalued dependencies.

Three or more probability distributions may be pairwise compatible but not collectively compatible, in the sense that they admit no common extensions. However, pairwise compatibility proves to be a necessary and sufficient condition for collective compatibility when the underlying system of distribution schemes is “acyclic”. If this is the case, then (and only then) do the distributions admit a product extension, whose expression can be computed by a simple algorithm.

A consistent categorical database can be viewed as a single contingency table by taking the maximum-entropy extension of its base tables. Such a view, here called the universal table model , is needed to answer a user who wishes “cross-classified” data, that is, categorical data resulting from the combination of information contained in two or more base tables. In order to implement a universal table interface , we make use of a query-evaluation procedure; this allows for an appropriate answer to be generated whether the requested data are stored in the database or not and, then, have to be computed (i.e., estimated).

The statistical analysis of the database contents is usually performed by using software packages, that require the numerical coding of database attributes. Unfortunately, statistics computed from attribute values ciphered might be meaningless (this is the case when the attribute values are intrinsically not ordered in any way). We present an analytical data model, where the information content of a database relation is represented by a contingency table and analysed using the methods of the multivariate information theory. From these quantitative tools of analysis may benefit first the database user interested in a statistical view of the database contents and inclined to put queries like “to what extent are attributes related (in a given database state)?” or like “how does one attribute depend on the others (in a given database state)?”. A second application, here only sketched, is the measurement of the record selectivities for queries, in view of an evaluation of the physical database organization performance.

In response to queries asked to a statistical database, the query system should avoid releasing summary statistics that could lead to the disclosure of confidential individual data. Attacks to the security of a statistical database may be direct or indirect and, in order to repel them, the query system should audit queries by controlling the amount of information released by their responses. This paper focuses on sum-queries with a response variable of nonnegative real type and proposes a compact representation of answered sum-queries, called an information model in “normal form,” which allows the query system to decide whether the value of a new sum-query can or cannot be safely answered. If it cannot, then the query system will issue the range of feasible values of the new sum-query consistent with previously answered sum-queries. Both the management of the information model and the answering procedure require solving linear-programming problems and, since standard linear-programming algorithms are not polynomially bounded (despite their good performances in practice), effective procedures that make a parsimonious use of them are stated for the general case. Moreover, in the special case that the information model is “graphical.” It is shown that the answering procedure can be implemented in polynomial time.

This communication presents and discusses an experimental proof of the correlation among local structure and second harmonic generation (SHG) in bulk nanostructured potassium niobiosilicate (KNS) glasses. In particular, SHG shows a maximum in correspondence of the early stages of nanostructuring, that are characterized by the segregation within the amorphous matrix of nanosized inhomogeneities. EXAFS experiments indicate that these inhomogeneities are determined by the maximum size reached by the niobium second coordination shell combined with the sudden inclusion of potassium atoms in it. Such rearrangement at the local level determines the maximum fluctuation of the bulk glass refractive index and in turn its maximum SHG activity.

We report an extensive study on the intrinsic bulk electronic structure of the high-temperature superconductor CeFeAsO0.89F0.11 and its parent compound CeFeAsO by soft and hard x-ray photoemissions, x-ray absorption, and soft x-ray emission spectroscopies. The complementary surface/bulk probing depth, and the elemental and chemical sensitivity of these techniques allow resolving the intrinsic electronic structure of each element and correlating it with the local structure, which has been probed by extended x-ray absorption fine-structure spectroscopy. The measurements indicate a predominant 4f1 i.e., Ce3+ initial-state configuration for cerium and an effective valence-band-to-4f charge-transfer screening of the core hole. The spectra also reveal the presence of a small Ce f0 initial-state configuration, which we assign to the occurrence of an intermediate-valence state. The data reveal a reasonably good agreement with the partial density of states as obtained in standard density-functional calculations over a large energy range. Implications for the electronic structure of these materials are discussed

Rare-earth oxides are among the materials which are presently studied as possible replacements of amorphous silicon dioxide as gate insulators in nanometric Si devices; in fact, they generally exhibit high values of the dielectric constant ('high kappa'), a necessary requirement to obtain a high capacitance with layer thickness greater than the value below which tunneling currents become unacceptably high. Lu2O3 is one of the rare-earth oxides which may have the required properties in view of its quite high values of kappa and forbidden band gap. Since the envisaged dielectric layers are only a few nanometers thick, a description and a physical understanding of the atomic and electronic structure of the interface are of great importance. In this paper, we report a study by synchrotron radiation photoemission and transmission electron microscopy of the growth of Lu2O3 on Si(001). Thanks to the high spectral and spatial resolution, we provide clear evidence of a rather complex structure in which all silicon suboxides and SiO2 are present at the same time, along with a silicatelike phase and Lu2O3 itself; moreover, some grains and both crystalline and amorphous portions are present. In the photoemission experiment, the contribution of the Si surface to the core level line shapes has been taken into account; in the electron microscopy measurements, we present line scans on the nanometer scale of O, Si, and Lu concentrations and a Fourier transform discussion of the structure of the crystalline portions of the overlayer. The valence band discontinuity, which is measured in situ and is relative to the structurally well characterized interface, is found to be 3.16 +/- 0.16 eV. These findings are discussed in relation to the suitability of Lu2O3 as a high-kappa dielectric and in the context of available theoretical predictions of thermodynamic stability versus the formation of silicon oxide, silicates, and silicides and of the band discontinuity problem. (c) 2007 American Institute of Physics.

We investigated the local structure around N and Sb atoms in GaAsSbN/GaAs epilayers as a function of growth conditions and annealing time via soft and hard x-ray absorption spectroscopies in order to find out if short range ordering (SRO) in the group-V sublattice is present. SRO is one of the potential origins of the huge blueshift of the band gap observed upon annealing in these materials. By combining a Sb K- and L- and N K-edge x-ray absorption fine structure spectroscopy analysis, we demonstrate that neither strong Sb clustering nor preferential Sb-N association is possible, and that Sb atoms see a random number of N next nearest neighbors except for growth temperatures smaller than 400 degrees C, for which Sb-N neighbors in the type-V sublattice are in excess with respect to statistical disorder. On the other hand, the evolution of SRO around N anions (breaking of nitrogen pairs and randomization) can play a role in the annealing-induced band gap blueshift. Varying growth conditions and concentration modifies the band gap but, surprisingly, it does not affect the position of the conduction band minimum when Sb is incorporated.

We describe the use of x-ray absorption spectroscopy (XAS) with synchrotron radiation to study the local atomic structure of high-k oxide thin and ultra thin films deposited on silicon. A brief description of the advantages of XAS to probe local atomic arrangements in this context is given. We then describe two case studies: Y2O3/Si(001) and Lu2O3/Si(001).

Yttria sY2O3d is one of the candidate materials actively studied as a high dielectric constant replacement of amorphous silicon dioxide in downscaled microelectronic devices. An understanding of the physical properties of yttria epilayers on silicon is both a required prerequisite for applications and of fundamental interest. Using x-ray absorption spectroscopy at both the yttrium and oxygen K edges we study the local atomic and electronic structure in Y2O3 epilayers deposited on Sis001d. We find that above a thin near - interface layer the epilayers have a local atomic and electronic structure bearing a close similarity to that of bulk yttria; however, there is an increase in static disorder with decreasing thickness which can be correlated to an increase of the defectivity. The unoccupied electronic structure, as probed by near edge spectra at the cation and oxygen edges, is very similar to that of bulk yttria; we present and discuss simulations within the real - space full multiple scattering formalism which are quite successful in reproducing the experimental line shape. In the near - interface layer we detect the presence of silicon oxide, as reported for this and other systems previously; a new finding is that yttrium -silicon bonds are present in the interface layer, forming the precursors to the formation of yttrium silicide which develops into a long range ordered phase at higher deposition temperatures. We compare our observations with available theoretical predictions on the thermodynamic stability of yttria in comparison to silicon dioxide, yttrium silicide, and yttrium silicate; the predictions are not confirmed by experiment as far as the 2 nm thick interface layer is concerned.

The search for high dielectric constant (high- k ) oxides to replace silicon dioxide for future CMOS devices is a formidable task. Key issues are definitely good structural and electrical properties as well as high quality interfaces between the high- k and the semiconductor substrate. In this work we study the local structure of ultra thin Y 2 O 3 films and Y 2 O 3 /Si interface, by using Y k -edge X-ray absorption spectroscopy (XAS) in grazing incidence geometry. Y 2 O 3 epilayers (2–20 nm thick) are grown on Si (0 0 1) by MBE at 450 °C and some of them are in-situ annealed at 500 °C for 30 min. In the as grown epilayer, XAS reveals the presence of Y–Si and Y–O correlations at the Y 2 O 3 /Si interface. The in-situ annealing produces a rearrangement of the local atomic environment at the interface and only Y–O correlations are detected. The local structural quality of the epilayers improves with thickness and annealing.

Dilute oxide semiconductor alloys obtained by adding oxygen to a II–VI binary compound are of potential applicative interest for blue-light emitters in which the oxygen content could be used to tune the band gap. Moreover, their properties can be usefully compared to the more thoroughly studied dilute nitrides in order to gain insight into the common mechanisms which give rise to their highly non-linear physical properties. Recently, it has been possible to deposit ZnSeO and ZnSeOS epilayers on GaAs(001), which exhibit a red-shift of the band gap and giant optical bowing. In order to provide a structural basis for an understanding of their physical properties, we have performed a study of a set of ZnSeO and ZnSeOS epilayers on GaAs by high resolution x-ray diffraction and x-ray absorption fine structure. We have found that the strain goes from compressive to tensile with increasing O and S concentration and that, while all epilayers are never found to be pseudomorphic, the ternary ones exhibit a low relaxed fraction if compared to the ZnSe/GaAs sample. O K-edge x-ray absorption near edge spectra and corresponding simulations within the full multiple-scattering regime show that O is substitutionally incorporated in the host lattice. Zn and Se K-edge extended x-ray absorption fine structure detect the formation of Zn–O and Zn–S bonds; the analysis of these spectra within multiple-scattering theory has allowed us to measure the local structural parameters. The value of Zn–Se bond length is found to be in agreement with estimates based on models of local distortions in strained and relaxed epilayers; an increase of the mean-square relative displacement is detected at high O and S concentration and is related to both intrinsic and extrinsic factors.