The development of discrimination-aware solutions is one of the main current research directions in the design of automated decision systems that make deep use of people-related data. Two main groups of techniques have been designed so far: the first focuses on fair machine learning, i.e., the development of algorithms that can detect and correct the bias in the context of a learning process; the second targets approaches for detecting and mitigating bias due to the under-representation of specific groups of people in the used dataset (representation bias), independently from the further analytical tasks to be executed. In both cases, bias can originate from how and where the data was originally collected or it can be introduced, sometimes amplified, during the data preparation steps preceding any analytical task. In this paper, we focus on representation bias and we present an approach for mitigating representation bias in datasets generated through data transformation, a specific data preparation phase. Differently from similar proposals, the proposed technique can mitigate bias defined in terms of multiple types of constraints, including coverage and fairness. To show the applicability of the proposed approach, we consider dropout prediction in the educational context as a case study. The preliminary reported experimental results show that the proposed technique can mitigate representation bias in an effective and efficient way.

The increasing impact of data-based decisions in education has risen concerns about the potential risk of an amplification of educational and societal inequities already implicit in existing data. Nondiscrimination can be characterized in terms of different properties (i.e., fairness, diversity, and coverage). Research mostly focused on fair machine learning, i.e., on the development of algorithms that can detect and, in some cases, correct bias. In this paper, we consider the case of dropout prediction and focus on coverage constraints. Specifically, with reference to this case study, we show why approaches are needed for guaranteeing nondiscrimination during all the steps of the data processing pipeline and discuss how a nondiscriminating pre-processing can be ensured by relying on coverage-based constraints on data transformations.

Many solutions for coarse geolocating of users at the time they post a message exist. However, for many important applications, like traffic monitoring and event detection, finer geolocation at the level of city neighborhoods, i.e., at a sub-city level, is needed. Data-driven approaches often do not guarantee good accuracy and efficiency due to the higher number of sub-city level positions to be estimated and the low availability of balanced and large training sets. We claim that external information sources overcome limitations of data-driven approaches in achieving good accuracy for sub-city level geolocation and we present a knowledge-driven approach achieving good results once the reference area of a message is known. Our algorithm, called Sherloc, exploits toponyms in the message, extracts their semantic from a geographic gazetteer, and embeds them into a metric space that captures the semantic distance among them. We identify the semantically closest toponyms to a message and then cluster them with respect to their spatial locations. Sherloc requires no prior training, it can infer the location at sub-city level with high accuracy, and it is not limited to geolocating on a fixed spatial grid.

Source selection deserves attention for live query processing over distributed, poorly controlled data sources since it is the key to produce the best available information, in terms of relevance, trustness, and freshness, as query result. In this paper, we present an approach taking into account contextdependent data quality, according to different dimensions, during source selection, with the aim of selecting not only the most relevant but also the highest quality sources.

XML documents are normally stored as plain text files. Hence, the natural and most convenient way to update XML documents is to simply edit the text files. But efficient query evaluation algorithms require XML documents to be indexed. Every element is given a unique identifier based on its location in the document or its preorder-traversal order, and this identifier is later used as (part of) the key in the index. Reassigning orders of possibly a large number of elements is therefore necessary when the original XML documents are updated. Immutable dynamic labeling schemes have been proposed to solve this problem, that, however, require very long labels and may decrease query performance. If we consider a real-world scenario, we note that many relatively small ad-hoc XML segments are inserted/deleted into/from an existing XML database. In this paper, we start from this consideration and we propose a new lazy approach to handle XML updates that also improves query performance. The lazy approach: (i) completely avoids reassigning existing element orders after updates; (ii) improves query processing by taking advantages from segments. Experimental results show that our approach is much more efficient in handling updates than using immutable labeling and, at the same time, it also improves the performance of recently defined structural join algorithms.

We consider the problem of indexing XML data for solving branching path expressions with the aim of reducing the number of joins to be executed and we propose a simple yet efficient join indexing approach to shrink the twig before applying any structural join algorithm. The indexing technique we propose, that we call XJoin Index, precomputes some structural (semi-)join results thus reducing the number of joins to be computed. Precomputed (semi-)joins support the following operations: (i) attribute selections, possibly involving several attributes; (ii) detection of parent-child relationships; (ii) counting selections, like Find all books with at least 3 authors. Unlike other approaches, based on specialized data structures XJoin Index is entirely based on B/sup +/-trees and can be coupled with any structural join algorithm proposed so far.

Peer-to-peer (P2P) technology can be naturally integrated with mobile agent technology in Internet applications, taking advantage of the autonomy, mobility, and efficiency of mobile agents in accessing and processing data. We address the problem of protecting critical information in agent-based P2P Internet applications under two different scenarios. First, we assume the route of a mobile agent in the P2P system is fixed. Under this assumption, we propose the usage of an efficient parallel dispatch model where the agent's route is signcrypted at the first step and dispatched to each new peer to collect information. Then, we assume the route is not specified and we propose the usage of a modified multi-signcryption scheme to guarantee protection. Based on this second approach, a mobile agent determines the next peer to communicate with independently and information is collected dynamically in one round of visiting a group of peers. Security issues under the two proposed models are then discussed.

Geographical maps can be represented and manipulated using different data models, each dealing with different map properties: geometrical properties, describing the shape, extension and location of the objects composing the map, combinatorial properties, interpreting the map as a set of disjoint elements satisfying a certain set of combinatorial constraints, and topological properties, describing the topological relationships existing among map objects. These different representations (that we call layers) are typically supported in most geographical systems. However, all existing systems are downward closed, meaning that if some information A is contained in the combinatorial (topological) layer, the information required to compute A must be contained in the geometrical (combinatorial/geometrical) layer. Several applications do not require this closure. Rather, they can benefit from the incomplete representation of the map. The aim of this paper is the definition of a reference framework for integrating various and possibly incomplete representations of geographical maps.

Static analysis of declarative languages deals with the detection, at compile time, of program properties that can be used to better understand the program semantics and to improve the efficiency of program evaluation. In logical update languages, an interesting problem is the detection of conflicting updates, inserting and deleting the same fact, for transactions based on set-oriented updates and active rules. In this paper, we investigate this topic in the context of the U-Datalog language, a set-oriented update language for deductive databases, based on a deferred semantics. We first formally define relevant properties of U-Datalog programs, mainly related to update conflicts. Then, we prove that the defined properties are decidable and we propose an algorithm to detect such conditions. Finally, we show how the proposed techniques can be applied to other logical update languages. Our results are based on the concept of labeling and query-tree.

The theory of amalgamated knowledge bases represents a formal logical foundation for heterogeneous databases. In an amalgamated knowledge base, data sources are modeled by generalized annotated logic. Moreover, an amalgamated knowledge base is equipped with a supervisor acting as a mediator for amalgamating knowledge from the local databases. Even if the framework is quite appealing, it does not model dynamic aspects. Moreover, no communication channels among local databases are supported and cooperation is provided only through the supervisor. In this paper, we extend the theory of amalgamated knowledge bases to deal with actions and cooperation among local databases.

Constraint databases have recently been proposed as a powerful framework to model and retrieve spatial data. The use of constraint databases should be supported by access data structures that make effective use of secondary storage and reduce query processing time. In this paper, we consider the indexing problem for objects represented by conjunctions of two-variable linear constraints and we analyze the problem of determining all generalized tuples whose extension intersects or is contained in the extension of a given half-plane. In an earlier paper we have shown that both selection problems can be reduced to a point location problem by using a dual transformation. If the angular coefficient of the half-plane belongs to a predefined set, we have proved that a dynamic optimal indexing solution, based on B/sup +/-trees, exists. In this paper we propose two approximation techniques that can be used to find the result when the angular coefficient does not belong to the predefined set. We also experimentally compare the proposed techniques with R-trees.

Linear constraint databases are a powerful framework to model spatial and temporal data. The use of constraint databases should be supported by access data structures that make effective use of secondary storage and reduce query processing time. Such structures should be able to store both finite and infinite objects and perform both containment (ALL) and intersection (EXIST) queries. As standard indexing techniques have certain limitations in satisfying such requirements, we employ the concept of geometric duality for designing new indexing techniques. In (Bertino et al., 1997) we have used the dual transformation for polyhedra to develop a dynamic optimal indexing solution based on B/sup +/-trees, to detect all objects contained in or intersecting a given half-plane, when the angular coefficient belongs to a predefined set. We extend the previous solution to allow angular coefficients to take any value. We present two approximation techniques for the dual representation of spatial objects, based on B/sup +/-trees. The techniques handle both finite and infinite objects and process both ALL and EXIST selections in a uniform way. We show the practical applicability of the proposed techniques by an experimental comparison with respect to R/sup +/-trees.

Constraint relational databases use constraints to both model and query data. A constraint relation contains a finite set of generalized tuples. Each generalized tuple is represented by a conjunction of constraints on a given logical theory and, depending on the logical theory and the specific conjunction of constraints, it may possibly represent an infinite set of relational tuples. For their characteristics, constraint databases are well suited to model multidimensional and structured data, like spatial and temporal data. The definition of an algebra for constraint relational databases is important in order to make constraint databases a practical technology. We extend the previously defined constraint algebra (called generalized relational algebra). First, we show that the relational model is not the only possible semantic reference model for constraint relational databases and we show how constraint relations can be interpreted under the nested relational model. Then, we introduce two distinct classes of constraint algebras, one based on the relational algebra, and one based on the nested relational algebra, and we present an algebra of the latter type. The algebra is proved equivalent to the generalized relational algebra when input relations are modified by introducing generalized tuple identifiers. However, from a user point of view, it is more suitable. Thus, the difference existing between such algebras is similar to the difference existing between the relational algebra and the nested relational algebra, dealing with only one level of nesting. We also show how external functions can be added to the proposed algebra.

Article Free Access Share on Static analysis of intensional databases in U-Datalog (extended abstract) Authors: Elisa Bertino University of Milano, Italy University of Milano, ItalyView Profile , Barbara Catania University of Milano, Italy University of Milano, ItalyView Profile Authors Info & Claims PODS '96: Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsJune 1996 Pages 202–212https://doi.org/10.1145/237661.237711Published:03 June 1996Publication History 6citation203DownloadsMetricsTotal Citations6Total Downloads203Last 12 Months5Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF