INODE: Building an End-to-End Data Exploration System
in Practice [Extended Vision]

This component links loosely coupled collections of data sources such as relational databases, graph databases or text documents based on the well-established ontology-based data access (OBDA) paradigm (Xiao et al., 2018a). OBDA uses a global ontology (knowledge graph) to model the domain of interest and provides a conceptual representation of the information in the data sources. The sources are linked to elements in the global ontology through declarative mappings. It is well-known that designing OBDA mappings manually is a time-consuming and error-prone task. The Data Modeling and Linking component of INODE aims at automatizing this task by providing two mechanisms: data-driven and task-driven mapping generation.

Data-driven Mapping Generation. This mechanism deals with linking novel data sources to the system. The idea is to rely on mapping patterns that describe well-assessed and sound schema-transformation rules usually applied in the design process of relational databases. By analyzing (driven by the patterns) the data sources, it is possible to automatically derive a so-called putative ontology (Sequeda and Miranker, 2015) describing both the explicit entities and relationships constituting the schema and the implicit ones inferrable from the data. From the mapping patterns, one can also automatically derive mappings that link the data sources to the putative ontology.

Task-driven Mapping Generation. This mechanism is applied whenever a task or a query is formulated that uses specific target ontology elements that are not yet aligned with the putative ontology. In such scenario, the semantics of the query are used to automatically generate mappings to align the target ontology with the putative ontology.

Knowledge Graph (KG) Generation. This service transforms unstructured information hidden in large quantities of text (e.g. repositories of scientific papers) to an exploitable structured representation through an NLP pipeline. INODE follows an Open Information Extraction (OIE) approach to convert each sentence of the corpus into a set of relational triples, where each triple consists of a subject, an object, and a predicate (relationship) linking them. We leverage a number of preprocessing techniques, including co-reference resolution and extractive summarization to improve the quality of the extracted relational triples. We combine different OIE methods (rule-based, analytics-based and learning-based) to achieve both high precision and high recall (Papadopoulos et al., 2020). The relational triples are further linked with domain-specific ontology concepts before being integrated into the knowledge graph.

This component is responsible for the execution of queries using Ontop (Xiao et al., 2020), a the state-of-the-art OBDA system. Ontop allows the users to formulate queries in terms of concepts and properties of their domain of expertise (represented in knowledge graphs), rather than in terms of table and attribute names used in the actual data sources. Hence, users do not have to be aware of the specific storage details of the underlying data sources in order to satisfy their information needs.

Query Execution. This service provides on-the-fly reformulation of SPARQL queries over the domain ontology to SQL queries over the data sources. An approach based on reformulation has the advantage that the data available in the data sources does not need to be duplicated in the query processing system, but can be kept in the data sources as-is. This means that the Query Execution service is guaranteed even in the common scenario where the user does not own the data nor does have the right to copy them. To produce reformulations that can efficiently be executed over the data, in INODE we use optimization techniques such as self-join elimination for denormalized data (Xiao et al., 2020) and optimizations of left-joins arising from OPTIONAL and MINUS operators (Xiao et al., 2018b).

Source Federation. The Source Federation service deals with distributing the processing of queries over the available data sources. INODE provides different kinds of federation ranging from SQL federation to seamless SPARQL federation. With respect to SPARQL, we can distinguish between two forms of federation: seamless federation and SPARQL 1.1 SERVICE federation.

In seamless federation, users send queries against a unified view of the remote endpoints without the need to be aware of the actual vocabularies used in the federated endpoints. The challenge is to automatically detect to which sources which components of the query need to be dispatched, to collect the retrieved results, and to combine them into a coherent answer. We address this challenge by relying on the knowledge about the sources encoded in the OBDA mappings. Given that efficiency is a crucial requirement in this setting, our approach requires a dedicated cost-model able to minimize the number of distributed joins over the federation layer, in order to favor more efficient joins at the level of the sources.

Instead, SERVICE federation might be adopted in those cases where users want to directly refer to “external” SPARQL endpoints, not yet integrated with the ontology. In this setting, the user directly references the desired endpoints at query time using the SPARQL 1.1 SERVICE functionality. Observe that the user is required to be aware of the vocabulary used in the external endpoint. Hence, the Source Federation service can simply delegate the execution of the SPARQL query component referenced in the SERVICE call.

Data Analytics. The data analytics service exploits novel and efficient query reformulation and optimization techniques (Xiao et al., 2020) to compute complex analytical functions. Such techniques are based on algebraic transformations of the SPARQL algebra tree, rather than on Datalog transformations as traditionally done in the OBDA literature. This shift of paradigm allows for an efficient implementation of analytical functions such as SPARQL aggregates. It is worth noting that INODE, through Ontop, provides the first open-source reformulation-based system able to support SPARQL aggregates.

The Answer Justification service generates in an automatic way compact and easy to understand explanations for query results. In an OBDA setting, the explanations for a result must take into account, in addition to the query, the three components of the input, namely the ontology, the mappings, and the data sources (Calvanese et al., 2019). The ontology is taken care of by identifying the ontology axioms used for the rewriting of the input query. As for the mappings, those considered in the justification are the ones that were used for the unfolding of the rewritten query to produce the SQL reformulation. Finally, the data is taken care of by identifying the actual tables and tuples that contributed to build the considered result, using an approach based on provenance semirings (Senellart et al., 2018).

Exploration by Natural Language. For translating a natural language question into SQL or SPARQL, INODE uses pattern-based, graph-based and neural network-based approaches. For translating from NL to SQL, INODE extends the pattern-based system SODA (Blunschi et al., 2012) with NLP techniques such as lemmatization, stemming and POS tagging to allow both key word search queries as well as full natural language questions. In addition, we use Bio-SODA (Sima et al., 2019), a graph-based system to enable NL questions over RDF graph databases. In order to enable federated queries across both relational databases and RDF graph databases, INODE uses an ontology-based data access technology leveraging Ontop (Calvanese et al., 2017). The advantage of using pattern-based or graph-based approaches over neural network-based approaches is that they do not require training data, which is often very costly to gain.

Since neural network-based approaches typically require large amounts of training data, we also experimented with various training data generation approaches. INODE uses an inverse data annotation approach called OTTA (Deriu et al., 2020). Rather than writing NL questions and then the corresponding SQL or SPARQL statements, OTTA reverses the process. In particular, OTTA randomly generates so-called operator trees which are similar to logical query plans that can easily be understood by non-tech savvy users. Afterwards, given these operator trees, crowd workers write the corresponding NL questions. In INODE, we use both crowd workers and domain experts for generating training data.

Finally, INODE integrates the neural network-based approach ValueNet, which leverages transformer architectures to translate NL to SQL (Brunner and Stockinger, 2021). The ultimate goal of INODE is to combine all these techniques into an intelligent hybrid-approach that improves on the errors of each of the individual systems.

Exploration by Explanation. One of the biggest hurdles in today’s exploration systems is that the system provides no explanations of the results or system choices. Nor does the system trigger input from the user, for example, by asking the user to provide more information. In INODE, we enable a conversational setting, where the system can (a) ask clarifications and (b) explain results in natural language. This interaction assumes that the system is capable of analyzing and understanding user requests and generating its answers or questions in natural language.

One approach used in INODE builds on Template-based Synthesis (Kokkalis et al., 2012). This approach considers the database schema as a graph and a query as a subgraph. We use templates that tell us how to compose sentences as we traverse the graph and we use different traversal strategies that generate query descriptions as phrases in natural language. Furthermore, to generate NL descriptions that use the vocabulary of a particular database, INODE enriches its vocabulary by leveraging ontologies built by the Data Modeling and Linking components. To further improve INODE’s explanation capabilities, we are working on an approach to automatically learn templates, which is especially critical for databases with no descriptive metadata, such as SDSS. Essentially, we are using neural-based methods to translate from SQL or SPARQL to natural language.

For example, user questions in natural language inevitably hide ambiguity. Hence, the system can come up with several possible query interpretations that may lead to unexpected results or need the user’s help for query disambiguation.

Exploration by Example and by Analytics. By-example is a powerful operator that encapsulates multiple semantics. It takes a set of examples, such as galaxies or patients, and explores its different facets, filters them, finds similar/dissimilar sets, finds overlapping sets, joins them with other sets, finds a superset, etc. Additionally, by-example operators can be combined with by-analytics to find sets that are similar/dissimilar wrt some value distributions. Figures 4 shows an example data exploration pipeline (DEP) for exploring galaxies with different instances of by-example.

By-example and by-analytics operators can be represented in the Region Connection Calculus (RCC) (Li and Ying, 2003) and are, in their general form, computationally challenging. For instance, by-subset is akin to solving a set cover problem, which has been extensively studied (Cormode et al., 2010). Similarly, by-join requires to have appropriate indices. In INODE, we adopt two approaches. One is based on a relational backend in which individual operators are translated into SQL. The other one is an in-memory Python implementation that relies on pre-computing and indexing sets. For some operators such as by-facet, the SQL version is straightforward since it resolves into generating a GROUP BY-query. For others, such as by-overlap, the Python version is simpler as it relies on using an index that records pairwise overlaps between pre-computed sets.

Exploration by Recommendation. In a mixed-initiative setting, the system actively guides the user in what possible actions to perform or data to look at next. In INODE, we are interested in recommendations in both cold-start (where the user has not given any input) and warm-start settings (where the user has asked one or more queries but may not know what to do next). In the former case, the goal is to show a set of example or starter queries that the users could use to get some initial answers from the dataset (e.g. (Howe et al., 2011)). In the latter case, the system can leverage the user’s interactions (queries) to show possible next queries (e.g., (Guilly et al., 2018)).

A big differentiator is the availability of query logs. In case no query logs are available, the system should still provide recommendations. In INODE we are addressing the recommendation problem from different angles, i.e., generating recommendations: (a) based on data analysis (Glenis et al., 2020) (b) by NL-based processing and query augmentation techniques leveraging knowledge bases (c) by user log analysis.

Exploration by Visualization. In information retrieval, search queries result in a list of candidates ranked by their matching score (Manning et al., [n.d.]). This also holds true for INODE, as most exploration operators generate multiple potential answers. However, results are not individual items such as documents, but data sets (i.e. sets of items) and have to be communicated to the user differently to support their goals. Not only do users have to decide, which data set contains the answer they are looking for, but also to compare the results, to assess redundancies, discrepancies and other surprising or interesting differences to draw hints on how to continue the exploration.

The goals of the by-visualization data access and exploration interface are two-fold: (1) Enable ”explorers” to understand, compare and decide based on the provided results and (2) enable them to interact with the results by enabling indirect query manipulation, identifying and highlighting parts that are of interest for further analysis and guiding them towards interesting regions (Stahnke et al., [n.d.]; Steiger et al., [n.d.]; Ruotsalo et al., [n.d.]; May et al., 2012). Depending on the users information need, the optimal answer may take different forms. For example, some questions can be satisfied by a single data cell, while others require aggregated values or even multiple tables. Hence, making the results explorable with respect to the users’ needs is very challenging.

Our processes for user requirements elicitation confirms our goals stated above and is based on the User Centered Design standard (International Organization for Standardization, 2019). In addition to that, users emphasized the importance to compare differences as well as similarities of queries and results. As a base line, we enabled the visualization of multiple tables with direct manipulation capabilities and currently work on an overview visualization that spans the result data space.

A simple data exploration process with INODE for exploring EU-projects stored in the CORDIS³³3https://cordis.europa.eu/ database is shown in Figure 5.

Traditionally SQL or SPARQL are used to query structured data stored in relational databases and graph databases, respectively. A manual time-consuming data integration process is usually required to integrate new data sources. Additionally, data integration techniques used for structured data are not directly applicable to unstructured data since they do not have a schema.

There are several data integration challenges that can be tackled with ML. The first one is to automate data integration (Golshan et al., 2017), in the spirit of existing work that improves entity matching using transformer architectures (Brunner and Stockinger, 2020). The second challenge is to automatically generate knowledge graphs, in the spirit of neural-network systems such as Snorkel  (Ratner et al., 2017). Another powerful concept to automate knowledge graph construction is to combine user dialogs with graph construction (Nguyen et al., 2017). The idea is to augment the knowledge graphs by learning concepts that are commonly queried but do not exist in the graph. In summary, there has been a large amount of research on automatic knowledge base construction. However, the combination of knowledge base construction with natural language query processing has been largely untapped.

Understanding user interests and expertise is a vital component for enabling intelligent data exploration. For instance, the general public interested in black holes has different expectations from an experienced astronomer with a vast knowledge of astrophysics. The challenge is to avoid overwhelming a novice user while providing interesting and relevant information to an expert user.

The system should constantly improve its behavior by learning and adapting to the user from task to task. Our operators are a great opportunity to learn and adapt to users, as they provide the ability to choose between utility and novelty, two dimensions that have not been explored together in the past. Additionally, they enable collecting user feedback at the level of individual operators and of a DEP. While ML methods for learning user profiles exist in the context of individual systems for web search or recommendations, they have not been studied before in the context of determining which operator caters for which user in the next step. A simple start is to use regression methods to determine the weight of utility and novelty when exploring data. Additionally, probabilistic language models (Cao et al., 2017) or matrix factorization-based approaches (Zhao et al., 2015) can be used to infer users’ topical interests, and latent factor models to mine user groups.

Traditional systems such as SODA, ATHENA, NALIR, or Logos (Blunschi et al., 2012; Saha et al., 2016; Li and Jagadish, 2014; Kokkalis et al., 2012) use pattern-based approach for NL to SQL or SQL to NL, or supervised ML (Kim et al., 2020; Brunner and Stockinger, 2021). A new opportunity here is to train a neural network for sequence-to-sequence prediction (Sutskever et al., 2014; Brunner and Stockinger, 2021) for translating from NL-to-SQL and vice versa. The key research challenge is how to use the feedback provided by users to disambiguate queries and feed the gained knowledge back into ML models to improve learning with semantic information for building ML models to tackle disambiguation and context modeling (Shekarpour et al., 2016).

This should allow to model and solve the two symmetrical translation problems at once. However, ML methods for query translation typically require large amounts of training data. Our vision is that a full-fledged exploration system should be able to leverage both pattern-based and ML-based approaches to provide the most relevant answers to the user.

Understanding queries and users serves the ability to provide guidance in generating DEPs. This challenge can be approached in different ways depending on the user’s expertise and willingness to provide feedback. In a scenario where a DEP is given (see example in Section 2), the problem could be cast as finding the right parameters for each query in the DEP. In a scenario where the user is providing the next query, it could be seen as a query completion problem. In a scenario where the user does not write exploration queries and only provides feedback on results, it could be seen as the problem of learning the user’s DEP. All these cases result in partially-guided or fully-guided exploration.

Furthermore, since DEPs bring together several data access modalities, which may be initiated by the user (e.g. a user query) or by the system (recommendations or explanations), the system needs to learn how to use its options to help the user in meaningful and unobtrusive ways. While there has been work on each of these capabilities individually (e.g., recommendations or query explanations), these efforts only focus on small parts of the problem lacking a holistic understanding of the behavior and dynamics of a multi-aspect system. ML approaches and in particular, Reinforcement Learning (RL) and Active Learning (AL) can be leveraged.

Partial Guidance with AL. AL is claimed to be superior to faceted search when the goal is to help users formulate queries. Systems like AIDE (Dimitriadou et al., 2016) and REQUEST (Ge et al., 2016) assist users in constructing accurate exploratory queries, while at the same time minimizing the number of sample records presented to them for labeling. Both systems rely on training a decision tree classifier to build a model that classifies unlabeled records. A bigger challenge is to leverage AL in generating and refining queries that go beyond SQL predicates.

Full-Guidance with RL. RL and Deep RL are becoming (Milo and Somech, 2020) the methods of choice for creating exploration pipelines and for generating DEPs based on a simulated agent experience (El et al., 2020; Seleznova et al., 2020). In (El et al., 2020), a Deep RL architecture is used for generating notebooks that show diverse aspects of a data set in a coherent narrative. In (Seleznova et al., 2020), an end-to-end exploration policy is generated to find a set of users in a collection of groups. Both frameworks accept a wide class of exploration actions and do not need to gather exploration logs. An open question is the applicability of this framework to specific data sets and the transferability of learned policies across data sets.

Evaluating data exploration requires a holistic approach that addresses performance, quality and user experience aspects (Eichmann et al., 2020). The iterative multi-step nature of DEPs makes evaluation particularly challenging since it is not simply a matter of summing up multiple local evaluations at each step. Regarding performance, the challenge lies in the design of logging mechanisms to export the performance of different steps in DEPs. Such logging must capture in fine details the time and memory usage each step takes so that they can be aggregated to assess a full DEP. The aggregation must be carefully designed to include user actions such as exploring multiple paths and backtracking. While some users prefer the shortest path to a goal, others may be more interested in exploring different paths.

Multiple evaluation questions arise: “How good are DEPs? How good are NL to SQL/SPARQL translations and vice versa? How good are the next-operator or next-data recommendations and explanations?” The novelty of our approach lies in the ability to jointly assess performance, quality and user experience for each use case.

We categorize INODE’s evaluation metrics into system metrics and human factors (Rahman et al., 2020). To answer above questions, certain key challenges need to be answered. The first challenge lies in extracting metrics from user interactions. We are addressing this by designing logging mechanisms to export various parameters. We use latency and memory usage for evaluating the system performance of a DEP. We also record the number of clicks, interaction time and user feedback. While some users prefer the shortest path to a goal, others may be more interested in exploring different paths.

Another challenge lies in the iterative multi-step nature of DEPs since it is not simply a matter of summing up multiple local evaluations at each step. An additional key challenge is human subject bias. To avoid such biases, our initial studies are designed in multiple stages such as pre-qualification of users, randomly assigning users to different treatment groups and finally feedback from users.

User acceptance of our system is strongly related to two key factors: accuracy - which reflects the closeness of exploration results to desired results, and controllability - which reflects the ability of our system to guide the user in the exploration (Eichmann et al., 2020). Accuracy is computed using standard methods such as precision and recall, and controllability is the inverse of the number of user-interactions. Our first endeavor is to deploy user studies that explore the relationship between accuracy and controllability. To do so, we will perform factorial design analysis and deploy questionnaires for exploration scenarios we are defining with our use case providers.

The key idea of using ML techniques here is to capture the dependence on users and data and learn different exploration profiles. A major challenge is to design pilot studies in a sound manner with direct observations via questionnaires and indirect ones (such as mouse tracking) to generate labeled datasets for learning. Using ML techniques, and in particular ensemble learning and multi-task learning, constitutes an unprecedented opportunity to adapt the evaluation to users and data.