Deductive rules over graph data are a commonly accepted way to address complex reasoning tasks; among them, we mention the company control problem, which consists of determining who exercises control - directly or indirectly, through aggregation and recursion - over ownership graphs. Solving this and similar problems is crucial for the Central Bank of Italy; the Bank uses Vadalog, a state-of-the-art proprietary reasoner based on an extended Datalog, to routinely manage changes (insertions and deletions) of ownership in large graphs covering all Italian companies. However, at a smaller scale, similar activities are also relevant in more targeted activities, e.g., for financial intelligence tasks in the public and private sectors. In this paper, we present a general scheme for generating active rules that correctly handle recursion, aggregation, and stratified negation, so as to deploy reactive reasoners over graph data managers. We show how to convert high-level reasoning rules expressed in Datalog into triggers as Cypher statements, the most aligned language with the recently standardized Graph Query Language. We discuss how Cypher triggers can be managed by a dedicated controller that replicates the reasoning capabilities of a deductive reasoner engine within a graph database system. We implement the controller within Neo4j, the most widespread open-source graph database, demonstrating that our implementation achieves adequate performance over small-to-medium property graphs. We also show that our approach is general and applicable to other domains (e.g., laws), directly allowing reasoning with deductive rules over graph databases. Finally, we discuss how the translation process from Datalog to Cypher can be facilitated by state-of-the-art pre-trained Large Language Models, capable of accurately performing the translation task.

In many recommendation applications, items may have limited availability thereby causing conflict among users interested in the same items. Over time, this results in unequal user treatment: few users are recommended the limited items and receive preferential treatment, while the rest is left with sub-optimal recommendations, ultimately leading them to leave. In this paper, we formalize the novel problem of compensating users in multi-session recommendations under limited item availability. Our aim is to generate recommendations that not only optimize accuracy, but also compensate users over time for the loss of accuracy incurred in previous iterations. We design compensation strategies that serve users and items in different orders and accommodate various recommendation adoption models. Our algorithms are integrated into SoCRATe (System for Compensating Recommendations with Availability and Time), a framework that enables us to study loss compensation over time. Our experiments on real data demonstrate that to best compensate users for the incurred loss, traditional recommenders need to be revisited to account for item availability. Our experiments on synthetic data explore different parameters of our solution and show that it is much faster than an optimal (brute-force) compensation strategy, while achieving comparable results.

Top- k queries, in particular those based on a linear scoring function, are a common way to extract relevant results from large datasets. Their major advantage over alternative approaches, such as skyline queries (which return all the undominated objects in a dataset), is that the cardinality of the output can be easily controlled through the k parameter and user preferences can be accommodated by appropriately weighing the involved attributes. In this paper we concentrate on two so-far neglected aspects of top- k queries: first, their general ability to return all the potentially interesting results, i.e., the tuples in the skyline; second, the difficulty that linear top- k queries might encounter in returning tuples with balanced attribute values that match user preferences more closely than tuples that are extremely good in one dimension but (very) poor in others. In order to quantify these undesirable effects we introduce four novel indicators for skyline tuples, which measure their robustness as well as the difficulty incurred by top-k queries to retrieve them. After observing that real datasets usually contain many relevant results that are hardly retrievable by linear top- k queries, and with the aim of favoring balanced results, we extend the queries with a term that accounts for the distance of a tuple from the preference direction established by the attributes' weights. This novel query, which we call directional query, adds the flexibility needed to allow each skyline tuple to be ranked first for a proper choice of weights, with no extra burden on the user and, in the most adverse scenarios, only a minor computational overhead, as measured through an extensive experimental analysis on real and synthetic data.

The Company Control Problem consists in understanding who exerts decision power in companies. Central banks, financial intelligence units, and market regulators are all interested in this problem, which is crucial for their core goals. In the context where these actors operate, changes in company control call for immediate reactions.Yet, computing control relationships is a computationally expensive problem that involves traversing the entire shareholding structure and aggregating shares over multiple paths.In the context of the joint European banking supervision, the Bank of Italy will soon handle the shareholding graph of all European companies, which comprises hundreds of millions of entities (firms and individuals) and billions of edges and properties. This graph is highly volatile as the Bank continuously receives updates about shareholding relationships with unpredictable high frequency. This makes the straightforward bulk solution, where all the company control relationships are computed and materialized whenever a change occurs, unaffordable in practice.In this work, we present an incremental rule-based formalization of the problem, adopting the Vadalog fragment of the Datalog+/- families of languages. Our approach analyzes the specific change, singles out the portions of the graph that are affected by it, and selectively updates them. This allows one both to timely evaluate the impact of ownership variations on an extensive European-scale shareholding graph and to enable economists to perform the so-called "what-if analysis", i.e., simulation scenarios to proactively study the consequences of potential share acquisition operations, that currently are prohibitively time expensive. We provide an extensive experimental evaluation on very large company graphs, comparatively confirming the scalability of our technique in a real production setting.

We demonstrate SoCRATe, an online system dedicated to providing adaptive recommendations to users when items have limited availability. SoCRATe is relevant to several real-world applications, among which movie and task recommendations. SoCRATe has several appealing features: (i) watching users as they consume recommendations and accounting for user feedback in refining recommendations in the next round; (ii) implementing loss compensation strategies to make up for sub-optimal recommendations, in terms of accuracy, when items have limited availability; (iii) deciding when to re-generate recommendations on a need-based fashion. SoCRATe accommodates real users as well as simulated users to enable testing multiple recommendation choice models. To frame evaluation, SoCRATe introduces a new set of measures that capture recommendation accuracy, user satisfaction and item consumption over time. All these features make SoCRATe unique and able to adapt recommendations to user preferences in a resource-limited setting. A video of SoCRATe is available at https://youtu.be/4wlaScc_rUo.

When composing multiple preferences characterizing the most suitable results for a user, several issues may arise. Indeed, preferences can be partially contradictory, suffer from a mismatch with the level of detail of the actual data, and even lack natural properties such as transitivity. In this paper we formally investigate the problem of retrieving the best results complying with multiple preferences expressed in a logic-based language. Data are stored in relational tables with taxonomic domains, which allow the specification of preferences also over values that are more generic than those in the database. In this framework, we introduce two operators that rewrite preferences for enforcing the important properties of transitivity, which guarantees soundness of the result, and specificity, which solves all conflicts among preferences. Although, as we show, these two properties cannot be fully achieved together, we use our operators to identify the only two alternatives that ensure transitivity and minimize the residual conflicts. Building on this finding, we devise a technique, based on an original heuristics, for selecting the best results according to the two possible alternatives. We finally show, with a number of experiments over both synthetic and real-world datasets, the effectiveness and practical feasibility of the overall approach.

Skyline and ranking queries are two popular, alternative ways of discovering interesting data in large datasets. Skyline queries are simple to specify, as they just return the set of all non-dominated tuples, thereby providing an overall view of potentially interesting results. However, they are not equipped with any means to accommodate user preferences or to control the cardinality of the result set. Ranking queries adopt, instead, a specific scoring function to rank tuples, and can easily control the output size. While specifying a scoring function allows one to give different importance to different attributes by means of, e.g., weight parameters, choosing the “right” weights to use is known to be a hard problem. In this article, we embrace the skyline approach by introducing an original framework able to capture user preferences by means of constraints on the weights used in a scoring function, which is typically much easier than specifying precise weight values. To this end, we introduce the novel concept of F-dominance , i.e., dominance with respect to a family of scoring functions F : a tuple t is said to F -dominate tuple s when t is always better than or equal to s according to all the functions in F . Based on F -dominance, we present two flexible skyline (F-skyline) operators, both returning a subset of the skyline: nd , characterizing the set of non- F -dominated tuples; po , referring to the tuples that are also potentially optimal, i.e., best according to some function in F . While nd and po coincide and reduce to the traditional skyline when F is the family of all monotone scoring functions, their behaviors differ when subsets thereof are considered. We discuss the formal properties of these new operators, show how to implement them efficiently, and evaluate them on both synthetic and real datasets.

Most scientific databases consist of datasets (or sources) which in turn include samples (or files) with an identical structure (or schema). In many cases, samples are associated with rich metadata, describing the process that leads to building them (e.g.: the experimental conditions used during sample generation). Metadata are typically used in scientific computations just for the initial data selection; at most, metadata about query results is recovered after executing the query, and associated with its results by post-processing. In this way, a large body of information that could be relevant for interpreting query results goes unused during query processing. In this paper, we present ScQL, a new algebraic relational language, whose operations apply to objects consisting of data–metadatapairs, by preserving such one-to-one correspondence throughout the computation. We formally define each operation and we describe an optimization, called meta-first , that may significantly reduce the query processing overhead by anticipating the use of metadata for selectively loading into the execution environment only those input samples that contribute to the result samples. In ScQL, metadata have the same relevance as data, and contribute to building query results; in this way, the resulting samples are systematically associated with metadata about either the specific input samples involved or about query processing, thereby yielding a new form of metadata provenance . We present many examples of use of ScQL, relative to several application domains, and we demonstrate the effectiveness of the meta-first optimization. • ScQL: a metadata aware query language for databases of scientific samples. • ScQL is compiled to a lower level representation suitable for optimization. • The novel meta-first optimization exploits metadata so as to speed up query evaluation.

The problem of aggregating scores, so as to provide a ranking of objects in a dataset according to different evaluation criteria, is central to many modern data-intensive applications. Although efficient (instance optimal) algorithms exist to this purpose (such as the Threshold Algorithm TA and its variants) none of them is able to deal with scenarios in which the function used to aggregate scores is only partially specified. This is the typical case when the function is a weighted sum, and the user is unable to provide precise values for the weights. In this paper, we consider the problem of processing multi-source top-k queries, when only constraints, rather than precise values, are available for the weights. After observing that the so-called Fagin's Algorithm (FA) can be adapted to solve the problem, yet only when no constraints at all are present (a case in which our queries will return the k-skyband of the dataset), we introduce the novel FSA algorithm, which we prove to be instance optimal for any set of constraints on the weights. We also propose several optimizations to the basic FSA logic so as to improve execution times. Experimental analysis on both real and synthetic datasets shows that our optimizations are indeed highly effective and that the increased flexibility provided by FSA introduces little overhead with respect to the case of classical top-k queries.

Traditionally, skyline and ranking queries have been treated separately as alternative ways of discovering interesting data in potentially large datasets. While ranking queries adopt a specific scoring function to rank tuples, skyline queries return the set of non-dominated tuples and are independent of attribute scales and scoring functions. Ranking queries are thus less general, but usually cheaper to compute and widely used in data management systems. We propose a framework to seamlessly integrate these two approaches by introducing the notion of restricted skyline queries (R-skylines). We propose R-skyline operators that generalize both skyline and ranking queries by applying the notion of dominance to a set of scoring functions of interest. Such sets can be characterized, e.g., by imposing constraints on the function's parameters, such as the weights in a linear scoring function. We discuss the formal properties of these new operators, show how to implement them efficiently, and evaluate them on both synthetic and real datasets.

Both social media and sensing infrastructures are producing an unprecedented mass of data characterized by their uncertain nature, due to either the noise inherent in sensors or the imprecision of human contributions. Therefore query processing over uncertain data has become an active research field. In the well-known class of applications commonly referred to as “top-K queries”, the objective is to find the best K objects matching the user's information need, formulated as a scoring function over the objects' attribute values. If both the data and the scoring function are deterministic, the best K objects can be univocally determined and totally ordered so as to produce a single ranked result set (as long as ties are broken by some deterministic rule). However, in application scenarios involving uncertain data and fuzzy information needs, this does not hold: when either the attribute values or the scoring function are nondeterministic, there may be no consensus on a single ordering, but rather a space of possible orderings. To determine the correct ordering, one needs to acquire additional information so as to reduce the amount of uncertainty associated with the queried data and consequently the number of orderings in such a space. An emerging trend in data processing is crowdsourcing, defined as the systematic engagement of humans in the resolution of tasks through online distributed work. Our approach combines human and automatic computation in order to solve complex problems: when data ambiguity can be resolved by human judgment, crowdsourcing becomes a viable tool for converging towards a unique or at least less uncertain query result. The goal of this paper is to define and compare task selection policies for uncertainty reduction via crowdsourcing, with emphasis on the case of top-K queries.

Querying uncertain data has become a prominent application due to the proliferation of user-generated content from social media and of data streams from sensors. When data ambiguity cannot be reduced algorithmically, crowdsourcing proves a viable approach, which consists of posting tasks to humans and harnessing their judgment for improving the confidence about data values or relationships. This paper tackles the problem of processing top-K queries over uncertain data with the help of crowdsourcing for quickly converging to the realordering of relevant results. Several offline and online approaches for addressing questions to a crowd are defined and contrasted on both synthetic and real data sets, with the aim of minimizing the crowd interactions necessary to find the realordering of the result set.

Despite the success of crowdsourcing marketplaces, fully harnessing their massive workforce remains challenging. In this work we study the effect on crowdsourcing campaigns of different feedback and payment strategies. Our results reveal the joint effect of feedback and payment on the quality and quantity of the outcome.

The possibility of assigning labels to localized regions in an image enables flexible image retrieval paradigms. However, the process of automatically segmenting and tagging images is notoriously hard, due to the presence of occlusions, noise, challenging illumination conditions, background clutter, etc. For this reason, human computation has recently emerged as a viable alternative when computer vision algorithms fail to provide a satisfactory answer. For example, Games with a purpose (GWAP) represent a powerful crowdsourcing mechanism to collect implicit annotations from human players. In this paper we consider the problem of aggregating the gaming tracks collected by a GWAP we developed to solve challenging instances of image segmentation problems. In particular we consider the existence of malicious players, who might try to fool the rules of the game to achieve higher rewards. The proposed solution can automatically estimate the reliability of human players, thus identifying cheaters. This information is exploited to aggregate the gaming tracks, thus significantly improving the image segmentation result and the quality of local image annotations.

Top-k diversity queries over objects embedded in a low-dimensional vector space aim to retrieve the best k objects that are both relevant to given user's criteria and well distributed over a designated region. An interesting case is provided by spatial Web objects, which are produced in great quantity by location-based services that let users attach content to places and are found also in domains like trip planning, news analysis, and real estate. In this article we present a technique for addressing such queries that, unlike existing methods for diversified top- k queries, does not require accessing and scanning all relevant objects in order to find the best k results. Our Space Partitioning and Probing (SPP) algorithm works by progressively exploring the vector space, while keeping track of the already seen objects and of their relevance and position. The goal is to provide a good quality result set in terms of both relevance and diversity. We assess quality by using as a baseline the result set computed by MMR, one of the most popular diversification algorithms, while minimizing the number of accessed objects. In order to do so, SPP exploits score-based and distance-based access methods, which are available, for instance, in most geo-referenced Web data sources. Experiments with both synthetic and real data show that SPP produces results that are relevant and spatially well distributed, while significantly reducing the number of accessed objects and incurring a very low computational overhead.

This paper investigates diversity queries over objects embedded in a low-dimensional vector space. An interesting case is provided by spatial Web objects, which are produced in great quantity by location-based services that let users attach content to places, and arise also in trip planning, news analysis, and real estate scenarios. The targeted queries aim at retrieving the best set of objects relevant to given user criteria and well distributed over a region of interest. Such queries are a particular case of diversified top-k queries, for which existing methods are too costly, as they evaluate diversity by accessing and scanning all relevant objects, even if only a small subset is needed. We therefore introduce Space Partitioning and Probing (SPP), an algorithm that minimizes the number of accessed objects while finding exactly the same result as MMR, the most popular diversification algorithm. SPP belongs to a family of algorithms that rely only on score-based and distance-based access methods, which are available in most geo-referenced Web data sources, and do not require retrieving all the relevant objects. Experiments show that SPP significantly reduces the number of accessed objects while incurring a very low computational overhead.

In this paper, we address the problem of joining ranked results produced by two or more services on the web. We consider services endowed with two kinds of access that are often available: 1) sorted access, which returns tuples sorted by score; 2) random access, which returns tuples matching a given join attribute value. Rank join operators combine objects of two or more relations and output the k combinations with the highest aggregate score. While the past literature has studied suitable bounding schemes for this setting, in this paper we focus on the definition of a pulling strategy, which determines the order of invocation of the joined services. We propose the Cost-Aware with Random and Sorted access (CARS) pulling strategy, which is derived at compile-time and is oblivious of the query-dependent score distributions. We cast CARS as the solution of an optimization problem based on a small set of parameters characterizing the joined services. We validate the proposed strategy with experiments on both real and synthetic data sets. We show that CARS outperforms prior proposals and that its overall access cost is always within a very short margin from that of an oracle-based optimal strategy. In addition, CARS is shown to be robust w.r.t. the uncertainty that may characterize the estimated parameters.

We introduce the proximity rank join problem, where we are given a set of relations whose tuples are equipped with a score and a real-valued feature vector. Given a target feature vector, the goal is to return the K combinations of tuples with high scores that are as close as possible to the target and to each other, according to some notion of distance or dissimilarity. The setting closely resembles that of traditional rank join, but the geometry of the vector space plays a distinctive role in the computation of the overall score of a combination. Also, the input relations typically return their results either by distance from the target or by score. Because of these aspects, it turns out that traditional rank join algorithms, such as the well-known HRJN , have shortcomings in solving the proximity rank join problem, as they may read more input than needed. To overcome this weakness, we define a tight bound (used as a stopping criterion) that guarantees instance optimality, that is, an I/O cost is achieved that is always within a constant factor of optimal. The tight bound can also be used to drive an adaptive pulling strategy, deciding at each step which relation to access next. For practically relevant classes of problems, we show how to compute the tight bound efficiently. An extensive experimental study validates our results and demonstrates significant gains over existing solutions.

Ranking queries report the top-K results according to a user-defined scoring function. A widely used scoring function is the weighted summation of multiple scores. Often times, users cannot precisely specify the weights in such functions in order to produce the preferred order of results. Adopting uncertain/incomplete scoring functions (e.g., using weight ranges and partially-specified weight preferences) can better capture user's preferences in this scenario.

All methods for efficient integrity checking require all integrity constraints to be totally satisfied, before any update is executed. However, a certain amount of inconsistency is the rule, rather than the exception in databases. In this paper, we close the gap between theory and practice of integrity checking, i.e., between the unrealistic theoretical requirement of total integrity and the practical need for inconsistency tolerance, which we define for integrity checking methods. We show that most of them can still be used to check whether updates preserve integrity, even if the current state is inconsistent. Inconsistency-tolerant integrity checking proves beneficial both for integrity preservation and query answering. Also, we show that it is useful for view updating, repairs, schema evolution, and other applications.

The term Deep Web (sometimes also called Hidden Web) refers to the data content that is created dynamically as the result of a specific search on the Web. In this respect, such content resides outside web pages, and is only accessible through interaction with the web site - typically via HTML forms. It is believed that the size of the Deep Web is several orders of magnitude larger than that of the so-called Surface Web, i.e., the web that is accessible and indexable by search engines.

Data stored outside Web pages and accessible from the Web, typically through HTML forms, consitute the so-called Deep Web. Such data are of great value, but difficult to query and search. We survey techniques to optimize query processing on the Deep Web, in a setting where data are represented in the relational model. We illustrate optimizations both at query plan generation time and at runtime, highlighting the role of integrity constraints. We discuss several prototype systems that address the query processing problem.

We introduce the proximity rank join problem, where we are given a set of relations whose tuples are equipped with a score and a real-valued feature vector. Given a target feature vector, the goal is to return the K combinations of tuples with high scores that are as close as possible to the target and to each other, according to some notion of distance. The setting closely resembles that of traditional rank join, but the geometry of the vector space plays a distinctive role in the computation of the overall score of a combination. Also, the input relations typically return their results either by distance from the target or by score. Because of these aspects, it turns out that traditional rank join algorithms, such as the well-known HRJN , have shortcomings in solving the proximity rank join problem, as they may read more input than needed. To overcome this weakness, we define a tight bound (used as a stopping criterion) that guarantees instance optimality, i.e., an I/O cost is achieved that is always within a constant factor of optimal. The tight bound can also be used to drive an adaptive pulling strategy, deciding at each step which relation to access next. For practically relevant classes of problems, we show how to compute the tight bound efficiently. An extensive experimental study validates our results and demonstrates significant gains over existing solutions.

Data sources on the web are often accessible through web interfaces that present them as relational tables, but require certain attributes to be mandatorily selected, e.g., via a web form. In a scenario where we integrate a set of such sources, and we pose queries over them, the values needed to access a source may have to be retrieved from other sources that are possibly not even mentioned in the query: answering queries at best can then be done only with a potentially recursive query plan that gets all obtainable answers to the query. Since data sources are typically distributed over a network, a major cost indicator for the execution of a query plan is the number of accesses to remote sources. In this paper we present an optimization technique for conjunctive queries that produces a query plan that: (1) minimizes the number of accesses according to a strong notion of minimality; (2) excludes all sources that are not relevant for the query. We introduce Toorjah, a prototype system that answers queries posed on sources with limitations by means of optimized query plans. Toorjah adopts a strategy that is aimed to retrieve answers as early as possible during query processing, and to present them to the user as they are computed. We provide experimental evidence of the effectiveness of our optimization, by showing the reduction of the number of accesses in a large number of cases.

Where can I attend an interesting database workshop close to a sunny beach? Who are the strongest experts on service computing based upon their recent publication record and accepted European projects? Can I spend an April weekend in a city served by a low-cost direct flight from Milano offering a Mahler's symphony? We regard the above queries as multi-domain queries, i.e., queries that can be answered by combining knowledge from two or more domains (such as: seaside locations, flights, publications, accepted projects, conference offerings, and so on). This information is available on the Web, but no general-purpose software system can accept the above queries nor compute the answer. At the most, dedicated systems support specific multi-domain compositions (e.g., Google-local locates information such as restaurants and hotels upon geographic maps). This paper presents an overall framework for multi-domain queries on the Web. We address the following problems: (a) expressing multi-domain queries with an abstract formalism, (b) separating the treatment of "search" services within the model, by highlighting their differences from "exact" Web services, (c) explaining how the same query can be mapped to multiple "query plans", i.e., a well-defined scheduling of service invocations, possibly in parallel, which complies with their access limitations and preserves the ranking order in which search services return results; (d) introducing cross-domain joins as first-class operation within plans; (e) evaluating the query plans against several cost metrics so as to choose the most promising one for execution. This framework adapts to a variety of application contexts, ranging from end-user-oriented mash-up scenarios up to complex application integration scenarios.