We propose and implement a tool for the access, analysis, and visual exploration of very large relational databases and data warehouses. To this end, we represent the database as a graph in which each table is represented by a tree rooted at the key and in which there is an edge from table T to table T’ if there is an attribute of T which is a foreign key of T’. The interface allows the user to define analytic queries by clicking on nodes and edges of the graph. The user actions are then translated into SQL group-by queries that are evaluated by the underlying database management system. Additionally, the interface allows the user to visualize the analysis results, and to interact with visualizations in order to explore the database content.

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.

System Evolution Analytics on a system that evolves is a challenge because it makes a State Series SS = {S1, S2…SN} (i.e., a set of states ordered by time) with several inter-connected entities changing over time. We present stability characteristics of interesting evolution rules occurring in multiple states. We defined an evolution rule with its stability as the fraction of states in which the rule is interesting. Extensively, we defined stable rule as the evolution rule having stability that exceeds a given threshold minimum stability (minStab). We also defined persistence metric, a quantitative measure of persistent entity-connections. We explain this with an approach and algorithm for System Network Analytics (SysNet-Analytics), which uses minStab to retrieve Network Evolution Rules (NERs) and Stable NERs (SNERs). The retrieved information is used to calculate a proposed System Network Persistence (SNP) metric. This work is automated as a SysNet-Analytics Tool to demonstrate application on real world systems including: software system, natural-language system, retail market system, and IMDb system. We quantified stability and persistence of entity-connections in a system state series. This results in evolution information, which helps in system evolution analytics based on knowledge discovery and data mining.

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 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.

International audience

We propose a framework for analyzing information visualization (infovis) based on the concept of functional dependency (FD). Although functional dependencies express important semantic information of data, they are rarely taken into account by general purpose infovis tools-- a fact that may cause problems in the visualization process. The main idea of our approach is to use the concept of FD for modeling the invariant structures of all three components of information visualization that is data, visual representations, and visual mappings.

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.

This paper presents a novel model of co-reference knowledge, which is based on the distinction of (i) a model of a common reality, (ii) a model of an agent's opinion about reality, and (iii) a model of agents' opinions if they talk about the same object or not. Thereby it is for the first time possible to describe consistently the evolution of the agent's knowledge and its relative consistency, and to formally study algorithms for managing co-reference knowledge between multiple agents if they have the potential to lead to higher states of consistency, independent from the particular mechanism to recognize co-reference. As an example, a scalable algorithm is presented based on monitoring atomic knowledge increments and an abstract notion of belief ranking. The presented approach has a wide potential to study the formal properties of current methods to find co-reference, and to lead to new methods for the global management of co-reference knowledge.

Preference queries are crucial for various applications (e.g. digital libraries) as they allow users to discover and order data of interest in a personalized way. In this paper, we define preferences as preorders over relational attributes and their respective domains. Then, we rely on appropriate linearizations to provide a natural semantics for the block sequence answering a preference query. Moreover, we introduce two novel rewriting algorithms (called LBA and TBA) which exploit the semantics of preference expressions for constructing progressively each block of the answer. We demonstrate experimentally the scalability and performance gains of our algorithms (up to 3 orders of magnitude) for variable database and result sizes, as well as for preference expressions of variable size and structure. To the best of our knowledge, LBA and TBA are the first algorithms for evaluating efficiently arbitrary preference queries over voluminous databases.

We study the problem of determining a concise, quantifier-free monadic predicate for a given set of objects in a given interpretation. We address both DNF and CNF predicates, as well as important sub-languages thereof. The problem is formalized as the search of a minimal element in a set of predicates equipped with a binary relation. We show that the problem has always a solution, that finding a minimal solution is always hard, but much harder when neither the given set of objects nor its complement are the extent of a formal concept (in the sense of Formal Concept Analysis).

We address the problem of defining semantics for logic programs in presence of incomplete and contradictory information coming from different sources. The information consists of facts that a central server collects and tries to combine using (a) a set of logical rules, that is, a logic program, and (b) a hypothesis representing the server's own estimates. In such a setting incomplete information from a source or contradictory information from different sources necessitate the use of many-valued logics in which programs can be evaluated and hypotheses can be tested. To carry out such activities we propose a formal framework based on bilattices such as Belnap's four-valued logics. In this framework we work with the class of programs defined by Fitting and we propose hypothesis-based semantics for such programs. We also establish an intuitively appealing connection between our hypothesis testing mechanism, on the one hand, and the well-founded semantics and Kripke-Kleene semantics of Datalog programs with negation, on the other hand.

We propose a framework for generating an information access space from existing knowledge repositories. Currently, vast amounts of information are being accumulated at accelerating paces in many fields. These include multimedia documents, application program and services. We need new access architecture for organizing and accessing intellectual assets. We propose the use of context as a data modelling mechanism and the construction of an interactive information access space to support users' intuitive access to large amounts of information. A context is a modular representation of information under different perspectives. A context-based information access space enables operations over contextualized objects. We describe the component-based framework and implementation of a context-based information access space.

Indexing and retrieval in Web catalogs can benefit from using faceted taxonomies. A faceted taxonomy consists of a set of facets, where each facet consists of a predefined set of terms structured by a subsumption relation. We propose two extensions of faceted taxonomies, which allow inferring conjunctions of terms that are valid in the underlying domain. We give a model-theoretic interpretation to these extended faceted taxonomies and we provide mechanisms for inferring the valid conjunctions of terms. This inference service can be exploited for preventing errors during the indexing process and for dynamically generating navigation trees that are suitable for browsing through the Web. The proposed scheme has several advantages by comparison to the hierarchical classification schemes that are currently employed by Web catalogs, namely: (a) conceptual clarity: it is easier to understand; (b) compactness: it takes less space; and (c) scalability: the update operations can be formulated easier and be performed more efficiently.

We propose a model for providing integrated and unified access to multiple information sources of the kind of Web catalogs. We assume that each source comprises two parts: (a) an ontology i.e. a set of terms structured by a subsumption relation, and (b) a database that stores objects of interest under the terms of the ontology. We assume that these objects belong to an underlying domain that is common to all sources (e.g. a set of Web pages of interest), and that different sources may use different ontologies with terms that correspond to different natural languages or to different levels of granularity. Information integration is obtained through a mediator comprising two parts: (a) an ontology, and (b) a set of articulations to the sources. Here, by articulation to a source we mean a set of relationships between terms of the mediator and terms of that source. Information requests (queries) are addressed to the mediator whose task is to analyze each query into sub-queries, translate them into queries to the appropriate sources, then merge the results to answer the original query. We study the querying and answering process in such a model and present algorithms for handling the main tasks of the mediator, namely, query translation between the mediator and the sources, source selection and result merging to produce the final answer.

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.

Although semantic data models provide expressive conceptual modeling mechanisms, they do not support context, i.e. providing controlled partial information on conceptual entities by viewing them from different viewpoints or in different situations. The authors present a model for representing contexts in information bases along with a set of operations for manipulating contexts. These operations support creating, updating, combining, and comparing contexts. The model contributes to the efficient handling of information, especially in distributed, cooperative environments, as it enables (i) representing (possibly overlapping) partitions of an information base; (ii) partial representations of objects, (iii) flexible naming (e.g. relative names, synonyms and homonyms), (iv) focusing attention, and (v) combining and comparing different partial representations. The work advances towards the development of a formal framework intended to clarify several theoretical and practical issues related to the notion of context. The use of context in a cooperative environment is illustrated through a detailed example.

We elaborate on the semantics of an enhanced object-oriented semantic network, where multiple instantiation, multiple specialization, and meta-classes are supported for both kinds of objects: entities and properties. By semantics of a semantic network, we mean the information (both explicit and derived) that the semantic network carries. Several data models use semantic networks to organize information. However, many of these models do not have a formalism defining what the semantics of the semantic network is. In our data model, in addition to the Isa relation, we consider a stronger form of specialization for properties, that we call restriction isa, or Risa for short. The Risa relation expresses property value refinement. A distinctive feature of our data model is that it supports the interaction between Isa and Risa relations. The combination of Isa and Risa provides a powerful conceptual modeling mechanism. The user declares objects and relations between objects through a program. Reasoning is done through a number of (built-in) inference rules that allow for derivations both at instance and schema level. Through the inference rules, new objects and new relations between objects are derived. In our data model, inherited properties are considered to be derived objects. In addition to the inference rules, a number of (built-in) system constraints exist for checking the validity of a program.

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.

We present a set-theoretic interpretation of the relational model which allows a semantic approach to query answering. We show that deduction of new tuples from those in the database is possible through set-containment and we give an algorithm for deductive query-answering.

We present a new database model in which each attribute is modeled by a family of disjoint subsets of an underlying population of objects. Such a family is called a partitioning, and the set of all partitionings is turned into a lattice by appropriately defining product and sum. A database is seen as a function from a sublattice into the lattice of partitionings. The model combines the following features: (1) syntactic simplicity (essentially that of the relational model), (2) powerful means for the specification of semantic information (in the form of lattice equations), and (3) deductive capability (essentially that of set theory). The relational model of data and the basic constructs of semantic modeling can be embedded into our model in a simple and straightforward manner.

The probabilistic independence of data base mappings is introduced and studied.The evolution of a data base is simulated in terms of a probabilistic model.The occurrence of any legal data base value is assumed to obey a probability distribution and thus any data base mapping is modelled as a random variable.The probabilistic independence of data base mappings is therefore defined and compared with the algebraic independence.The probabilistic independence is in general a stronger condition than the algebraic independence.The relationship of the two notions of independence is studied and necessary and sufficient conditions are given under which the algebraic and the probabilistic independencies are equivalent.

Article Free Access Share on Partition semantics for relations Authors: Stavros S. Cosmadakis View Profile , Paris C. Kanellakis View Profile , Nicolas Spyratos View Profile Authors Info & Claims PODS '85: Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systemsMarch 1985 Pages 261–275https://doi.org/10.1145/325405.325452Published:25 March 1985Publication History 8citation94DownloadsMetricsTotal Citations8Total Downloads94Last 12 Months10Last 6 weeks6 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

Given a multirelational database scheme and a relational mapping f transforming it, an important question is whether the resulting scheme is equivalent to the original one. This question was addressed in the literature with respect to those relational schemes that satisfy the so called universal relation assumption; however, no study was ever concerned with multirelational (data base) schemes that do not necessarily satisfy this assumption.We present two general definitions of lossless transformation of the database scheme based on the so-called closed world and open world assumptions. While both definitions seem to be practically justified, the one based on the open world assumption is more tractable We are able to test losslessness defined in such a way for a wide class of relational expressions and dependencies. An algorithm for testing losslessness of a mappings (which are arbitrary relational expressions built up from projections, cartesian products and restrictions) is presented in the paper. Moreover, given a lossless transformation, our algorithm enables us to explicitly construct an inverted mapping that restores the corresponding state of the original database. The application of the algorithm to schemes specified by differrent types of dependencies is described. In particular the application of the algorithm for schemes specified by inclusion dependencies is presented. In this case the algorithm works for families of inclusion dependencies having finite chase property. This class of inclusion dependencies is characterized in the paper.

Article Free Access Share on Information theoretic aspects of data bases Authors: S. Abiteboul INRIA, 78153 Le Chesnay - FRANCE INRIA, 78153 Le Chesnay - FRANCEView Profile , M. Spyratos Carleton University, Ottawa - CANADA Carleton University, Ottawa - CANADAView Profile , N. Spyratos INRIA, 78153 Le Chesnay - FRANCE INRIA, 78153 Le Chesnay - FRANCEView Profile Authors Info & Claims PODS '83: Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systemsMarch 1983 Pages 312–316https://doi.org/10.1145/588058.588095Published:21 March 1983Publication History 1citation223DownloadsMetricsTotal Citations1Total Downloads223Last 12 Months23Last 6 weeks2 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

This paper concerns query answering in relational databases. We assume a universe U of attributes and a set of values associated with each attribute. A database scheme is a given collection R = {1, 2, ..., n} of subsets of U, called relation schemes. A query in R is any subset of U. We call "context" any joinable subset of R. An unambiguous context is one in which a query receives the same answer independently of the subcontext used for the computation. A formal treatment of unambiguous contexts is presented and it is shown that they provide a suitable basis for discussing the universal relation assumption, the relationship uniqueness assumption, maximal objects, and other related concepts.

We present a model-independent treatment of some important data base problems. Our approach uses the data base update as elementary concept. The basic tool is the data base view defined by a set of data base updates rather than by the usual view definition mapping.

A database view is a portion of the data structured in a way suitable to a specific application. Updates on views must be translated into updates on the underlying database. This paper studies the translation process in the relational model. The procedure is as follows: first, a “complete” set of updates is defined such that together with every update the set contains a “return” update, that is, one that brings the view back to the original state; given two updates in the set, their composition is also in the set. To translate a complete set, we define a mapping called a “translator,” that associates with each view update a unique database update called a “translation.” The constraint on a translation is to take the database to a state mapping onto the updated view. The constraint on the translator is to be a morphism. We propose a method for defining translators. Together with the user-defined view, we define a “complementary” view such that the database could be computed from the view and its complement. We show that a view can have many different complements and that the choice of a complement determines an update policy. Thus, we fix a view complement and we define the translation of a given view update in such a way that the complement remains invariant (“translation under constant complement”). The main result of the paper states that, given a complete set U of view updates, U has a translator if and only if U is translatable under constant complement.

Abstract The calculation of terminal reliability in other than simple series‐parallel networks takes time exponential in the size of the network. A method is presented for reducing network size by decomposing the network into subnetworks. Terminal reliability is obtained from calculations in the subnetworks. As the efficiency of the method depends on the network decomposition, some simple rules for selecting ‘good’ decompositions are presented. The method yields approximate values of terminal reliability. In sparse networks, however, the approximation is very satisfactory. Further, if the network decomposition satisfies certain conditions, exact values are obtained. Although the method assumes undirected links and perfectly reliable nodes, it can be easily extended to include directed links and failing nodes.