Aggregate queries often require computing large intermediate joins despite producing only small outputs. We identify broad classes of acyclic aggregate queries that can be evaluated without materialising any join results, using a bottom-up, semi-join–based propagation of cardinalities and partial aggregates. An implementation in Spark SQL shows that this approach is widely applicable and yields substantial performance gains on standard benchmarks.

Graph Transformers are popular neural networks that extend the well-known Transformer architecture to the graph domain. These architectures operate by applying self-attention on graph nodes and incorporating graph structure through the use of positional encodings (e.g., Laplacian positional encoding) or structural encodings (e.g., random-walk structural encoding). The quality of such encodings is critical, since they provide the necessary \emph{graph inductive biases} to condition the model on graph structure. In this work, we propose \emph{motif structural encoding} (MoSE) as a flexible and powerful structural encoding framework based on counting graph homomorphisms. Theoretically, we compare the expressive power of MoSE to random-walk structural encoding and relate both encodings to the expressive power of standard message passing neural networks. Empirically, we observe that MoSE outperforms other well-known positional and structural encodings across a range of architectures, and it achieves state-of-the-art performance on a widely studied molecular property prediction dataset.

Hypertree decompositions provide a way to evaluate Conjunctive Queries (CQs) in polynomial time, where the exponent of this polynomial is determined by the width of the decomposition. In theory, the goal of efficient CQ evaluation therefore has to be a minimisation of the width. However, in practical settings, it turns out that there are also other properties of a decomposition that influence the performance of query evaluation. It is therefore of interest to restrict the computation of decompositions by constraints and to guide this computation by preferences. To this end, we propose a novel framework based on candidate tree decompositions, which allows us to introduce soft hypertree width (shw). This width measure is a relaxation of hypertree width (hw); it is never greater than hw and, in some cases, shw may actually be lower than hw. Most importantly, shw preserves the tractability of deciding if a given CQ is below some fixed bound, while offering more algorithmic flexibility. In particular, it provides a natural way to incorporate preferences and constraints into the computation of decompositions. A prototype implementation and preliminary experiments confirm that this novel framework can indeed have a practical impact on query evaluation.

Optimising queries with many joins is known to be a hard problem. The explosion of intermediate results as opposed to a much smaller final result poses a serious challenge to modern database management systems (DBMSs). This is particularly glaring in case of analytical queries that join many tables but ultimately only output comparatively small aggregate information. Analogous problems are faced by graph database systems when processing analytical queries with aggregates on top of complex path queries. In this work, we propose novel optimisation techniques, both on the logical, and physical level, that allow us to avoid the materialisation of join results for certain types of aggregate queries. The key to these optimisations is the notion of guardedness , by which we impose restrictions on the occurrence of attributes in GROUP BY clauses and in aggregate expressions. The efficacy of our optimisations is validated through their implementation in Spark SQL and extensive empirical evaluation on various standard benchmarks.

Regarding computer security, the growth of code vulnerability types presents a persistent challenge. These vulnerabilities, which may cause severe consequences, necessitate precise classification for effective mitigation. However, the rapid emergence of new vulnerability types complicates the classification process. Traditional methodologies, which often involve human expertise and the manual labeling or generation of example instances, are not only resource-intensive but also struggle to adapt to the dynamic nature of these vulnerabilities. This article introducesVulnSense, an innovative method that harnesses the capabilities of Generalized Zero-Shot Learning (GZSL) to address the vulnerability classification problem.VulnSenselearns about unseen vulnerability classes from the descriptions of these unseen classes, while not requiring to see any instances of these unseen classes. Specifically,VulnSenselearns from three main resources: 1) seen classes with labeled code instances; 2) descriptions of these seen classes; and 3) descriptions of “unseen” classes which have no labeled instances. Our experiments underscoreVulnSense's superiority over existing GZSL methods in classifying instances of unseen classes. Concurrently, it maintains a performance parity with traditional labeled-example based learning methods in classifying instances of seen vulnerabilities.VulnSensedemonstrates the potential of using GZSL for vulnerability classification, while also highlighting challenges that inspire future work.

Seminal research in the field of graph neural networks (GNNs) has revealed a direct correspondence between the expressive capabilities of GNNs and the $k$-dimensional Weisfeiler-Leman ($k$WL) test, a widely-recognized method for verifying graph isomorphism. This connection has reignited interest in comprehending the specific graph properties effectively distinguishable by the $k$WL test. A central focus of research in this field revolves around determining the least dimensionality $k$, for which $k$WL can discern graphs with different number of occurrences of a pattern graph $p$. We refer to such a least $k$ as the WL-dimension of this pattern counting problem. This inquiry traditionally delves into two distinct counting problems related to patterns: subgraph counting and induced subgraph counting. Intriguingly, despite their initial appearance as separate challenges with seemingly divergent approaches, both of these problems are interconnected components of a more comprehensive problem: "graph motif parameters". In this paper, we provide a precise characterization of the WL-dimension of labeled graph motif parameters. As specific instances of this result, we obtain characterizations of the WL-dimension of the subgraph counting and induced subgraph counting problem for every labeled pattern $p$. Particularly noteworthy is our resolution of a problem left open in previous work concerning induced copies. We additionally demonstrate that in cases where the $k$WL test distinguishes between graphs with varying occurrences of a pattern $p$, the exact number of occurrences of $p$ can be computed uniformly using only local information of the last layer of a corresponding GNN. We finally delve into the challenge of recognizing the WL-dimension of various graph parameters. We give a polynomial time algorithm for determining the WL-dimension of the subgraph counting problem for given pattern $p$, answering an open question from previous work. We additionally show how to utilize deep results from the field of graph motif parameters, together with our characterization, to determine the WL-dimension of induced subgraph counting and counting $k$-graphlets.

A large body of work has investigated the properties of graph neural networks and identified several limitations, particularly pertaining to their expressive power. Their inability to count certain patterns (e.g., cycles) in a graph lies at the heart of such limitations, since many functions to be learned rely on the ability of counting such patterns. Two prominent paradigms aim to address this limitation by enriching the graph features with subgraph or homomorphism pattern counts. In this work, we show that both of these approaches are sub-optimal in a certain sense and argue for a more fine-grained approach, which incorporates the homomorphism counts of all structures in the “basis” of the target pattern. This yields strictly more expressive architectures without incurring any additional overhead in terms of computational complexity compared to existing approaches. We prove a series of theoretical results on node-level and graph-level motif parameters and empirically validate them on standard benchmark datasets.

One of the main challenges in the area of Neuro-Symbolic AI is to perform logical reasoning in the presence of both neural and symbolic data. This requires combining heterogeneous data sources such as knowledge graphs, neural model predictions, structured databases, crowd-sourced data, and many more. To allow for such reasoning, we generalise the standard rule-based language Datalog with existential rules (commonly referred to as tuple-generating dependencies) to the fuzzy setting, by allowing for arbitrary t-norms in the place of classical conjunctions in rule bodies. The resulting formalism allows us to perform reasoning about data associated with degrees of uncertainty while preserving computational complexity results and the applicability of reasoning techniques established for the standard Datalog setting. In particular, we provide fuzzy extensions of Datalog chases which produce fuzzy universal models and we exploit them to show that in important fragments of the language, reasoning has the same complexity as in the classical setting.

Generalised hypertree width ($ghw$) is a hypergraph parameter that is central to the tractability of many prominent problems with natural hypergraph structure. Computing $ghw$ of a hypergraph is notoriously hard. The decision version of the problem, checking whether $ghw(H) \leq k$, is paraNP-hard when parameterised by $k$. Furthermore, approximation of $ghw$ is at least as hard as approximation of Set-Cover, which is known to not admit any fpt approximation algorithms. Research in the computation of ghw so far has focused on identifying structural restrictions to hypergraphs -- such as bounds on the size of edge intersections -- that permit XP algorithms for $ghw$. Yet, even under these restrictions that problem has so far evaded any kind of fpt algorithm. In this paper we make the first step towards fpt algorithms for $ghw$ by showing that the parameter can be approximated in fpt time for graphs of bounded edge intersection size. In concrete terms we show that there exists an fpt algorithm, parameterised by $k$ and $d$, that for input hypergraph $H$ with maximal cardinality of edge intersections $d$ and integer $k$ either outputs a tree decomposition with $ghw(H) \leq 4k(k+d+1+)(2k-1)$, or rejects, in which case it is guaranteed that $ghw(H) > k$. Thus, in the special case, of hypergraphs of bounded edge intersection, we obtain an fpt $O(k^3)$-approximation algorithm for $ghw$.

Various classic reasoning problems with natural hypergraph representations are known to be tractable if a hypertree decomposition (HD) of low width exists. The resulting algorithms are attractive for practical use in fields like databases and constraint satisfaction. However, algorithmic use of HDs relies on the difficult task of first computing a decomposition of the hypergraph underlying a given problem instance, which is then used to guide the algorithm for this particular instance. The performance of purely sequential methods for computing HDs is inherently limited, yet the problem is, theoretically, amenable to parallelisation. In this article, we propose the first algorithm for computing hypertree decompositions that is well suited for parallelisation. The newly proposed algorithm log- k -decomp requires only a logarithmic number of recursion levels and additionally allows for highly parallelised pruning of the search space by restriction to so-called balanced separators. We provide a detailed experimental evaluation over the HyperBench benchmark and demonstrate that log- k -decomp outperforms the current state of the art significantly.

Existential rules, also known as tuple-generating dependencies (TGDs) or Datalog+/- rules, are heavily studied in the communities of Knowledge Representation and Reasoning, Semantic Web, and Databases, due to their rich modelling capabilities. In this paper we consider TGDs in the temporal setting, by introducing and studying DatalogMTLE---an extension of metric temporal Datalog (DatalogMTL) obtained by allowing for existential rules in programs. We show that DatalogMTLE is undecidable even in the restricted cases of guarded and weakly-acyclic programs. To address this issue we introduce uniform semantics which, on the one hand, is well-suited for modelling temporal knowledge as it prevents from unintended value invention and, on the other hand, provides decidability of reasoning; in particular, it becomes 2-EXPSPACE-complete for weakly-acyclic programs but remains undecidable for guarded programs. We provide an implementation for the decidable case and demonstrate its practical feasibility. Thus we obtain an expressive, yet decidable, rule-language and a system which is suitable for complex temporal reasoning with existential rules.

Modern data processing applications often combine information from a variety of complex sources. Oftentimes, some of these sources, like Machine-Learning systems or crowd-sourced data, are not strictly binary but associated with some degree of confidence in the observation. Ideally, reasoning over such data should take this additional information into account as much as possible. To this end, we propose extensions of Datalog and Datalog+/- to the semantics of Lukasiewicz logic Ł, one of the most common fuzzy logics. We show that such an extension preserves important properties from the classical case and how these properties can lead to efficient reasoning procedures for these new languages.

Extending programming languages with stochastic behaviour such as probabilistic choices or random sampling has a long tradition in computer science. A recent development in this direction is a declarative probabilistic programming language, proposed by Barany et al. in 2017, which operates on standard relational databases. In particular, Barany et al. proposed generative Datalog, a probabilistic extension of Datalog that allows sampling from discrete probability distributions. Intuitively, the output of a generative Datalog program P on an input database D is a probability space over the minimal models of D and P, the so-called possible outcomes. This is a natural generalization of the (deterministic) semantics of Datalog, where the output of a program on a database is their unique minimal model. A natural question to ask is how generative Datalog can be enriched with the useful feature of negation, which in turn leads to a strictly more expressive declarative probabilistic programming language. In particular, the challenging question is how the probabilistic semantics of generative Datalog with negation can be robustly defined. Our goal is to provide an answer to this question by interpreting negation according to the stable model semantics.

We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs H→ and G→, count the number of copies of H→ in G→. The standard setting, where the tractability is well understood, uses only |H→| as a parameter. In this paper we adopt as a parameter |H→|+d(G→), where d(G→) is the maximum outdegree of |G→|. Under this parameterisation, we completely characterize the fixed-parameter tractability of the problem in both its non-induced and induced versions through two novel structural parameters, the fractional cover number ρ* and the source number αs. On the one hand we give algorithms with running time f(|H→|,d(G→)) · |G→|ρ*(H→)+O(1) and f(|H→|,d(G→)) · |G→|αs(H→)+O(1) for counting respectively the copies and induced copies of H→ in G→; on the other hand we show that, unless the Exponential Time Hypothesis fails, for any class C→ of directed graphs the restriction of the problem to patterns in C→ is fixed-parameter tractable if and only if ρ*(C→) is bounded (αs(C→) for the induced version). These results explain how the orientation of the pattern can make counting easy or hard, and prove that a classic algorithm by Chiba and Nishizeki and its extensions (Chiba and Nishizeki, SICOMP ’85; Bressan, Algorithmica ’21) are optimal unless ETH fails.

Fractional (hyper-)graph theory is concerned with the specific problems that arise when fractional analogues of otherwise integer-valued (hyper-)graph invariants are considered. The focus of this paper is on fractional edge covers of hypergraphs. Our main technical result generalizes and unifies previous conditions under which the size of the support of fractional edge covers is bounded independently of the size of the hypergraph itself. We show how this combinatorial result can be used to extend previous tractability results for checking if the fractional hypertree width of a given hypergraph is ≤k for some constant k. Moreover, we show a dual version of our main result for fractional hitting sets.

Numerous fundamental database and reasoning problems are known to be NP-hard in general but tractable on instances where the underlying hypergraph structure is β-acyclic. Despite the importance of many of these problems, there has been little success in generalizing these results beyond acyclicity. In this paper, we take on this challenge and propose nest-set width, a novel generalization of hypergraph β-acyclicity. We demonstrate that nest-set width has desirable properties and algorithmic significance. In particular, evaluation of boolean conjunctive queries with negation (CQ¬) is tractable for classes with bounded nest-set width. Furthermore, propositional satisfiability (SAT) is fixed-parameter tractable when parameterized by nest-set width.

Various classic reasoning problems with natural hypergraph representations are known to be tractable when a hypertree decomposition (HD) of low width exists. The resulting algorithms are attractive for practical use in fields like databases and constraint satisfaction. However, algorithmic use of HDs relies on the difficult task of first computing a decomposition of the hypergraph underlying a given problem instance, which is then used to guide the algorithm for this particular instance. The performance of purely sequential methods for computing HDs is inherently limited, yet the problem is, theoretically, amenable to parallelisation.

It is well known that the tractability of conjunctive query answering can be characterised in terms of treewidth when the problem is restricted to queries of bounded arity. We show that a similar characterisation also exists for classes of queries with unbounded arity and degree 2. To do so we introduce hypergraph dilutions as an alternative method to primal graph minors for studying substructures of hypergraphs. Using dilutions we observe an analogue to the Excluded Grid Theorem for degree 2 hypergraphs. In consequence, we show that that the tractability of conjunctive query answering can be characterised in terms of generalised hypertree width. A similar characterisation is also shown for the corresponding counting problem. We also generalise our main structural result to arbitrary bounded degree and discuss possible paths towards a characterisation of tractable conjunctive query answering for the bounded degree case.

Abstract Modern applications combine information from a great variety of sources. Oftentimes, some of these sources, like machine-learning systems, are not strictly binary but associated with some degree of (lack of) confidence in the observation. We propose MV-Datalog and $\mathrm{MV-Datalog}^\pm$ as extensions of Datalog and $\mathrm{Datalog}^\pm$ , respectively, to the fuzzy semantics of infinite-valued Łukasiewicz logic $\mathbf{L}$ as languages for effectively reasoning in scenarios where such uncertain observations occur. We show that the semantics of MV-Datalog exhibits similar model theoretic properties as Datalog. In particular, we show that (fuzzy) entailment can be decided via minimal fuzzy models. We show that when they exist, such minimal fuzzy models are unique and can be characterised in terms of a linear optimisation problem over the output of a fixed-point procedure. On the basis of this characterisation, we propose similar many-valued semantics for rules with existential quantification in the head, extending $\mathrm{Datalog}^\pm$ .

Numerous fundamental database and reasoning problems are known to be NP-hard in general but tractable on instances where the underlying hypergraph structure is β-acyclic. Despite the importance of many of these problems, there has been little success in generalizing these results beyond acyclicity. In this paper, we take on this challenge and propose nest-set width, a novel generalization of hypergraph β-acyclicity. We demonstrate that nest-set width has desirable properties and algorithmic significance. In particular, evaluation of boolean conjunctive queries with negation is tractable for classes with bounded nest-set width. Furthermore, propositional satisfiability is fixed-parameter tractable when parameterized by nest-set width.

Hypertree decompositions (HDs), as well as the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHDs) are hypergraph decomposition methods successfully used for answering conjunctive queries and for solving constraint satisfaction problems. Every hypergraph H has a width relative to each of these methods: its hypertree width hw(H) , its generalized hypertree width ghw(H) , and its fractional hypertree width fhw(H) , respectively. It is known that hw(H)≤ k can be checked in polynomial time for fixed k , while checking ghw(H)≤ k is NP-complete for k ≥ 3 . The complexity of checking fhw(H)≤ k for a fixed k has been open for over a decade. We settle this open problem by showing that checking fhw(H)≤ k is NP-complete, even for k=2 . The same construction allows us to prove also the NP-completeness of checking ghw(H)≤ k for k=2 . After that, we identify meaningful restrictions that make checking for bounded ghw or fhw tractable or allow for an efficient approximation of the fhw .

Constraint satisfaction problems (CSPs) are an important formal framework for the uniform treatment of various prominent AI tasks, e.g., coloring or scheduling problems. Solving CSPs is, in general, known to be NP-complete and fixed-parameter intractable when parameterized by their constraint scopes. We give a characterization of those classes of CSPs for which the problem becomes fixed-parameter tractable. Our characterization significantly increases the utility of the CSP framework by making it possible to decide the fixed-parameter tractability of problems via their CSP formulations. We further extend our characterization to the evaluation of unions of conjunctive queries, a fundamental problem in databases. Furthermore, we provide some new insight on the frontier of PTIME solvability of CSPs. In particular, we observe that bounded fractional hypertree width is more general than bounded hypertree width only for classes that exhibit a certain type of exponential growth. The presented work resolves a long-standing open problem and yields powerful new tools for complexity research in AI and database theory.