Abstract Conventional database systems function as static data repositories, storing vast amounts of facts and offering efficient query processing capabilities. The sheer volume of data these systems store has a direct impact on their scalability, both in terms of storage space and query processing time. Deductive database systems, on the other hand, require far less storage space since they derive new knowledge by applying inference rules. The challenge is how to efficiently obtain the required derivations, compared to having them in explicit form. In this study, we concentrate on a set of predefined inference rules for subsumption and disjointness relations, including their negations. We use compact data structures to store the facts and provide algorithms to support each type of relation, minimizing even further the storage space requirements. Our experimental findings demonstrate the feasibility of this approach, which not only saves space but is often faster than a baseline that uses well‐known graph traversal algorithms implemented on top of a traditional adjacency list representation to derive the relations.

Microservices architecture advocates decentralized data ownership for building software systems. Particularly, in the Database per Service pattern, each microservice is supposed to maintain its own database and to handle the data related to its functionality. When implementing microservices in practice, however, there seems to be a paradox: The de facto technology (i.e., containerization) for microservice implementation is claimed to be unsuitable for the microservice component (i.e., database) in production environments, mainly due to the data persistence issues (e.g., dangling volumes) and security concerns. As a result, the existing discussions generally suggest replacing database containers with cloud database services, while leaving the on-premises microservice implementation out of consideration. After identifying three statelessness-dominant application scenarios, we proposed container-native data persistence as a conditional solution to enable resilient database containers in production. In essence, this data persistence solution distinguishes stateless data access (i.e., reading) from stateful data processing (i.e., creating, updating, and deleting), and thus it aims at the development of stateless microservices for suitable applications. In addition to developing our proposal, this research is particularly focused on its validation, via prototyping the solution and evaluating its performance, and via applying this solution to two real-world microservice applications. From the industrial perspective, the validation results have proved the feasibility, usability, and efficiency of fully containerized microservices for production in applicable situations. From the academic perspective, this research has shed light on the operation-side micro-optimization of individual microservices, which fundamentally expands the scope of “software micro-optimization” and reveals new research opportunities.

Cloud computing has made federated database systems (FDBS) significantly more practical to implement than in the past. As part of a recent Web-based Geographic Information System (WebGIS) project, we are employing cloud-native technologies (from the container ecosystem) to develop a federated database (DB) infrastructure, to help manage and utilise the distributed and various geospatial data. Unfortunately, there seem to be inherent challenges and complexity of applying the container and Kubernetes technologies to building and running DB systems. Considering that most of the geospatial and theme data are pre-obtained and fixed in our WebGIS project, we decided to focus on the read-only user queries and still resort to Kubernetes to implement an FDBS instance to use. Unlike the de facto practices (e.g., using the StatefulSets mechanism, extending Kuberentes APIs, or employing KubeFed), our solution for Kubernetes-aided FDBS simplifies the tech stack by investigating the fractal object of federated data management, inclusively containerising DB instances, and using the lightweight Deployment mechanism to handle stateless DB containers. Overall, this research not only reveals an easy-to-implement approach to constructing read-only components in a fully-fledged FDBS, but also proposes and demonstrates a novel methodology for FDBS investigations.

The topological model for spatial objects identifies common boundaries between regions, explicitly storing adjacency relations, which not only improves the efficiency of topologyrelated queries, but also provides advantages such as avoiding data duplication and facilitating data consistency. Recently, a compact representation of the topological model based on planar graph embeddings was proposed. In this article, we provide an elegant generalization of such a representation to support hierarchies of vector objects, which better fits the multi-granular nature of spatial data, such as the political and administrative partition of a country. This representation adds a small space on top of the succinct base representation of each granularity, while efficiently answering new topology-related queries between objects not necessarily at the same level of granularity.

A spatial data set is consistent if it satisfies a set of integrity constraints. Although consistency is a desirable property of databases, enforcing the satisfaction of integrity constraints might not be always feasible. In such cases, the presence of inconsistent data may have a negative effect on the results of data analysis and processing and, in consequence, there is an important need for data-cleaning tools to detect and remove, if possible, inconsistencies in large data sets. This work proposes strategies to support data cleaning of spatial databases with respect to a set of integrity constraints that impose topological relations between spatial objects. The basic idea is to rank the geometries in a spatial data set that should be modified to improve the quality of the data (in terms of consistency). An experimental evaluation validates the proposal and shows that the order in which geometries are modified affects both the overall quality of the database and the final number of geometries to be processed to restore consistency.

This work presents a new signature for 2D spatial configurations that is useful for the optimization of a hotspot detection process. The signature is a string of numbers representing changes along the horizontal and vertical slices of a configuration, which serves as the key of an inverted index that groups layout' windows with the same signature. The method extracts signatures from a compact specification of similar exact patterns with a fixed size. Then, these signatures are used as search keys of the inverted index to retrieve candidate windows that can match the patterns. Experimental results show that this simple type of signature has 100% recall and, in average, over 85% of precision in terms of the area effectively covered by the pattern and the retrieved area of the layout. In addition, the signature shows a good discriminate quality, since around 99% of the extracted signatures match each of them with a single pattern.

An inconsistency measure can be used to compare the quality of different data sets and to quantify the cost of data cleaning. In traditional relational databases, inconsistency is defined in terms of constraints that use comparison operators between attributes. Inconsistency measures for traditional databases cannot be applied to spatial data sets because spatial objects are complex and the constraints are typically defined using spatial relations. This paper proposes an inconsistency measure to evaluate how dirty a spatial data set is with respect to a set of integrity constraints that define the topological relations that should hold between objects in the data set. The paper starts by reviewing different approaches to quantify the degree of inconsistency and showing that they are not suitable for the problem. Then, the inconsistency measure of a data set is defined in terms of the degree in which each spatial object in the data set violates topological constraints, and the possible representations of spatial objects are points, curves, and surfaces. Finally, an experimental evaluation demonstrates the applicability of the proposed inconsistency measure and compares it with previously existing approaches.

In this paper we propose three compact data structures to answer queries on temporal graphs. We define a temporal graph as a graph whose edges appear or disappear along time. Possible queries are related to adjacency along time, for example, to get the neighbors of a node at a given time point or interval. A naive representation consists of a time-ordered sequence of graphs, each of them valid at a particular time instant. The main issue of this representation is the unnecessary use of space if many nodes and their connections remain unchanged during a long period of time. The work in this paper proposes to store only what changes at each time instant. The ttk2-tree is conceptually a dynamic k2-tree in which each leaf and internal node contains a change list of time instants when its bit value has changed. All the change lists are stored consecutively in a dynamic sequence. During query processing, the change lists are used to expand only valid regions in the dynamic k2-tree. It supports updates of the current or past states of the graph. The ltg-index is a set of snapshots and logs of changes between consecutive snapshots. The structure keeps a log for each node, storing the edge and the time where a change has been produced. To retrieve direct neighbors of a node, the previous snapshot is queried, and then the log is traversed adding or removing edges to the result. The differential k2-tree stores snapshots of some time instants in k2-trees. For the other time instants, a k2-tree is also built, but these are differential (they store the edges that differ from the last snapshot). To perform a query it accesses the k2-tree of the given time and the previous full snapshot. The edges that appear in exactly one of these two k2-trees will be the final results. We test our proposals using synthetic and real datasets. Our results show that the ltg-index obtains the smallest space in general. We also measure times for direct and reverse neighbor queries in a time instant or a time interval. For all these queries, the times of our best proposal range from tens of µs to several ms, depending on the size of the dataset and the number of results returned. The ltg-index is the fastest for direct queries (almost as fast as accessing a snapshot), but it is 5-20 times slower in reverse queries. The differential k2-tree is very fast in time instant queries, but slower in time interval queries. The ttk2-tree obtains similar times for direct and reverse queries and different time intervals, being the fastest in some reverse interval queries. It has also the advantage of being dynamic.

This paper presents the Succinct Moving Object Index (SMO - Index) that pursues efficiency in storage and time of query processing for timestamp and interval queries. The data structure stores data and index together in a compact manner reducing the need of using external memory. It is based on a K2-tree to store snapshots of objects' location at some time instants, and on a compact representation of the movement of objects between consecutive snapshots. The experimental evaluation shows that the SMO-Index overcomes MVR-Tree in space used and time cost when objects constantly move at similar speed.

Geo-referencing is a key task for geographical information retrieval because it allows unstructured or textual documents (i.e., Web pages) to be associated with geographical locations, which are then used by geo-search engines to index documents and search information by spatial criteria. This work proposes a strategy to extract geo-references from textual documents that combine natural language-processing techniques and co-reference solving heuristics, which in turn can be used to expand a geographical gazetteer. Implicit geographical entities (i.e., those entities referred to by pronouns) are recognized and incorporated into the gazetteer that is updated and used for geo-referencing tasks. Experiments show the promise of the approach to geo-referencing Web pages when dealing with implicit and/or indirect geo-references.

In contrast to the enormous development of database management systems to support spatial databases, very little work has been done in evaluating the quality of spatial data in terms of how much they satisfy a set of topo-semantic integrity constraints, in particular, a set of topological dependency constraints. In the same way, mechanisms for enforcing the satisfaction of those constraints are not necessarily available or even feasible. In this paper we propose measures to evaluate the degree of violation of a topological dependency constraint by geometries stored in a spatial database instance. We also propose how these measures can be aggregated to globally evaluate the data quality of a database instance such that they enable to compare database instances in terms of their constraint satisfaction. We provide an experimental evaluation of those measures using synthetic and real data. We validate our measures by i) analyzing their correlation with the semantic distance of topological relations and ii) checking that the more we randomly modify geometries to make database instances inconsistent, the more our global data quality measure decreases, showing its sensibility to the introduced constraint violations.

In order to deal with inconsistent databases, a repair semantics defines a set of admissible database instances that restore consistency, while staying close to the original instance. This set can be used to characterize consistent data and consistent query answers in inconsistent databases. In this work we present a repair semantics for spatial databases and spatial integrity constraints, i.e. constraints that combine semantic and topological aspects of spatial data. We also propose the notion of consistent answer to a spatial conjunctive query. This introduces the idea of inconsistency tolerance in the spatial domain, shifting the goal from the consistency of a spatial database to the consistency of query answers.

Searching spatial configurations is a particular case of maximal constraint satisfaction problems, where constraints expressed by spatial and nonspatial properties guide the search process. In the spatial domain, binary spatial relations are typically used for specifying constraints while searching spatial configurations. Searching configurations is particularly intractable when configurations are derived from a combination of objects, which involves a hard combinatorial problem. This paper presents a genetic algorithm (GA) that combines a direct and an indirect approach to treating binary constraints in genetic operators. A new genetic operator combines randomness and heuristics for guiding the reproduction of new individuals in a population. Individuals are composed of spatial objects whose relationships are indexed by a content measure. This paper describes the GA and presents experimental results that compare the genetic versus a deterministic and a local-search algorithm. These experiments show the convenience of using a GA when the complexity of the queries and databases do no guarantee the tractability of a deterministic strategy.

Semantic similarity plays an important role in geographic information systems as it supports the identification of objects that are conceptually close, but not identical. Similarity assessments are particularly important for retrieval of geospatial data in such settings as digital libraries, heterogeneous databases, and the World Wide Web. Although some computational models for semantic similarity assessment exist, these models are typically limited by their inability to handle such important cognitive properties of similarity judgements as their inherent asymmetry and their dependence on context. This paper defines the Matching-Distance Similarity Measure (MDSM) for determining semantic similarity among spatial entity classes, taking into account the distinguishing features of these classes (parts, functions, and attributes) and their semantic interrelations (is–a and part–whole relations). A matching process is combined with a semantic-distance calculation to obtain asymmetric values of similarity that depend on the degree of generalization of entity classes. MDSM's matching process is also driven by contextual considerations, where the context determines the relative importance of distinguishing features. Based on a human-subject experiment, MDSM results correlate well with people's judgements of similarity. When contextual information is used for determining the importance of distinguishing features, this correlation increases; however, the major component of the correlation between MDSM results and people's judgements is due to a detailed definition of entity classes.

Semantic similarity measures play an important role in information retrieval and information integration. Traditional approaches to modeling semantic similarity compute the semantic distance between definitions within a single ontology. This single ontology is either a domain-independent ontology or the result of the integration of existing ontologies. We present an approach to computing semantic similarity that relaxes the requirement of a single ontology and accounts for differences in the levels of explicitness and formalization of the different ontology specifications. A similarity function determines similar entity classes by using a matching process over synonym sets, semantic neighborhoods, and distinguishing features that are classified into parts, functions, and attributes. Experimental results with different ontologies indicate that the model gives good results when ontologies have complete and detailed representations of entity classes. While the combination of word matching and semantic neighborhood matching is adequate for detecting equivalent entity classes, feature matching allows us to discriminate among similar, but not necessarily equivalent entity classes.