Browsing by Author "Pieris, Andreas"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Absolute Expressiveness of Subgraph-Based Centrality Measures
    (Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023) Pieris, Andreas; Salas Cornejo, Jorge Eduardo
    In graph-based applications, a common task is to pinpoint the most important or “central” vertex in a (directed or undirected) graph, or rank the vertices of a graph according to their importance. To this end, a plethora of so-called centrality measures have been proposed in the literature. Such measures assess which vertices in a graph are the most important ones by analyzing the structure of the underlying graph. A family of centrality measures that are suited for graph databases has been recently proposed by relying on the following simple principle: the importance of a vertex in a graph is relative to the number of “relevant” connected subgraphs surrounding it; we refer to the members of this family as subgraph-based centrality measures. Although it has been shown that such measures enjoy several favourable properties, their absolute expressiveness remains largely unexplored. The goal of this work is to precisely characterize the absolute expressiveness of the family of subgraph-based centrality measures by considering both directed and undirected graphs. To this end, we characterize when an arbitrary centrality measure is a subgraph-based one, or a subgraph-based measure relative to the induced ranking. These characterizations provide us with technical tools that allow us to determine whether well-established centrality measures are subgraph-based. Such a classification, apart from being interesting in its own right, gives useful insights on the structural similarities and differences among existing centrality measures.
  • Thumbnail Image
    Item
    Expressive languages for querying the semantic web
    (2018) Arenas Saavedra, Marcelo Alejandro; Gottlob, Georg; Pieris, Andreas
  • Thumbnail Image
    Item
    On the expressiveness and structural properties of centrality measures
    (2024) Salas Cornejo, Jorge; Pieris, Andreas; Riveros Jaeger, Cristian; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    Centrality measures are used as analytical tools to understand graph-based data in various contexts. They are particularly useful for detecting important agents in disease spreading, influential individuals in social networks, or political decisionmakers. This is primarily due to the diversity of measures and their potential for exploitation in theoretical analyses. However, there exists a gap in the understanding of centrality from a foundational perspective. In this thesis, we provide an in-depth study of centrality measures from two different angles. Firstly, we examine how centralities behave over trees. Due to the simple structure of trees, it is easier to analyze each centrality measure in a restricted setting. We introduce the rooting tree property and propose a framework of potential functions to characterize rooting measures. In the last two Chapters, we present a novel study of the family of subgraph-based centralities (SBMs), which serve as a general framework for developing new measures. To define an SBM, we select a set of important subgraphs relevant to a specific application. The most important vertices are then determined based on the number of important subgraphs surrounding them. Initially, we investigate the absolute and ranking expressiveness of SBMs, answering the question of when an arbitrary centrality measure can be defined as an SBM. This, in turn, allows us to compare commonly used centralities within the scope of SBMs. Finally, we conduct an experimental study of important subgraph-based measures, as well as commonly used measures, using statistical scores such as Pearson correlation, ranking distances, and similarities to identify evidence of closely related measures.
  • No Thumbnail Available
    Item
    Semantic Optimization of Conjunctive Queries
    (2020) Barcelo, Pablo; Figueira, Diego; Gottlob, Georg; Pieris, Andreas
    This work deals with the problem of semantic optimization of the central class of conjunctive queries (CQs). Since CQ evaluation is NP-complete, a long line of research has focussed on identifying fragments of CQs that can be efficiently evaluated. One of the most general restrictions corresponds to generalized hypetreewidth bounded by a fixed constant k >= 1; the associated fragment is denoted GHW(k). A CQ is semantically in GHW(k) if it is equivalent to a CQ in GHW(k). The problem of checking whether a CQ is semantically in GHW(k) has been studied in the constraint-free case, and it has been shown to be NP-complete. However, in case the database is subject to constraints such as tuple-generating dependencies (TGDs) that can express, e.g., inclusion dependencies, or equality-generating dependencies (EGDs) that capture, e.g., key dependencies, a CQ may turn out to be semantically in GHW(k) under the constraints, while not being semantically in GHW(k) without the constraints. This opens avenues to new query optimization techniques. In this article, we initiate and develop the theory of semantic optimization of CQs under constraints. More precisely, we study the following natural problem: Given a CQ and a set of constraints, is the query semantically in GHW(k), for a fixed k >= 1, under the constraints, or, in other words, is the query equivalent to one that belongs to GHW(k) over all those databases that satisfy the constraints? We show that, contrary to what one might expect, decidability of CQ containment is a necessary but not a sufficient condition for the decidability of the problem in question. In particular, we show that checking whether a CQ is semantically in GHW1 is undecidable in the presence of full TGDs (i.e., Datalog rules) or EGDs. In view of the above negative results, we focus on the main classes of TGDs for which CQ containment is decidable and that do not capture the class of full TGDs, i.e., guarded, non-recursive, and sticky sets of TGDs, and show that the problem in question is decidable, while its complexity coincides with the complexity of CQ containment. We also consider key dependencies over unary and binary relations, and we show that the problem in question is decidable in elementary time. Furthermore, we investigate whether being semantically in GHW(k) alleviates the cost of query evaluation. Finally, in case a CQ is not semantically in GHW(k), we discuss how it can be approximated via a CQ that falls in GHW(k) in an optimal way. Such approximations might help finding "quick" answers to the input query when exact evaluation is intractable.