Given a table T with a set of dimensions D, the skycube of T is the union of all skylines obtained by considering each of the subsets of D (subspaces). The number of these skylines is exponential w.r.t D. To make the skycube practically useful, two lines of research have been pursued so far: the first one aims to propose efficient algorithms for computing it and the second one considers either that the skycube is too large to be computed in a reasonable time or it requires too much memory space to be stored. They therefore propose skycube summarization techniques to reduce time and space consumption. Intuitively, previous efforts have been devoted to compute or summarize the following information: ``for every tuple t, list the skylines where t belongs to". In this paper, we consider the complementary statement, i.e., ``for every tuple t, list the skylines where t does not belong to". This is what we call the negative skycube. Despite the apparent equivalence between these two statements, our analysis and extensive experiments show that these two points of views do not lead to the same behavior of the related algorithms. More specifically, our proposal shows that (i) the negative summary can be obtained much faster than state of the art techniques for positive summaries, (ii) in general, it consumes less space, (iii) skyline queries evaluation using this summary are much faster, (iv) the positive skycube can be obtained much more rapidly than state of the art algorithms, and (v) it can be used for a larger class of queries, namely k-domination skylines.

Let T be a table of n points described by a set of d attributes/dimensions. Let p, q ∈ T. p dominates q iff it is better than q in every dimension and there exists at least one attribute for which p is strictly better than p. p is a skyline point of T iff it is not dominated by any point of T. A skyline query returns the set of all skyline points. In order to integrate Skyline queries into database management systems, deriving an estimation of the skyline cardinality is important for query optimization purposes. We propose techniques for estimating skyline cardinality when data distribution is known. We first provide an unbiased estimator which requires one traversal of the whole data which is much faster than computing the exact skyline. Then, we show that this estimator can be used on a sample of the underlying data while preserving the estimation quality, i.e., it is still unbiased. Next, we provide a convergent estimator which does not require any data access but the data distribution. It estimates skyline cardinality expectation for those data sets respecting data distribution. The advantages of these solutions are their ease of implementation and, by contrast to other proposals, no costly subskyline queries are required. Our solutions are implemented and some experiments are reported showing both the accuracy of the estimations and the execution time efficiency by which they are obtained.

Given a table T ( Id , D 1 , …, D d ), the skycube of T is the set of skylines with respect to to all nonempty subsets (subspaces) of the set of all dimensions { D 1 , …, D d }. To optimize the evaluation of any skyline query, the solutions proposed so far in the literature either (i) precompute all of the skylines or (ii) use compression techniques so that the derivation of any skyline can be done with little effort. Even though solutions (i) are appealing because skyline queries have optimal execution time, they suffer from time and space scalability because the number of skylines to be materialized is exponential with respect to d . On the other hand, solutions (ii) are attractive in terms of memory consumption, but as we show, they also have a high time complexity. In this article, we make contributions to both kinds of solutions. We first observe that skyline patterns are monotonic. This property leads to a simple yet efficient solution for full and partial skycube materialization when the skyline with respect to all dimensions, the topmost skyline, is small. On the other hand, when the topmost skyline is large relative to the size of the input table, it turns out that functional dependencies, a fundamental concept in databases, uncover a monotonic property between skylines. Equipped with this information, we show that closed attributes sets are fundamental for partial and full skycube materialization. Extensive experiments with real and synthetic datasets show that our solutions generally outperform state-of-the-art algorithms.

The border concept has been introduced by Mannila and Toivonen in their seminal paper [20]. This concept finds many applications, e.g maximal frequent itemsets, minimal functional dependencies, emerging patterns between consecutive database instances and materialized view selection. For large transactions and relational databases defined on n items or attributes, the running time of any border computations are mainly dominated by the time T (for standard sequential algorithms) required to test the interestingness, in general the frequencies, of sets of candidates.

A view selection algorithm takes as input a fact table and computes a set of views to store in order to speed up queries. The performance of view selection algorithm is usually measured by three criteria: (1) the amount of memory to store the selected views, (2) the query response time and (3) the time complexity of this algorithm. The two first measurements deal with the output of the algorithm. No existing solutions give good trade-off between amount of memory and queries cost with a small time complexity. We propose in this paper an algorithm guaranteeing a constant approximation factor of queries response time with respect to the optimal solution. Moreover, the time complexity for a D-dimensional fact table is O (D * 2D) corresponding to the fastest known algorithm. We provide an experimental comparison with two other well known algorithms showing that our approach also gives good performance in terms of memory.

The Semantic Web is a vision for the future of the Web in which information is given explicit meaning, making it easier for machines to automatically process and integrate information available on the Web. An ontology defines the terms used to describe and represent an area of knowledge. Ontologies are used by people, databases, and applications that need to share domain information (a domain is just a specific subject area or area of knowledge, like medicine, tool manufacturing, real estate, automobile repair, financial management, etc.). In this paper we combine this two concepts to annotate models with meta-data according to the corresponding domain ontology with all the new extracted information in order to improve the performance of the entire system.