In order to answer a “joint” query from multiple data cubes, Pourabass and Shoshani [2007] distinguish the data cube on the measure of interest (called the “primary” data cube) from the other data cubes (called “proxy” data cubes) that are used to involve the dimensions (in the query) not in the primary data cube. They demonstrate in study cases that, if the measures of the primary and proxy data cubes are correlated, then the answer to a joint query is an accurate estimate of its true value. Needless to say, for two or more proxy data cubes, the result depends upon the way the primary and proxy data cubes are combined together; however, for certain combination schemes Pourabass and Shoshani provide a sufficient condition , that they call proxy noncommonality , for the invariance of the result. In this article, we introduce: (1) a merge operator combining the contents of a primary data cube with the contents of a proxy data cube, (2) merge expressions for general combination schemes, and (3) an equivalence relation between merge expressions having the same pattern. Then, we prove that proxy noncommonality characterizes patterns for which every two merge expressions are equivalent. Moreover, we provide an efficient procedure for answering joint queries in the special case of perfect merge expressions. Finally, we show that our results apply to data cubes in which measures are obtained from unaggregated data using the aggregate functions SUM, COUNT, MAX, and MIN, and a lot more.

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.

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.

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.

Protecting sensitive information in a two-dimensional table asked for by a statistical user of a database raises computational problems involving both the query system which should guarantee the data security, and the user who should be able to disclose sensitive data when it is unprotected. We provide a quadratic algorithm which allows the query system to test a censored table for security, and a linear algorithm to find a minimum number of suppressions sufficient for protecting all sensitive cells; however, if sensitive information refers not only to single cells but also to cell sets, we prove that the problem of minimizing the number of suppressions is NP-hard. Finally, we provide a cubic algorithm which allows a user to disclose sensitive information in a censored table.

In order to achieve a good design of a probabilistic database, we introduce statistical join dependencies whose definition shows an apparent analogy with relational join dependencies. Indeed, a certain number of formal properties of relational join dependencies are shared by statistical join dependencies; so, we can sometimes apply the design techniques employed for relational databases to probabilistic databases.>

Female AdministrahonAt this point the query can be evaluated; due to assumptions Al and A2, the value C(Q) can be computed using formula (1).This quantity is called the

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 heuristic procedure is presented for approximating an n-dimensional discrete probability distribution with a decomposable model of a given complexity. It is shown that, without loss of generality, the search space can be restricted to a suitable subclass of decomposable models, whose members are called elementary models. The selected elementary model is constructed in an incremental manner according to a local-optimality criterion that consists of minimizing a suitable cost function. It is shown by an example that the solution computed by the procedure is sometimes optimal.>

The evaluability of queries on a statistical database containing joinable tables connected by an intersection hypergraph is considered. A characterization of evaluable queries is given, which allows one to define polynomial-time procedures both for testing evaluability and for evaluating queries. These results are useful in designing an 'informed query system' for statistical databases which promotes an integrated use of stored information. Such a query system allows the user to formulate a query involving attributes from several joinable tables as if they were all contained in a single universal table.>

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.

A compatible categorical data base can be viewed as a single (contingency) table by taking the maximum-entropy extension of the component tables. Such a view, here called universal table model, is needed to answer a user who wishes “cross-classified” categorical data, that is, categorical data resulting from the combination of the information contents of two or more base tables. In order to implement a universal table interface we make use of a query-optimization procedure, which is able to generate an appropriate answer both in the case that the asked data are present in the data base and in the case that they are not and, then, have to be estimated