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.
Haystack: A Platform for Authoring End User Semantic Web Applications
The Semantic Web promises to open innumerable opportunities for automation and information retrieval by standardizing the protocols for metadata exchange. However, just as the success of the World Wide Web can be attributed to the ease of use and ubiquity of Web browsers, we believe that the unfolding of the Semantic Web vision depends on users getting powerful but easy-to-use tools for managing their information. But unlike HTML, which can be easily edited in any text editor, RDF is more complicated to author and does not have an obvious presentation mechanism. Previous work has concentrated on the ideas of generic RDF graph visualization and RDF Schema-based form generation. In this paper, we present a comprehensive platform for constructing end user applications that create, manipulate, and visualize arbitrary RDF-encoded information, adding another layer to the abstraction cake. We discuss a programming environment specifically designed for manipulating RDF and introduce user interface concepts on top that allow the developer to quickly assemble applications that are based on RDF data models. Also, because user interface specifications and program logic are themselves describable in RDF, applications built upon our framework enjoy properties such as network updatability, extensibility, and end user customizability – all desirable characteristics in the spirit of the Semantic Web.
CompactLTJ: Space & Time Efficient Leapfrog Triejoin on Graph Databases
Leapfrog Triejoin (LTJ) is arguably the most practical and popular worst-case-optimal (wco) algorithm for solving basic graph patterns in graph databases. Its main drawback is that it needs the database triples (subject, predicate, object) represented as paths in a trie, for each of the six orders of subject, predicate, and object. The resulting blowup in space makes most systems disregard LTJ or implement it only partially, which makes their corresponding algorithms non-wco. In this paper we show that, by using compact data structures, it is possible to build an index that at the same time matches the query time performance of the fastest classic wco index, and uses a fraction of the space of non-wco indices (which are much slower). Concretely, we make use of compact tree representations to store functional tries using one bit per trie edge, instead of one pointer, and further reduce the space by storing partial tries. Our most compact variant uses 5–6 times less space than classic wco implementations and 2–3 times less than classic non-wco systems. At solving queries, it is on par with the fastest classic wco system, and 30–40 times faster than non-wco systems. We further incorporate improved query resolution strategies into CompactLTJ variants, which makes it considerably faster than classic wco systems as well, on queries that do not output too many results. Finally, we show how CompactLTJ can incorporate dynamism without altering its performance, even under very demanding update regimes. We leave a public fully-functional implementation of CompactLTJ that can be directly used by practitioners.
GraphQL
GraphQL is a query language designed to build client applications by providing an intuitive and flexible syntax and system for describing their data requirements and interactions.
Warnings for pattern matching
We examine the ML pattern-matching anomalies of useless clauses and non-exhaustive matches. We state the definition of these anomalies, building upon pattern matching semantics, and propose a simple algorithm to detect them. We have integrated the algorithm in the Objective Caml compiler, but we show that the same algorithm is also usable in a non-strict language such as Haskell. Or-patterns are considered for both strict and non-strict languages.
Semantic Data Modeling, Graph Query, and SQL, Together at Last?
Our teams advance the state of the art through research, systems engineering, and collaboration across Google.
Triple Pattern Fragments: a Low-cost Knowledge Graph Interface for the Web
Does this article spark your interest? Then we should work together!
Deep Dive into ParadeDB's v2 API: The Future of SQL Search
Explore ParadeDB's v2 API that eliminates schema duplication, simplifies tokenization, and provides transparent search operators for intuitive SQL-based full-text search.
Functorial data migration
In this paper we present a simple database definition language: that of categories and functors. A database schema is a small category and an instance is a set-valued functor on it. We show that morphisms of schemas induce three “data migration functors”, which translate instances from one schema to the other in canonical ways. These functors parameterize projections, unions, and joins over all tables simultaneously and can be used in place of conjunctive and disjunctive queries. We also show how to connect a database and a functional programming language by introducing a functorial connection between the schema and the category of types for that language. We begin the paper with a multitude of examples to motivate the definitions, and near the end we provide a dictionary whereby one can translate database concepts into category-theoretic concepts and vice versa.
Relational foundations for functorial data migration | Proceedings of the 15th Symposium on Database Programming Languages
In this paper we present a simple database definition language: that of categories and functors. A database schema is a small category and an instance is a set-valued functor on it. We show that morphisms of schemas induce three ''data migration ...
Functional Query Languages with Categorical Types
We study three category-theoretic types in the context of functional query languages (typed lambda-calculi extended with additional operations for bulk data processing). The types we study are:
OWL - Semantic Web Standards
The W3C Web Ontology Language (OWL) is a Semantic Web language designed to represent rich and complex knowledge about things, groups of things, and relations between things. OWL is a computational logic-based language such that knowledge expressed in OWL can be exploited by computer programs, e.g., to verify the consistency of that knowledge or to make implicit knowledge explicit. OWL documents, known as ontologies, can be published in the World Wide Web and may refer to or be referred from other OWL ontologies. OWL is part of the W3C’s Semantic Web technology stack, which includes RDF, RDFS, SPARQL, etc.
Making Databases Faster with LLM Evolutionary Sampling
Traditional query optimization relies on cost-based optimizers that estimate execution cost (e.g., runtime, memory, and I/O) using predefined heuristics and statistical models. Improving these heuristics requires substantial engineering effort, and even when implemented, these heuristics often cannot take into account semantic correlations in queries and schemas that could enable better physical plans. Using our DBPlanBench harness for the DataFusion engine, we expose the physical plan through a compact serialized representation and let the LLM propose localized edits that can be applied and executed. We then apply an evolutionary search over these edits to refine candidates across iterations. Our key insight is that LLMs can leverage semantic knowledge to identify and apply non-obvious optimizations, such as join orderings that minimize intermediate cardinalities. We obtain up to 4.78$\times$ speedups on some queries and we demonstrate a small-to-large workflow in which optimizations found on small databases transfer effectively to larger databases.
GraphRAG: A Practitioner's Guide to 6 Advanced Architectural Patterns
Beyond basic graph retrieval: six production-oriented architectures for combining semantic search, knowledge graphs, and LLM reasoning.
Specification of graph translators with triple graph grammars
Data integration is a key issue for any integrated set of software tools. A typical CASE environment, for instance, offers tools for the manipulation of requirements and software design documents, and it provides more or less sophisticated assistance for keeping these documents in a consistent state. Up to now, almost all data consistency observing or preserving integration tools are hand-crafted due to the lack of generic implementation frameworks and the absence of adequate specification formalisms. Triple graph grammars are intended to fill this gap and to support the specification of interdependencies between graph-like data structures on a very high level. Furthermore, they are the fundamentals of a new machinery for the production of batch-oriented as well as incrementally working data integration tools.
Introducing Cosette
Today we are thrilled to announce our official 1.0 release of Cosette, a SQL solver for automatically checking semantic equivalences of SQL…
Ologs: A Categorical Framework for Knowledge Representation
In this paper we introduce the olog, or ontology log, a category-theoretic model for knowledge representation (KR). Grounded in formal mathematics, ologs can be rigorously formulated and cross-compared in ways that other KR models (such as semantic networks) cannot. An olog is similar to a relational database schema; in fact an olog can serve as a data repository if desired. Unlike database schemas, which are generally difficult to create or modify, ologs are designed to be user-friendly enough that authoring or reconfiguring an olog is a matter of course rather than a difficult chore. It is hoped that learning to author ologs is much simpler than learning a database definition language, despite their similarity. We describe ologs carefully and illustrate with many examples. As an application we show that any primitive recursive function can be described by an olog. We also show that ologs can be aligned or connected together into a larger network using functors. The various methods of information flow and institutions can then be used to integrate local and global world-views. We finish by providing several different avenues for future research.