Hybrid search, which integrates vector and structured retrieval, is essential for efficient and accurate information access over large-scale data in modern AI-based applications.We build upon HNSW, a state-of-the-art approximate nearest neighbor index for efficient hybrid search that organizes data in multi-layer proximity graphs.We exploit information from previously executed queries to inform new ones to start with the right foot-i.e., by selecting more effective entry points for the proximity graph exploration.This strategy accelerates convergence from the earliest search steps and improves accuracy.Finally, we experimentally evaluate our approach on six diverse datasets under varying settings, demonstrating consistent improvements.

This work addresses the problem of hybrid search in vector databases, which store vectors together with some property attributes. Given a query that consists of a vector and some restrictions on its property attributes, we want to retrieve approximate nearest neighbor vectors for the query while ensuring compliance with predicate conditions, such as point or range filters on a specific vector property attribute. The challenge is compounded by the need to balance two competing requirements: on one hand, ensuring high accuracy in the vector search by leveraging a similarity-based index that is independent of specific attributes, allowing it to serve all queries; on the other hand, the impracticality of replicating such a structure for each attribute or predicate condition. To address these challenges, we propose an agnostic, attribute popularity-aware solution for predicate filtering in approximate nearest neighbor (ANN) search, leveraging the efficiency of graph-based indexing structures for vectors. Our method begins by clustering nodes within the underlying graph structure and constructing lightweight in-memory sketches for the predicates. During query processing, the search selectively applies a two-hop traversal strategy only when necessary, guided by the attribute popularity within the identified cluster. Experimental evaluation across five benchmark datasets demonstrates that our approach consistently outperforms state-of-the-art methods.

The problems of Data Integration/Exchange (DE) and Ontology Based Data Access (OBDA) have been extensively studied across different communities. The underlying problem is common: using a number of differently structured data-sources mapped to a mediating schema/ontology/knowledge-graph, answer a query posed on the latter. In DE, forward-chaining algorithms, collectively known as the chase, transform source data to a new materialised instance that satisfies the ontology and can be directly queried. In OBDA, backward-chaining algorithms rewrite the query over the source schema, taking the ontology into account, in order to execute the rewriting directly on the sources. These two reasoning approaches have seen an individual rise in algorithms, practical implementations, and benchmarks. However, there has not been a principled methodology to compare solutions across both areas. In this paper we provide an original methodology and a benchmark infrastructure - a set of test scenarios, generator and translator tools, and an experimental infrastructure - to allow the translation and execution of a DE/OBDA scenario across areas and among different chase and query-rewriting systems. In the process, we also present a syntactic restriction of linear Tuple Generating Dependencies that precisely captures DL-Lite R , a correspondence previously uninvestigated. We perform cross-approach experiments under a wide range of assumptions, such as the use of different source-to-target mapping languages, shedding light to the interplay between forward-and backward-chaining. Our preliminary results show that, indeed, chase can compete and might overcome query rewriting even in the face of large data especially for complex mapping languages.

The Shapes Constraint Language (SHACL) is the recent W3C recommendation language for validating RDF data, by verifying certain shapes on graphs. Previous work has largely focused on the validation problem, while the standard decision problems of satisfiability and containment, crucial for design and optimisation purposes, have only been investigated for simplified versions of SHACL. Moreover, the SHACL specification does not define the semantics of recursively-defined constraints, which led to several alternative recursive semantics being proposed in the literature. The interaction between these different semantics and important decision problems has not been investigated yet. In this article we provide a comprehensive study of the different features of SHACL, by providing a translation to a new first-order language, called SCL, that precisely captures the semantics of SHACL. We also present MSCL, a second-order extension of SCL, which allows us to define, in a single formal logic framework, the main recursive semantics of SHACL. Within this language we also provide an effective treatment of filter constraints which are often neglected in the related literature. Using this logic we provide a detailed map of (un)decidability and complexity results for the satisfiability and containment decision problems for different SHACL fragments. Notably, we prove that both problems are undecidable for the full language, but we present decidable combinations of interesting features, even in the face of recursion.

Users have the right to consent to the use of their data, but current methods are limited to very coarse-grained expressions of consent, as "opt-in/opt-out" choices for certain uses. In this paper we identify the need for fine-grained consent management and formalize how to express and manage user consent and personal contracts of data usage in relational databases. Unlike privacy approaches, our focus is not on preserving confidentiality against an adversary, but rather cooperate with a trusted service provider to abide by user preferences in an algorithmic way. Our approach enables data owners to express the intended data usage in formal specifications, that we call consent constraints , and enables a service provider that wants to honor these constraints, to automatically do so by filtering query results that violate consent; rather than both sides relying on "terms of use" agreements written in natural language. We provide formal foundations (based on provenance), algorithms (based on unification and query rewriting), connections to data privacy, and complexity results for supporting consent in databases. We implement our framework in an open source RDBMS, and provide an evaluation against the most relevant privacy approach using the TPC-H benchmark, and on a real dataset of ICU data.

Generating value from data requires the ability to find, access and make sense of datasets. There are many efforts underway to encourage data sharing and reuse, from scientific publishers asking authors to submit data alongside manuscripts to data marketplaces, open data portals and data communities. Google recently beta-released a search service for datasets, which allows users to discover data stored in various online repositories via keyword queries. These developments foreshadow an emerging research field around dataset search or retrieval that broadly encompasses frameworks, methods and tools that help match a user data need against a collection of datasets. Here, we survey the state of the art of research and commercial systems and discuss what makes dataset search a field in its own right, with unique challenges and open questions. We look at approaches and implementations from related areas dataset search is drawing upon, including information retrieval, databases, entity-centric and tabular search in order to identify possible paths to tackle these questions as well as immediate next steps that will take the field forward.

Conjunctive-query containment is the problem of deciding whether the answers of a given conjunctive query on an arbitrary database instance are always contained in the answers of a second query on the same instance. This is a very relevant question in query optimization, data integration, and other data management and artificial intelligence areas. The problem has been deeply studied and understood for the, so-called, set-semantics, i.e., when query answers and database instances are modelled as sets of tuples. In particular, it has been shown by Chandra and Merlin to be NPTIME-COMPLETE. On the contrary, when investigated under bag-semantics, a.k.a. multiset semantics, which allows for replicated tuples both in the underlying instance and in the query answers, it is not even clear whether the problem is decidable. Since this is exactly the standard interpretation for commercial relational database systems, the question turns out to be an important one. Multiple works on variations and restrictions of the bag-containment problem have been reported in the literature and, although the general problem is still open, we contribute with this article by solving a special case that has been identified as a major open problem on its own. More specifically, we study projection-free queries, i.e., queries without existentially quantified variables, and show decidability for the bag-containment problem of a projection-free conjunctive query into a generic conjunctive query. We prove indeed that deciding containment in this setting is in ¶i^p_2. Our approach relies on the solution of a special case of the Diophantine inequality problem via a reduction to the linear inequality problem and clearly exposes inherent difficulties in the analysis of the general question.

The chase is a family of algorithms used in a number of data management tasks, such as data exchange, answering queries under dependencies, query reformulation with constraints, and data cleaning. It is well established as a theoretical tool for understanding these tasks, and in addition a number of prototype systems have been developed. While individual chase-based systems and particular optimizations of the chase have been experimentally evaluated in the past, we provide the first comprehensive and publicly available benchmark---test infrastructure and a set of test scenarios---for evaluating chase implementations across a wide range of assumptions about the dependencies and the data. We used our benchmark to compare chase-based systems on data exchange and query answering tasks with one another, as well as with systems that can solve similar tasks developed in closely related communities. Our evaluation provided us with a number of new insights concerning the factors that impact the performance of chase implementations.

We are interested in scalable data integration and data exchange under constraints/dependencies. In data exchange the problem is how to materialize a target database instance, satisfying the source-to-target and target dependencies, that provides the certain answers. In data integration, the problem is how to rewrite a query over the target schema into a query over the source schemas that provides the certain answers. In both these problems we make use of the chase algorithm, the main tool to reason with dependencies. Our first contribution is to introduce the frugal chase, which produces smaller universal solutions than the standard chase, still remaining polynomial in data complexity. Our second contribution is to use the frugal chase to scale up query answering using views under LAV weakly acyclic target constraints, a useful language capturing RDF/S. The latter problem can be reduced to query rewriting using views without constraints by chasing the source-to-target mappings with the target constraints. We construct a compact graph-based representation of the mappings and the constraints and develop an efficient algorithm to run the frugal chase on this representation. We show experimentally that our approach scales to large problems, speeding up the compilation of the dependencies into the mappings by close to 2 and 3 orders of magnitude, compared to the standard and the core chase, respectively. Compared to the standard chase, we improve online query rewriting time by a factor of 3, while producing equivalent, but smaller, rewritings of the original query.

In this paper we consider the problem of answering queries using views, which is important for data integration, query optimization, and data warehouses. We consider its simplest form, conjunctive queries and views, which already is NP-complete. Our context is data integration, so we search for maximally-contained rewritings. By looking at the problem from a graph perspective we are able to gain a better insight and develop an algorithm which compactly represents common patterns in the source descriptions, and (optionally) pushes some computation offline. This together with other optimizations result in an experimental performance about two orders of magnitude faster than current state-of-the-art algorithms, rewriting queries using over 10000 views within seconds.