State-of-the-art relational schema design generates a lossless, dependency-preserving decomposition into Third Normal Form (3NF), that is in Boyce-Codd Normal Form (BCNF) whenever possible. In particular, dependency-preservation ensures that data integrity can be maintained on individual relation schemata without having to join them, but may need to tolerate a priori unbounded levels of data redundancy and integrity faults. As our main contribution we parameterize 3NF schemata by the numbers of minimal keys and functional dependencies they exhibit. Conceptually, these parameters quantify, already at schema design time, the effort necessary to maintain data integrity, and allow us to break ties between 3NF schemata. Computationally, the parameters enable us to optimize normalization into 3NF according to different strategies. Operationally, we show through experiments that our optimizations translate from the logical level into significantly smaller update overheads during integrity maintenance. Hence, our framework provides access to parameters that guide the computation of logical schema designs which reduce operational overheads.

Abstract Covers for a set of functional dependencies (FDs) are fundamental for many areas of data management, such as integrity maintenance, query optimization, database design, and data cleaning. When declaring integrity constraints, keys enjoy native support in database systems while FDs need to be enforced by triggers or at application level. Consequently, maximizing the use of keys will provide the best support. We propose the new notion of mixed cover for a set of FDs, comprising the set of minimal keys together with a cover for the set of non-key FDs implied by the FD set. We establish sequential and parallel algorithms for computing mixed covers from a given set of FDs, and illustrate that they complement each other in terms of their performance. Even though FD covers are typically smaller in number or size than their corresponding mixed cover, the latter generate orders of magnitude lower overheads during integrity maintenance. We also quantify how mixed covers improve the performance of query, refresh and insert operations on the TPC-H benchmark under different constraint workloads and scaling factors. Finally, we illustrate the growth of performance improvement for optimal over minimal-reduced covers, justifying the significant time required for computing the former.

System logs, recording critical information about system operations, serve as indispensable tools for system anomaly detection. Graph-based methods have demonstrated superior performance compared to other methods in capturing the interdependencies of log events. However, existing methods often neglect the complex substructure patterns of nodes within log graphs, making it challenging to capture the subtle alteration in event type, structure, and the location of exceptions that indicate node anomalies. To address this limitation, this paper proposes a novel framework called Substructure-aware Log Anomaly Detection at Code File Level (SLAD). It first introduces a Monte Carlo Tree Search strategy tailored specifically for log anomaly detection to discover representative substructures. Then, SLAD incorporates a substructure distillation way to enhance the efficiency of anomaly inference based on the representative substructures. After that, we introduce a soft pruning to obtain key substructure for nodes. Experimental results show SLAD outperforms all baselines. Particularly, SLAD demonstrates at least 15 times faster than substructure-based graph learning methods in anomaly inference.

Covers for a set of functional dependencies (FDs) are fundamental for many areas of data management, such as integrity maintenance, query optimization, database design, and data cleaning. When declaring integrity constraints, keys enjoy native support in database systems while FDs need to be enforced by triggers or at application level. Consequently, maximizing the use of keys will provide the best support. We propose the new notion of mixed cover for a set of FDs, comprising the set of minimal keys together with a cover for the set of non-key FDs implied by the FD set. We establish sequential and parallel algorithms for computing mixed covers from a given set of FDs, and illustrate that they complement each other in terms of their performance. Even though FD covers are typically smaller in number or size than their corresponding mixed cover, the latter generate orders of magnitude lower overheads during integrity maintenance. We also quantify how mixed covers improve the performance of query, refresh and insert operations on the TPC-H benchmark under different constraint workloads.

We present exact complexity bounds on the discovery of cross joins from database relations, and algorithms that work evidently well on real-world data sets within those bounds.

We parameterize schemata in Boyce-Codd Normal Form (BCNF) by the number n of minimal keys they exhibit. We show that n quantifies a trade-off between access variety and update complexity. Indeed, access variety refers to the number of different ways by which every entity over the schema is represented uniquely, while update complexity refers to the number of attribute sets for which uniqueness needs to be preserved during updates. As normalization aims at minimizing the level of effort required to preserve data consistency during updates, we establish an algorithm that returns a lossless, dependency-preserving 3NF decomposition where the subset of output schemata not in BCNF is minimized and redundant BCNF schemata are eliminated from the highest to the lowest n exhibited. In particular, if a lossless, dependency-preserving BCNF decomposition exists, our algorithm returns one where the maximum n across all output schemata is minimized. Experiments with synthetic and real-world data quantify the impact of n on the update and query performance over schemata in BCNF with n minimal keys, and show insight into the efficacy of our algorithm suite.

A cross join between two attribute sets holds on a relation whenever its projection onto the union of the attribute sets is the cross join between its projections on the first and second attribute set. Hence, the cross join is a fundamental operator on database relations. For example, it can rewrite the division operator into a simple projection, or measure the independence of tuple values between two attribute sets during cardinality estimation. It is therefore surprising that we present the first research on the discovery problem of cross joins. We show that the problem of deciding whether there is a cross join that holds on a given relation is not only NP-complete but W[3]-complete in its arguably most natural parameter, namely its arity. We establish the first algorithms that discover all cross joins that hold on a given relation. We illustrate in experiments with benchmark data that our algorithms perform well within the limits established by our hardness results. Our treatment of cross joins and the design of our algorithms enables us to extend our findings to the discovery of cross joins that meet a given approximation ratio. Our experiments quantify the trade-off between discovery time and targeted ratio.