Incomplete Information research is quite mature when it comes to so called existential nulls, where an existential null is a value stored in the database, representing an unknown object. For some reason universal nulls, that is, values representing all possible objects, have received almost no attention. We remedy the situation in this paper, by showing that a suitable finite representation mechanism, called Star Cylinders, handling universal nulls can be developed based on the Cylindric Set Algebra of Henkin, Monk and Tarski. We provide a finitary version of the cylindric set algebra, called Cylindric Star Algebra, and show that our star-cylinders are closed under this algebra. Moreover, we show that any First Order Relational Calculus query over databases containing universal nulls can be translated into an equivalent expression in our cylindric star-algebra, and vice versa. All cylindric star-algebra expressions can be evaluated in time polynomial in the size of the database. The representation mechanism is then extended to Naive Star Cylinders, which are star-cylinders allowing existential nulls in addition to universal nulls. For positive queries (with universal quantification), the well known naive evaluation technique can still be applied on the existential nulls, thereby allowing polynomial time evaluation of certain answers on databases containing both universal and existential nulls. If precise answers are required, certain answer evaluation with universal and existential nulls remains in coNP. Note that the problem is coNP-hard, already for positive existential queries and databases with only existential nulls. If inequalities ¬( x i ≈ x j ) are allowed, reasoning over existential databases is known to be [Formula: see text]-complete, and it remains in [Formula: see text] when universal nulls and full first order queries are allowed.

Recently there has been an effort to solve the problems caused by the infamous NULL in relational databases, by systematically applying Kleene's three-valued logic to SQL. The third truth-value is unknown. In this paper we show that by using a fourth truth-value inconsistent, all the advantages of the three-valued approach can be retained, and that negation can be given a constructive, intuitionistic meaning that allows negative knowledge to be specified in the logic explicitly, without having to resort to extra-logical notions of stratification or to non-monotonic reasoning. The four-valued approach also allows for a computationally efficient treatment of query answering in the presence of inconsistencies. This is in contrast to the computationally intractable repair approach to inconsistency management. From a practical view-point we show that the Cylindric Star Algebra, developed by the authors, is particularly well suited for evaluating First Order queries on four-valued databases, and that the framework of data exchange can smoothly adapted to the four truth-values.

A lot of research activity has recently taken place around the chase procedure, due to its usefulness in data integration, data exchange, query optimization, peer data exchange and data correspondence, to mention a few. As the chase has been investigated and further developed by a number of research groups and authors, many variants of the chase have emerged and associated results obtained. Due to the heterogeneous nature of the area it is frequently difficult to verify the scope of each result. In this paper we take closer look at recent developments, and provide additional results. Our analysis allows us create a taxonomy of the chase variations and the properties they satisfy. Two of the most central problems regarding the chase is termination, and discovery of restricted classes of sets of dependencies that guarantee termination of the chase. The search for the restricted classes has been motivated by a fairly recent result that shows that it is undecidable (RE-complete, to be more precise) to determine whether the chase with a given dependency set will terminate on a given instance. There is a small dissonance here, since the quest has been for classes of sets of dependencies guaranteeing termination of the chase on all instances, even though the latter problem was not known to be undecidable. We resolve the dissonance in this paper by showing that determining whether the chase with a given set of dependencies terminates on all instances is unsolvable, and on level ∏ 2 0 in the Arithmetical Hierarchy. For this we use a reduction from word rewriting systems, thereby also showing the close connection between the chase and word rewriting. The same reduction also gives us the aforementioned instance-dependent RE-completeness result as a byproduct. For one of the restricted classes guaranteeing termination on all instances, the stratified sets dependencies, we provide new complexity results for the problem of testing whether a given set of dependencies belongs to it. These results rectify some previous claims that have occurred in the literature.

The inversion of data exchange mappings is one of the thorniest issues in data exchange. In this paper we study inverse data exchange from a novel perspective. Previous work has dealt with the static problem of finding a target-to-source mapping that captures the "inverse" of a source-to-target data exchange mapping. As we will show this approach has some drawbacks when it come actually applying the inverse mapping in order to recover a source instance from a materialized target instance. More specifically (1): As is well known, the inverse mappings have to be expressed in a much more powerful language than the mappings they invert. (2): There are simple cases where a source instance computed by the inverse mapping misses sound information that one may easily obtain when the particular target instance is available. (3): In some cases the inverse mapping can introduce unsound information in the recovered source instance.

The notion of representation systems describes structures that are algebraically closed under queries. It has recently been realized that representation systems are highly relevant also in the context of data exchange. We extend the notion of representation system to encompass data exchange mappings and their composition. Seen through this lens, two major classes of representation systems emerge, namely homomorphic data exchange systems and strong data exchange systems. The homomorphic "OWA" systems encompass the "classical" part of data exchange. Reasoning is modulo homomorphic equivalence (CQ-equivalence), and only unions of conjunctive queries and monotone data exchange mappings are supported.

Checking the correspondence between two or more database instances and enforcing it is a procedure widely used in practice without however having been explored from a theoretical perspective. In this paper we formally introduce the data correspondence setting and its associated computational problems: checking the existence of solutions, and verifying whether a candidate is a solution, for three distinct types of solutions. Data correspondence is a generalization of data exchange and peer data exchange, and a special case of repairing inconsistent databases. We introduce a new class of dependencies, called semi-LAV, that properly includes both LAV and full dependencies, while retaining tractability for peer data exchange, data correspondence, and database repairs. We also introduce the concept of Σ-satisfying homomorphisms. This new type of homomorphism, together with recent advances, is essential in achieving tractability, while at the same time allowing a large class of dependencies, namely the aforementioned semi-LAV ones. We also show the intractability for a series of problems in the case of weakly acyclic tuple generating dependencies. This implies that many tractability results for weakly acyclic dependencies do not carry over to data correspondence; in these new settings we need to restrict the dependencies a bit further, yielding our semi-LAV dependencies.

In this paper we study the problem of deciding whether a regular path query over views in data-integration systems can be re-expressed without recursion. The problem becomes challenging when the views contain recursion, thereby potentially making recursion in the query unecessary. We define two related notions of boundedness of regular path queries. For one of the notions we show it PSPACE complete, and obtain a constructive method for optimizing regular path queries in data-integration systems. For the other notion of boundedness, we show it PTIME reducible to the notorious problem of limitedness in distance automata, for which only exponential time algorithms are currently known.

Efficient algorithms for mining frequent itemsets are crucial for mining association rules as well as for many other data mining tasks. Methods for mining frequent itemsets have been implemented using a prefix-tree structure, known as an FP-tree, for storing compressed information about frequent itemsets. Numerous experimental results have demonstrated that these algorithms perform extremely well. In this paper, we present a novel FP-array technique that greatly reduces the need to traverse FP-trees, thus obtaining significantly improved performance for FP-tree-based algorithms. Our technique works especially well for sparse data sets. Furthermore, we present new algorithms for mining all, maximal, and closed frequent itemsets. Our algorithms use the FP-tree data structure in combination with the FP-array technique efficiently and incorporate various optimization techniques. We also present experimental results comparing our methods with existing algorithms. The results show that our methods are the fastest for many cases. Even though the algorithms consume much memory when the data sets are sparse, they are still the fastest ones when the minimum support is low. Moreover, they are always among the fastest algorithms and consume less memory than other methods when the data sets are dense.

Mining frequent itemsets is at the core of mining association rules, and is by now quite well understood algorithmically for main memory databases. In this paper, we investigate approaches to mining frequent itemsets when the database or the data structures used in the mining are too large to fit in main memory. Experimental results show that our techniques reduce the required disk accesses by orders of magnitude, and enable truly scalable data mining.

In this paper we consider general path constraints for semistructured databases. Our general constraints do not suffer from the limitations of the path constraints previously studied in the literature. We investigate the containment of regular path queries under general path constraints. We show that when the path constraints and queries are expressed by words, as opposed to languages, the containment problem becomes equivalent to the word rewrite problem for a corresponding semi-Thue system. Consequently, if the corresponding semi-Thue system has an undecidable word problem, the word query containment problem will be undecidable too. Also, we show that there are word constraints, where the corresponding semi-Thue system has a decidable word rewrite problem, but the general query containment under these word constraints is undecidable. In order to overcome this, we exhibit a large, practical class of word constraints with a decidable general query containment problem.Based on the query containment under constraints, we reason about constrained rewritings -using views- of regular path queries. We give a constructive characterization for computing optimal constrained rewritings using views.

Keys are very important in many aspects of data management, such as guiding query formulation, query optimization, indexing, etc. We consider the situation where an XML document does not come with key definitions, and we are interested in using data mining techniques to obtain a representation of the keys holding in a document. In order to have a compact representation of the set of keys holding in a document, we define a partial order on the set of all key expressions. This order is based on an analysis of the properties of absolute and relative keys for XML. Given the existence of the partial order, only a reduced set of key expressions need to be discovered.Due to the semistructured nature of XML documents, it turns out to be useful to consider keys that hold in "almost" the whole document, that is, they are violated only in a small part of the document. To this end, the support and confidence of a key expression are also defined, and the concept of approximate key expression is introduced. We give an efficient algorithm to mine a reduced set of approximate keys from an XML document.

Previous work on frequent item set mining has focused on finding all itemsets that are frequent in a specified part of a database. We motivate the dual question of finding under what circumstances a given item set satisfies a pattern of interest (e.g., frequency) in a database. Circumstances form a lattice that generalizes the instance lattice associated with datacube. Exploiting this, we adapt known cube algorithms and propose our own, minCirc, for mining the strongest (e.g., minimal) circumstances under which an itemset satisfies a pattern. Our experiments show that minCirc is competitive with the adapted algorithms. We motivate mining queries involving migration between item set and circumstance lattices and propose the notion of Armstrong Basis as a structure that provides efficient support for such migration queries, as well as a simple algorithm for computing it.

Studies the problem of efficiently computing correlated item sets satisfying given constraints. We call them valid correlated item sets. It turns out that constraints can have subtle interactions with correlated item sets, depending on their underlying properties. We show that, in general, the set of minimal valid correlated item sets does not coincide with that of minimal correlated item sets that are valid, and we characterize classes of constraints for which these sets coincide. We delineate the meaning of these two spaces and give algorithms for computing them. We also give an analytical evaluation of their performance and validate our analysis with a detailed experimental evaluation.

We study the problem of combining updates—a special instance of theory change—and counterfactual conditionals in propositional knowledge bases. Intuitively, an update means that the world described by the knowledge base has changed. This is opposed to revisions—anotherinstance of theory change—where our knowledge about a static world changes. A countcrfactual implication is a statement of the form ‘If A were the case, then B would also be the case’, where the negation of A may be derivable from our current knowledge. We present a decidable logic, called VCU2, that has both update and counterfactual implication as connectives in the object language. Our update operator is a generalization of operators previously proposed and studied in the literature. We show that our operator satisfies certain postulates set forth for any reasonable update. The logic VCU2 is an extension of D. K. Lewis' logic VCU for counterfactual conditionals. The semantics of VCU2 is that of a multimodal prepositional calculus, and is based on possible worlds. The infamous Ramsey Rule becomes a derivation rule in our sound and complete axiomatization. We then show that Gärdenfors' Triviality Theorem, about the impossibility to combine theory change and counterfactual conditionals via the Ramsey Rule, does not hold in our logic. It is thus seen that the Triviality Theorem applies only to revision operators, not to updates.

In order to enable the database programmer to reason about relations over strings of arbitrary length we introduce alignment logic, a modal extension of relational calculus. In addition to relations, a state in the model consists of a two-dimensional array where the strings are aligned on top of each other. The basic modality in the language (a transpose, or “slide”) allows for a rearrangement of the alignment, and more complex formulas can be formed using a syntax reminiscent of regular expressions, in addition to the usual connectives and quantifiers. It turns out that the computational counterpart of the string-based portion of the logic is the class of multitape two-way finite state automata, which are devices particularly well suited for the implementation of string matching. A computational counterpart of the full logic is obtained from relational algebra by extending the selection operator into filters based on these multitape machines. Safety of formulas in alignment logic implies that new strings generated from old ones have to be of bounded length. While an undecidable property in general, this boundedness is decidable for an important subclass of formulas. As far as expressive power is concerned, alignment logic includes previous proposals for querying string databases, and gives full Turing computability. The language can be restricted to define exactly regular sets and sets in the polynomial hierarchy.

We propose a language that expresses uniformly queries and updates on knowledgebases consisting of finite sets of relational structures. The language contains an operator that “inserts” arbitrary first-order sentences into knowledgebase. The semantics of the insertion is based on the notion of update formalized by Katsuno and Mendelzon in the context of belief revision theory. Our language can express, among other things, hypothetical queries and queries on recursively indefinite databases. The expressive power of our language lies between existential second-order and general second-order queries. The data complexity is in general within exponential time, although it can be lowered to co-NP and to polynomial time by restricting the form of queries and updates.

Article Free Access Share on Horn tables-an efficient tool for handling incomplete information in databases Author: G. Grahne University of Helsinki, Department of Computer Science, Teollisuuskatu 23 SF-00510 Helsinki FINLAND University of Helsinki, Department of Computer Science, Teollisuuskatu 23 SF-00510 Helsinki FINLANDView Profile Authors Info & Claims PODS '89: Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsMarch 1989Pages 75–82https://doi.org/10.1145/73721.73728Published:29 March 1989Publication History 12citation334DownloadsMetricsTotal Citations12Total Downloads334Last 12 Months8Last 6 weeks0 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

Well-known results on graph traversal are used to develop a practical, efficient algorithm for evaluating regularly and linearly recursive queries in databases that contain only binary relations. Transformations are given that reduce a subset of regular and linear queries involving n-ary relations (n > 2) to queries involving only binary relations.

We represent a set of possible worlds using an incomplete information database. The representation techniques that we study form a hierarchy, which generalizes relations of constants. This hierarchy ranges from the very simple Codd-table, (i e , a relation of constants and distinct variables called nulls, which stand for values present but unknown), to much more complex mechanisms involving views on conditioned-tables, (i e , queries on Codd-tables together with conditions). The views we consider are the queries that have polynomial data-complexity on complete information databases. Our conditions are conjunctions of equalities and inequalities.(1) We provide matching upper and lower bounds on the data-complexity of testing containement, membership, and uniqueness for sets of possible worlds and we fully classify these problems with respect to our representation hierarchy. The most surprising result in this classification is that it is complete in P2p, whether a set of possible worlds represented by a Codd-table is a subset of a set of possible worlds represented by a Codd-table with one conjuction of inequalities.(2) We investigate the data-complexity of querying incomplete information databases. We examine both asking for certain facts and for possible facts. Our approach is algebraic but our bounds also apply to logical databases. We show that asking for a certain fact is coNP-complete, even for a fixed first order query on a Codd-table. We thus strengthen a lower bound of [16], who showed that this holds for a Codd-table with a conjunction of inequalities. For each fixed positive existential query we present a polynomial algorithm solving the bounded possible fact problem of this query on conditioned-tables. We show that our approach is, in a sense, the best possible, by deriving two NP-completeness lower bounds for the bounded possible fact problem when the fixed query contains either negation or recursion.

Acyclic database schemes have attracted a lot of interest because of the nice properties enjoyed by such schemes. Recently some new acyclicity conditions that are strictly stronger than the normal α-acyclicity have been introduced by Fagin. Because of increased requirements, the database schemes in the new classes have some further useful properties that are not shared by α-acyclic schemes. Therefore the new classes have practical relevance.A database designer may work in terms of attribute sets and data dependencies, and not only in terms of database schemes. Thus it is important to have a characterization for the acyclic schemes of various degree in terms of data dependencies. For α-acyclic schemes such a characterization exists, but for the new classes the question has been open. In this paper we provide characterizations for β-, γ- and Berge-acyclic database schemes. The characterizations can be stated in a simple form: thus they should be useful for the database designer.