Efficient consistency maintenance of incomplete and dynamic real-life databases is a quality label for further data analysis. In prior work, we tackled the generic problem of database updating in the presence of tuple generating constraints from a theoretical viewpoint. The current paper considers the usability of our approach by (a) introducing incremental update routines (instead of the previous from-scratch versions) and (b) removing the restriction that limits the contents of the database to fit in the main memory. In doing so, this paper offers new algorithms, proposes queries and data models inviting discussions on the representation of incompleteness on databases. We also propose implementations under a graph database model and the traditional relational database model. Our experiments show that computation times are similar globally but point to discrepancies in some steps.

Abstract In this paper, we investigate rule semantics for deductive databases in the context of four-valued logic. In our approach, a database is a pair $\varDelta =(E,R)$, where $E$ is a set of pairs, each pair associating a ground fact with a truth value (thus, allowing to store true, false or inconsistent facts) and $R$ is a set of rules generalizing standard Datalog rules in the following sense: (i) the head of a rule can be a positive or a negative atom and (ii) the body can involve any among the connectors of four-valued logic. We define the database semantics as the least fixed point of a monotonic operator and we compare this semantics with that of k-existential programs defined by Fitting and paraconsistent extended logic programs defined by Arieli. Our main contribution is to show that, if we consider rules as implications (i.e. if we view the database as a set of formulas) then the semantics of the database is the unique minimal model of the set of database formulas. Here, minimality is understood with respect to the knowledge ordering of four-valued logic satisfying a monotonicity property whereby the truth value of the head of an instantiated rule is greater than that of the body. Moreover, we characterize databases having finite semantics and then, we address the issue of database updating. We argue that our approach allows for a new kind of updates, in which the update result depends not only on the fact involved in the update but also on its current truth value in the database.

In this article we introduce a Data and Knowledge Integration Model and a Collaborative Platform for fact-oriented Agricultural Biodiversity Management that is inspired by the conservation and sustainable use of biodiversity within agricultural landscapes, which is essential for the future of agriculture and food security. We demonstrate and validate our proposal in a realistic case study that was carried out with stakeholders from educational institutes including several government agencies from five Ministries, i.e. Ministry of Agricultural and Cooperative, Ministry of Natural Resources and Environment, Ministry of Public Health, Ministry of Commerce and Ministry of Higher Education, Science, Research and Innovation. Key challenges are how to make data inter-operation across these agencies when re-engineering the existing information system and how to make trustworthy platform for data collecting, integrating and sharing, especially, how to keep these agencies engaged throughout the project. The resulting Syntax-Semantic-Organizational Inter-operability model was proposed to provide a candidate best practice for engineering data and knowledge integration through a community-shared and reusable Data Reference Model. The resulting Data Governance Implementation across government agencies, by using BIO-AGRI-WATCH as a case study, has significant consequences regarding communication and engagement with stakeholders and dedicated team for increasing their trust in digital data sharing platform.

In this paper we present two recommendation algorithms, called Node-Edge-Based and Node-Based recommendation algorithms. These algorithms are designed to recommend items to users connected via social network. Our algorithms are based on three main features: a social network analysis measure (degree centrality), the graph searching algorithm (Depth First Search algorithm), and the semantic similarity measure (which measures the closeness between the input item and users). We apply these algorithms to a real dataset (Amazon dataset) and we compare them with item-based collaborative filtering and hybrid recommendation algorithms. Our results show good precision as well as in a good performance in terms of runtime. Moreover, Node-Edge-Based and Node-Based algorithms search a small part of the dataset, compared to item-based and hybrid recommendation algorithms.

In this paper we consider the problem of answering OLAP queries in the context of a data warehouse using materialized views. Materialized views are stored in a cache and our approach uses partition semantics to rewrite incoming queries in terms of the stored views. We take advantage of functional dependencies between data to derive efficient rewriting algorithms and to define a cache maintenance method that optimizes the storage required for the materialized views.

The problem of mining all frequent queries on a relational table is a problem known to be intractable even for conjunctive queries. In this article, we restrict our attention to conjunctive projection-selection queries and we assume that the table to be mined satisfies a set of functional dependencies. Under these assumptions, we define and characterize two pre-orderings with respect to which the support measure is shown to be anti-monotonic. Each of these pre-orderings induces an equivalence relation for which all queries of the same equivalence class have the same support. The goal of this article is not to provide algorithms for the computation of frequent queries, but rather to provide basic properties of pre-orderings and their associated equivalence relations showing that functional dependencies can be used for an optimized computation of supports of conjunctive queries. In particular, we show that one of the two pre-orderings characterizes anti-monotonicity of the support, while the other one refines the former, but allows to characterize anti-monotonicity with respect to a given table, only. Basic computational implications of these properties are discussed in the article.

Multidimensional databases have been designed to provide decision makers with the necessary tools to help them understand their data. This framework is different from transactional data as the datasets contain huge volumes of historicized and aggregated data defined over a set of dimensions that can be arranged through multiple levels of granularities. Many tools have been proposed to query the data and navigate through the levels of granularity. However, automatic tools are still missing to mine this type of data in order to discover regular specific patterns. In this article, we present a method for mining sequential patterns from multidimensional databases, at the same time taking advantage of the different dimensions and levels of granularity, which is original compared to existing work. The necessary definitions and algorithms are extended from regular sequential patterns to this particular case. Experiments are reported, showing the significance of this approach.

International audience

International audience

In this paper we study the problem of mining all frequent queries in a given database table, a problem known to be intractable even for conjunctive queries. We restrict our attention to projection-selection queries, and we assume that the table to be mined satisfies a set of functional dependencies. Under these assumptions we define a pre-ordering ≺ over queries and we show the following: (a) the support measure is anti-monotonic (with respect to ≺), and (b) if we define q ≺ q' iff q ≺ q' and q' ≺ q then all queries of an equivalence class have the same support.

Commonly used in network routing, programming, classification and knowledge representation systems, labeling schemes have also interested the XML community. We thus motivate and describe numbering schemes, their applications, and the trade off between storage capacities and runtime performance. We present a taxonomy of numbering schemes for XML based on the types of supported queries (ancestor, adjacent, etc), the encoding technique, and whether the scheme offers robustness properties according to updates. We describe some of the numbering techniques proposed for XML. We focus on prefix-based schemes. We give a qualitative comparison of the existing numbering schemes, discussing their advantages and drawbacks. Then, we compare their storage requirement and performances. Finally, we consider the new research directions that are likely to benefit from numbering scheme techniques.

OLAP users heavily rely on visualization of query answers for their interactive analysis of massive amounts of data. Very often, these answers cannot be visualized entirely and the user has to navigate through them to find relevant facts.In this paper, we propose a framework for personalizing OLAP queries. In this framework, the user is asked to give his (her) preferences and a visualization constraint, that can be for instance the limitations imposed by the device used to display the answer to a query. Given this, for each query, our method computes the part of the answer that respects both the user preferences and the visualization constraint. In addition, a personalized structure for the visualization is proposed.

On-Line Analytical Processing (OLAP) provides an interactive query-driven analysis of multidimensional data based on a set of navigational operators like roll-up or slice and dice. In most cases, the analyst is expected to use these operations intuitively to find interesting patterns in a huge amount of data of high dimensionality.In this paper, we propose an approach to enhance this analysis by preparing the data set so that the analyst can explore it in a more systematic and effective manner. More precisely we define a measurement of the quality of the representation of multidimensional data and we present a framework for investigating the computation of appropriate representations. We identify the problems of computing such representations and study them w.r.t. an OLAP restructuring operator.

Views over databases have recently regained attention in the context of data warehouses, which are seen as materialized views. In this setting, efficient view maintenance is an important issue, for which the notion of self-maintainability has been identified as desirable. We extend self-maintainability to (query and update) independence, and we establish an intuitively appealing connection between warehouse independence and view complements. Moreover, we study minimal complements and show how to compute them in the presence of key constraints and inclusion dependencies in the underlying databases. Taking advantage of these complements, an algorithm is outlined for the specification of independent warehouses.

We propose a deductive database model containing two kinds of rules: update rules of the form L0←L1, where L0 and L1 are literals, and query rules of the form of normal logic program rules. A basic feature of our approach is that new knowledge inputs are always assimilated. Moreover, updates are always deterministic and they preserve database consistency. We consider that update rules have higher priority than query rules, i.e., update rules may generate exceptions to query-driven derivations. We introduce a semantics framework for database update and query answering, based on the well-founded semantics. We also suggest an alternative approach based on extended logic programs and we show that our database model can be defined in terms of non-monotonic formalisms.

The updating of relational databases has received extensive attention in the past few years. However, the various methods proposed present two main drawbacks: either the method cannot perform some update because of nondeterminism, or the method is deterministic but leads to counterintuitive results. In this paper, we use partition semantics to study updating in universal scheme interfaces. It is shown that, contrary to other approaches, the main difficulties are due to nondeterminism of deletions. We characterize when a deletion is deterministic or not, and we show how partition semantics allow for choices in certain cases of nondeterminism.>

A method for updating deductive databases that allows the insertion or deletion of a fact over intensional predicates in a deterministic manner is presented. It is shown that, contrary to most other approaches, inserting or deleting facts over tensional predicates can always be accomplished without having to make choices. The approach relies on well-founded semantics and on the following two basic approaches: deleted facts are explicitly stored in the database and the inserted and deleted facts may concern any predicate, not just extensional predicates.>

The authors present a novel approach to database updating through universal scheme interfaces. The main contribution of the approach is the elimination of non-determinism. That is, contrary to most other approaches, inserting or deleting a tuple can always be done without having to make any choice at all. Tuples that have been deleted from the database are explicitly stored and are used subsequently in order to invalidate certain derivations. Updates are performed in a monotonous manner, and updates satisfy the property of reversibility.>

We define partition semantics for databases with incomplete information and we present an algorithm for query processing in the presence of incomplete information and functional dependencies. We show that Lipski's model for databases with incomplete information can be seen as a special case of our model.