Search

Half a century ago, Charles Bachman foresaw the significance and centrality of data in the digital world. In this short paper, we delve into the evolution of these ideas within the database community over the past decades. We believe that this historical analysis helps deepen our comprehension of the fundamental changes undergoing our discipline and provides insights into the future trajectory of our field.

Mapuzugun is the language of the Mapuche people. Due to political and historical reasons, its number of speakers has decreased and the language has been excluded from the educational system in Chile and Argentina. For this reason, it is very important to support the revitalization of the Mapuzugun in all spaces and media of society. In this work we present a tool towards supporting educational activities of Mapuzugun, tailored to the characteristics of the language. The tool consists of three parts: design and development of an orthography detector and converter; a morphological analyzer; and an informal translator. We also present a case study with Mapuzugun students showing promising results. Short Abstract in Mapuzuzgun: T\"ufachi k\"uzaw pegelfi ki\~ne zugun k\"uzawpey\"um kelluaetew pu mapuzugun chillkatufe kimal kizu ta\~ni zugun., Comment: To be presented at the 17th Workshop on Innovative Use of NLP for Building Educational Applications

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. The goal of this document is to provide a conceptual map of the data management tasks underlying these developments, paying particular attention to data models and query languages for graphs.

In this paper we provide a comprehensive introduction to knowledge graphs, which have recently garnered significant attention from both industry and academia in scenarios that require exploiting diverse, dynamic, large-scale collections of data. After some opening remarks, we motivate and contrast various graph-based data models and query languages that are used for knowledge graphs. We discuss the roles of schema, identity, and context in knowledge graphs. We explain how knowledge can be represented and extracted using a combination of deductive and inductive techniques. We summarise methods for the creation, enrichment, quality assessment, refinement, and publication of knowledge graphs. We provide an overview of prominent open knowledge graphs and enterprise knowledge graphs, their applications, and how they use the aforementioned techniques. We conclude with high-level future research directions for knowledge graphs., Comment: Revision from v5: Correcting errata from previous version for entailment/models, and some other minor typos

Implementations of a standard language are expected to give same outputs to identical queries. In this paper we study why different implementations of SPARQL (Fuseki, Virtuoso, Blazegraph and rdf4j) behave differently when evaluating queries with correlated variables. We show that at the core of this problem lies the historically troubling notion of logical substitution. We present a formal framework to study this issue based on Datalog that besides clarifying the problem, gives a solid base to define and implement nesting.

A graph database is a database where the data structures for the schema and/or instances are modeled as a (labeled)(directed) graph or generalizations of it, and where querying is expressed by graph-oriented operations and type constructors. In this article we present the basic notions of graph databases, give an historical overview of its main development, and study the main current systems that implement them.

Recent availability of data of writing processes at keystroke-granularity has enabled research on the evolution of document writing. A natural step is to develop systems that can actually show this data and make it understandable. Here 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 with 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., Comment: 5 pages. Short paper accepted at the 23rd ACM Conference on Intelligent User Interfaces

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.

Reflections on the Concept of Data and its Implications for Science and Society, Comment: Notes for a talk at LEARN Final Conference, Economic Commission for Latin America and the Caribbean (ECLAC), Senate House, University of London, London, May 5th., 2017

The paper determines the algebraic and logic structure of the multiset semantics of the core patterns of SPARQL. We prove that the fragment formed by AND, UNION, OPTIONAL, FILTER, MINUS and SELECT corresponds precisely to both, the intuitive multiset relational algebra (projection, selection, natural join, arithmetic union and except), and the multiset non-recursive Datalog with safe negation., Comment: This is an extended and updated version of the paper accepted at the International Semantic Web Conference 2016

In the current SPARQL specification the notion of correlation and substitution are not well defined. This problem triggers several ambiguities in the semantics. In fact, implementations as Fuseki and Virtuoso assume different semantics. In this technical report, we provide a semantics of correlation and substitution following the classic philosophy of substitution and correlation in logic, programming languages and SQL. We think this proposal not only fix the current ambiguities and problems, but helps to set a safe formal base to further extensions of the language. This work is part of an ongoing work of Daniel Hernandez. These anomalies in the W3C Specification of SPARQL 1.1 were detected early and reported no later than 2014, when two erratas were registered (cf. https://www.w3.org/2013/sparql-errata#errata-query-8 and https://www.w3.org/2013/sparql-errata#errata-query-10).

This paper presents a thorough study of negation in SPARQL. The types of negation supported in SPARQL are identified and their main features discussed. Then, we study the expressive power of the corresponding negation operators. At this point, we identify a core SPARQL algebra which could be used instead of the W3C SPARQL algebra. Finally, we analyze the negation operators in terms of their compliance with elementary axioms of set theory., Comment: Proc. of the Alberto Mendelzon International Workshop on Foundations of Data Management (AMW'2016)

Group centrality is an extension of the classical notion of centrality for individuals, to make it applicable to sets of them. We perform a SWOT (strengths, weaknesses, opportunities and threats) analysis of the use of group centrality in semantic networks, for different centrality notions: degree, closeness, betweenness, giving prominence to random walks. Among our main results stand out the relevance and NP-hardness of the problem of finding the most central set in a semantic network for an specific centrality measure.

Criticism of the conference model should be put in context. Evidences suggest that the essential features of this model have emerged as responses to challenges posed by current trends of scientific research and the impact of the new techno-economic paradigm, the age of Information and Communication Technology. This context seems indispensable when discussing today's problems of scientific evaluation, in particular the Conference vs. Journal (CvJ) debate. This debate, also, would benefit from systematic historical and sociological studies of these practices. In this note we briefly develop these arguments., Comment: Written in 2010 / circulated privately / never published

Carlos Grandjot (1900-1979) was a German mathematician, doctorate from G\"ottingen, who moved to Chile in 1929 and developed there his life and career. He was influential in the development of Chilean mathematics during the period 1930 to 1960. This article reports our investigation of his biography and describes the mathematical environment in his new homeland., Comment: German translation by Karin Erxmeyer from the original Spanish published in "Bolet\'{\i}n de la Asociaci\'on Matem\'atica Venezolana, Vol. XI, No. 1 (2004)"

A map is an abstract visual representation of a region, taken from a given space, usually designed for final human consumption. Traditional cartography focuses on the mapping of Euclidean spaces by using some distance metric. In this paper we aim at mapping the Web space by leveraging its relational nature. We introduce a general mathematical framework for maps and an algebra and discuss the feasibility of maps suitable for interpretation not only by humans but also by machines.

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., Comment: 10 pages - first submission

SPARQL is the W3C candidate recommendation query language for RDF. In this paper we address systematically the formal study of SPARQL, concentrating in its graph pattern facility. We consider for this study a fragment without literals and a simple version of filters which encompasses all the main issues yet is simple to formalize. We provide a compositional semantics, prove there are normal forms, prove complexity bounds, among others that the evaluation of SPARQL patterns is PSPACE-complete, compare our semantics to an alternative operational semantics, give simple and natural conditions when both semantics coincide and discuss optimizations procedures.

It is known that the existential theory of equations in free groups is decidable. This is a famous result of Makanin. On the other hand it has been shown that the scheme of his algorithm is not primitive recursive. In this paper we present an algorithm that works in polynomial space, even in the more general setting where each variable has a rational constraint, that is, the solution has to respect a specification given by a regular word language. Our main result states that the existential theory of equations in free groups with rational constraints is PSPACE-complete. We obtain this result as a corollary of the corresponding statement about free monoids with involution., Comment: 45 pages. LaTeX source