Abstract Practical SQL engines differ in subtle ways in their handling of typing constraints and implicit type casts. These issues, usually not considered in formal accounts of SQL, directly affect the portability of queries between engines. To understand this problem, we present a formal typing semantics for SQL, named $$\textsf{TRAF} $$ TRAF , that explicitly captures both static and dynamic type behavior. The system $$\textsf{TRAF} $$ TRAF is expressed in terms of abstract operators that provide the necessary leeway to precisely model different SQL engines (PostgreSQL, MS SQL Server, MySQL, SQLite, and Oracle). We show that this formalism provides formal guarantees regarding the handling of types. We provide practical conditions on engines to prove type safety and soundness of queries. In this regard, $$\textsf{TRAF} $$ TRAF can serve as precise documentation of typing in existing engines and potentially guide their evolution, as well as provide a formal basis to study type-aware query optimizations, and design provably-correct query translators. Additionally, we test the adequacy of the formalism, implementing $$\textsf{TRAF} $$ TRAF in Python for these five engines, and tested them with thousands of randomly-generated queries.

Graph databases have become an important data management technology across various domains, including biology, sociology, industry ( e.g . fraud detection, supply chain management, financial services), and investigative journalism, due to their ability to efficiently store and query large-scale knowledge graphs and networks. Recently, the Graph Query Language (GQL) was introduced as a new ISO standard providing a unified framework for querying graphs. However, this initial specification lacks a formal type system for query validation. As a result, queries can fail at runtime due to type inconsistencies or produce empty results without prior warning. Solving this issue would help users write correct queries, especially on large datasets. To address this gap, we introduce a formal type model for a core fragment of GQL extended with property-based filtering and imprecise types both in the schema and the queries. This model, named FPPC, enables static detection of semantically incorrect and stuck queries, improving user feedback. We establish key theoretical properties, including emptiness (detecting empty queries due to type mismatches) and type safety (guaranteeing that well-typed queries do not fail at runtime). Additionally, we prove a gradual guarantee , ensuring that removing type annotations either does not introduce static type errors or only increases the result set. By integrating imprecision into GQL, FPPC offers a flexible solution for handling schema evolution and incomplete type information. This work contributes to making GQL more robust, improving both its usability and its formal foundation.

Graphs have become the best way we know of representing knowledge. The computing community has investigated and developed the support for managing graphs by means of digital technology. Graph databases and knowledge graphs surface as the most successful solutions to this program. This tutorial will provide a conceptual map of the data management tasks underlying these developments, paying particular attention to data models and query languages for graphs

Knowledge Graphs can be considered as fulfilling an early vision in Computer Science of creating intelligent systems that integrate knowledge and data at large scale. Stemming from scientific advancements in research areas of Semantic Web, Databases, Knowledge representation, NLP, Machine Learning, among others, Knowledge Graphs have rapidly gained popularity in academia and industry in the past years. The integration of such disparate disciplines and techniques give the richness to Knowledge Graphs, but also present the challenge to practitioners and theoreticians to know how current advances develop from early techniques in order, on one hand, take full advantage of them, and on the other, avoid reinventing the wheel. This tutorial will provide a historical context on the roots of Knowledge Graphs grounded in the advancements of Logic, Data and the combination thereof.

Recent availability of data about writing processes at keystroke-granularity has enabled research on the evolution of document writing. A natural task is to develop systems that can actually show this data, that is, user interfaces that transform the data of the process of writing --today a black box-- into intelligible forms. On this line, we propose a data structure that captures a document's fine-grained history and an organic visualization that serves as an interface to it. We evaluate a proof-of-concept implementation of the system through a pilot study using documents written by students at a public university. Our results are promising and reveal facets such as general strategies adopted, local edition density and hierarchical structure of the final text.

We report on a community effort between industry and academia to shape the future of graph query languages. We argue that existing graph database management systems should consider supporting a query language with two key characteristics. First, it should be composable, meaning, that graphs are the input and the output of queries. Second, the graph query language should treat paths as first-class citizens. Our result is G-CORE, a powerful graph query language design that fulfills these goals, and strikes a careful balance between path query expressivity and evaluation complexity.

We study the network structure underlying dictionaries. We systematize the properties of such networks and show their relevance for linguistics. As case of study, we apply this technique to identify the graph structure of Ogden’s Basic English. We show that it constitutes a strong core of the English language network and that classic centrality measures fail to capture this set of words.

The Web of Linked Data is a huge graph of distributed and interlinked datasources fueled by structured information. This new environment calls for formal languages and tools to automatize navigation across datasources (nodes in such graph) and enable semantic-aware and Web-scale search mechanisms. In this article we introduce a declarative navigational language for the Web of Linked Data graph called N auti LOD. N auti LOD enables one to specify datasources via the intertwining of navigation and querying capabilities. It also features a mechanism to specify actions (e.g., send notification messages) that obtain their parameters from datasources reached during the navigation. We provide a formalization of the N auti LOD semantics, which captures both nodes and fragments of the Web of Linked Data. We present algorithms to implement such semantics and study their computational complexity. We discuss an implementation of the features of N auti LOD in a tool called swget, which exploits current Web technologies and protocols. We report on the evaluation of swget and its comparison with related work. Finally, we show the usefulness of capturing Web fragments by providing examples in different knowledge domains.

Censuses are one of the most relevant types of statistical data, allowing analyses of the population in terms of demography, economy, sociology, and culture. For fine‐grained analysis, census agencies publish census microdata that consist of a sample of individual records of the census containing detailed anonymous individual information. Working with microdata from different censuses and doing comparative studies are currently difficult tasks due to the diversity of formats and granularities. In this article, we show that novel data processing techniques can be applied to make census microdata interoperable and easy to access and combine. In fact, we demonstrate how Linked Open Data principles, a set of techniques to publish and make connections of (semi‐)structured data on the web, can be fruitfully applied to census microdata. We present a step‐by‐step process to achieve this goal and we study, in theory and practice, two real case studies: the 2001 Spanish census and a general framework for Integrated Public Use Microdata Series (IPUMS‐I).

The first digital computer for scientific and engineering applications was installed in Chile in 1962. It was an ER-56 Standard Elektrik Lorenz (“Lorenzo” by its Spanish nickname) made in Germany. It was acquired the Faculty of Physical and Mathematical Sciences of University of Chile. It was used in teaching, scientific and technological research, and in engineering projects of State and private enterprises. Its arrival installed automation and computers in the imaginary of Chilean society. Five years of intense use laid the foundation for the future development of the computing discipline in the country.

The massive semantic data sources linked in the Web of Data give new meaning to old features like navigation; introduce new challenges like semantic specification of Web fragments; and make it possible to specify actions relying on semantic data. In this paper we introduce a declarative language to face these challenges. Based on navigational features, it is designed to specify fragments of the Web of Data and actions to be performed based on these data. We implement it in a centralized fashion, and show its power and performance. Finally, we explore the same ideas in a distributed setting, showing their feasibility, potentialities and challenges.

In the paper, “semQA: SPARQL with Idempotent Disjunction”, the authors study the RDF query language SPARQL. In particular, they claim that some of the results presented in are not correct. In this note, we refute the claims made in, and actually show that some of the formal results of are incorrect.

This paper studies the compressibility of RDF data sets. We show that big RDF data sets are highly compressible due to the structure of RDF graphs (power law), organization of URIs and RDF syntax verbosity. We present basic approaches to compress RDF data and test them with three well-known, real-world RDF data sets.

SPARQL is the standard language for querying RDF data. In this article, we address systematically the formal study of the database aspects of SPARQL, concentrating in its graph pattern matching facility. We provide a compositional semantics for the core part of SPARQL, and study the complexity of the evaluation of several fragments of the language. Among other complexity results, we show that the evaluation of general SPARQL patterns is PSPACE-complete. We identify a large class of SPARQL patterns, defined by imposing a simple and natural syntactic restriction, where the query evaluation problem can be solved more efficiently. This restriction gives rise to the class of well-designed patterns. We show that the evaluation problem is coNP-complete for well-designed patterns. Moreover, we provide several rewriting rules for well-designed patterns whose application may have a considerable impact in the cost of evaluating SPARQL queries.

The resource description framework (RDF) is a metadata model and language recommended by the W3C. This paper presents a framework to incorporate temporal reasoning into RDF, yielding temporal RDF graphs. We present a semantics for these kinds of graphs which includes the notion of temporal entailment and a syntax to incorporate this framework into standard RDF graphs, using the RDF vocabulary plus temporal labels. We give a characterization of temporal entailment in terms of RDF entailment and show that the former does not yield extra asymptotic complexity with respect to nontemporal RDF graphs. We also discuss temporal RDF graphs with anonymous timestamps, providing a theoretical framework for the study of temporal anonymity. Finally, we sketch a temporal query language for RDF, along with complexity results for query evaluation that show that the time dimension preserves the tractability of answers

In multidimensional data models intended for online analytic processing (OLAP), data are viewed as points in a multidimensional space. Each dimension has structure, described by a directed graph of categories, a set of members for each category, and a child/parent relation between members. An important application of this structure is to use it to infer summarizability, that is, whether an aggregate view defined for some category can be correctly derived from a set of precomputed views defined for other categories. A dimension is called structurally heterogeneous if two members in a given category are allowed to have ancestors in different categories. In this article, we propose a class of integrity constraints, dimension constraints , that allow us to reason about summarizability in heterogeneous dimensions. We introduce the notion of frozen dimensions which are minimal homogeneous dimension instances representing the different structures that are implicitly combined in a heterogeneous dimension. Frozen dimensions provide the basis for efficiently testing the implication of dimension constraints and are a useful aid to understanding heterogeneous dimensions. We give a sound and complete algorithm for solving the implication of dimension constraints that uses heuristics based on the structure of the dimension and the constraints to speed up its execution. We study the intrinsic complexity of the implication problem and the running time of our algorithm.

The Semantic Web is based on the idea of adding more machine-readable semantics to web information via annotations written in a language called the Resource Description Framework (RDF). RDF resembles a subset of binary first-order logic including the ability to refer to anonymous objects. Its extended version, RDFS, supports reification, typing and inheritance. These features introduce new challenges into the formal study of sets of RDF/RDFS statements and languages for querying them. Although several such query languages have been proposed, there has been little work on foundational aspects. We investigate these, including computational aspects of testing entailment and redundancy. We propose a query language with well-defined semantics and study the complexity of query processing, query containment, and simplification of answers.

A common technique for speeding up OLAP query processing is to materialize (pre-compute) some aggregate views, called cube views, and use them for the derivation of other cube views. The derivations are inferred from the dimension hierarchies, and are usually represented as a relation between cube views called cube dependence relation, also called summarizability relation for a single dimension hierarchy. In this paper, we study the problem of computing the summarizability relation of dimension schemas that model structural irregularities of dimensions by means of integrity constraints. We study the intrinsic complexity of the problem, and present an algorithm, which uses deep structural properties of dimension hierarchies and constraints to solve the problem. Finally, we give an extension of the algorithm to compute the dependence relation for the multidimensional case.

We prove that the computational complexity of the problem of deciding if an equation in a free group has a solution is PSPACE. The problem was proved decidable in 1982 by Makanin, whose algorithm was proved later to be non primitive recursive: this was the best upper bound known for this problem. Our proof consists in reducing equations in free groups to equations in free semigroups with antiinvolution, and presenting an algorithm for deciding equations in free semigroups with antiinvolution. 1. INTRODUCTION Let \\Sigma = fa1 ; : : : ; ang be an alphabet. An equation in the free group G generated by \\Sigma with unknowns x1 ; : : : ; xm is an equality of the form w(x1 ; : : : ; xm ; a1 ; : : : ; an) = 1, where w is a word formed from the letters x1 ; : : : ; xm ; a1 ; : : : ; an and their inverses. A solution of such an equation is a list v1 ; : : : ; vm of words in a1 ; : : : ; an ; a \\Gamma1 1 ; : : : ; a \\Gamma1 n such that w(v1 ; : : : ; vm ; a1 ; : : : ; an) = 1 in the group ...

In this paper we study solvability of equations over free semigroups, known as word equations, particularly G.S. Makanin's algorithm (1977), a general procedure to decide if a word equation has a solution. The upper bound time-complexity of Makanin's original decision procedure was quadruple exponential in the length of the equation, as shown by Jaffar. A. Koscielski and L. Pacholski (1996) reduced it to triple exponential, and conjectured that it could be brought down to double exponential. The present paper proves this conjecture. In fact we prove the stronger fact that its space-complexity is single exponential.