The relation between Datalog programs and homomorphism problems, and, between Datalog programs and bounded treewidth structures has been recognized for some time and given much attention recently. Additionally, the essential role of persistent variables (in program expansions) for solving several relevant problems has also started to be observed. In Afrati et al. [2005] the general notion of program persistencies was refined into four notions (two syntactical ones and two semantical ones) and the interrelationship between these four persistency numbers was studied. In the present article (1) we prove undecidability results concerning the semantical notions of persistency number--modulo equivalence, of persistency number and of characteristic integer, (2) we exhibit new classes of programs for which boundedness is undecidable and (3) we prove intractabiltity results concerning the syntactical notions of weak persistency number and of weak characteristic integer.

The relation between Datalog programs and homomorphism problems and between Datalog programs and bounded treewidth structures has been recognized for some time and given much attention recently. Additionally, the essential role of persistent variables (of program expansions) in solving several relevant problems has also started to be observed. It turns out that to understand the contribution of these persistent variables to the difficulty of some expressibility problems, we need to understand the interrelationship among different notions of persistency numbers , some of which we introduce and/or formalize in the present work.This article is a first foundational study of the various persistency numbers and their interrelationships. To prove the relations among these persistency numbers, we had to develop some nontrivial technical tools that promise to help in proving other interesting results too. More precisely, we define the adorned dependency graph of a program , a useful tool for visualizing sets of persistent variables, and we define automata that recognize persistent sets in expansions.We start by elaborating on finer definitions of expansions and queries, which capture aspects of homomorphism problems on bounded treewidth structures. The main results of this article are (a) a program transformation technique, based on automata-theoretic tools, which manipulates persistent variables (leading, in certain cases, to programs of fewer persistent variables); (b) a categorization of the different roles of persistent variables; this is done by defining four notions of persistency numbers which capture the propagation of persistent variables from a syntactical level to a semantical one; (c) decidability results concerning the syntactical notions of persistency numbers that we have defined; and (d) the exhibition of new classes of programs for which boundedness is undecidable.

We give lower bou.nds on the complexity of evaluating Datalog queries; our results delimit the possibility of optimizing such queries by compile-time techniques.The main technical tool is a new class of linear firstorder formulas, whose quantifier depth (respectively, number of variables) measures the sequential (respectively, parallel) complexity of Datalog programs.We define a combinatorial game, and use it to prove nonexpressibility of certain Datalog queries by linear formulas; we thus obtain lower bounds for sequential and for parallel complexity.We prove tight versions of our results, for queries of restricted form, by exploiting uniformity and invariance properties of Datalog programs.

It is shown that, by choosing appropriate encodings of instances as relational structures, several known polynomial-time many-one reductions can he described in first-order logic, and furthermore they are monadic. As a corollary, several known NP-complete problems in monadic NP are shown not to be in monadic co-NP. It is further shown that there is no monadic first-order reduction from connectivity to directed reachability, even in the presence of successor. Finally, some classes of syntactically restricted first-order reductions are shown to be incomparable.>

We show that certain monotonic polynomial time queries are not expressible in variants of Datalog. The proof techniques include lower bounds for monotone circuit size and a “Pumping Lemma” for Datalog queries.

Familiar beta eta -equational reasoning on lambda -terms is unsound for proving observational congruences when termination of the standard lazy interpreter is taken into account. A complete logic, based on sequents, for proving termination-observational congruences between simply-typed terms without constants is developed. It is shown that the theory, like that of beta eta -reasoning in the ordinary types lambda -calculus, is decidable. The authors examined the termination behavior of the functional language PCF under the standard interpreters.>

Unary inclusion dependencies are database constraints expressing subset relationships. The decidability of implication for these dependencies together with embedded implicational dependencies, such as functional dependencies, are investigated. As shown by Casanova et al., the unrestricted and finite implication problems are different for the class of functional and unary inclusion dependencies; also, for this class and for any fixed k , finite implication has no k -ary complete axiomatization. For both of these problems, complete axiomatizations and polynomial-time decision procedures are provided: linear time for unrestricted implication and cubic time for finite implication. It follows that functional and unary inclusion dependencies form a semantically natural class of first-order sentences with equality, which although not finitely controllable, is efficiently solvable and docile. Generalizing from these results, it is shown that the interaction between functional and inclusion dependencies characterizes: (1) unrestricted implication of unary inclusion and all embedded implicational dependencies; (2) finite implication of unary inclusion and all full implicational dependencies; (3) finite implication of unary inclusion and all embedded tuple-generating dependencies. As a direct consequence of this analysis, most of the applications of dependency implication are extended, within polynomial-time, to database design problems involving unary inclusion dependencies. Such examples are tests for lossless joins and tests for complementarity of projective views. Finally, if one additionally requires that

A study is made of the complete adequacy for a lambda -calculus with simple recursive types. The set of types is built using the standard domain-theoretic constructors, namely, function space, sum, cartesian and strict product, and lifting. The recursive types allow the author to solve arbitrary systems of mutually recursive domain equations. Thus, he can define in this calculus types of integers, Booleans, lists and streams over these, and so on. The author can also define numerals, Boolean constants, simple arithmetic versions, of pure untyped terms. A precise description is given of the author's calculus, as well as some examples illustrating its expressiveness. A complete adequacy result for the lattice semantics is presented. The problem of designing a completely adequate evaluator for the CPO semantics is also examined.>

A Datalog program is bounded iff it is equivalent to a recursion-free Datalog program. We show that, for some classes of Datalog programs, expressibility in first-order query languages coincides with boundedness. Our results imply that testing first-order expressibility is undecidable for binary programs, decidable for monadic programs, and complete for Σ02.

We study the effect of various syntactic restrictions on the expressive power of database logic programs. We find natural examples of programs which

Datalog is the language of logic programs without function symbols. It is used as a database query language. If it is possible to eliminate recursion from a Datalog program Π, then Π is said to be bounded. It is known that the problem of deciding whether a given Datalog program is bounded is undecidable, even for binary programs. We show here that boundedness is decidable for monadic programs, i.e., programs where the recursive predicates are monadic (the non-recursive predicates can have arbitrary arity). Underlying our results are new tools for the optimization of Datalog programs based on automata theory and logic. In particular, one of the tools we develop is a theory of two-way alternating tree automata. We also use our techniques to show that containment for monadic programs is decidable.

Deciding if a graph has a VLSI layout with a specified maximum edge length is NP-complete.

We investigate the parallel computational complexity of recursive rule queries.These queries are a subset of first-order relational queries augmented with recursion.They form an important psrt of the PROLOG language aud can be eva!uated in PTIME.In [32] Sagiv has shown that it is decidable whether a typed recursive rule query is equivalent to a first-order relational query.We present an alternative proof of this fact We demonstrate a "gap" theorem for these queries.We provide two classes of queries, which can be evaluated in NC, using a logarithmic number of iterations of a first-order query.Finally, we give various, syntactically tight, queries which are logspace-complete in ETIME and cannot be evaluated in this fashion.

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

We present a novel way to formulate database dependencies as sentences of first-order logic, using equational statements instead of Horn clauses. Dependency implication is directly reduced to equational implication. Our approach is powerful enough to express functional and inclusion dependencies, which are the most common database constraints. We present a new proof procedure for these dependencies. We use our equational formulation to derive new upper and lower bounds for the complexity of their implication problems.

We present a new graph theoretic approach to the implication problem for functional (FD) and inclusion (IND) dependencies. Using this methodology we prove decidability for the case of typed IND's and acyclic FD's. We provide new lower bounds for the implication of typed, acyclic IND's and FD's --- NP-hardness and PSPACE-hardness for bounded domains. Finally, we show that there is no k-ary complete axiomatization for implication of FD's, even when we have pairwise consistency, i.e., all possible typed IND's hold.

The problem of translating updates of database views is studied.View updates are disambiguated by requiring that a specified view complement (i.e., a second view that contains all the information omitted from the given view) remain constant during the translation.Some of the computational problems related to the apphcafion of this general methodology in the context of relational databases are studied.Projective views of databases that consist of a single relation and satisfy funcuonal dependencies are emphasized.After characterizing complementary views, the authors show that finding a minimum complement of a given view is NP-complete.The problem of translating the insertion of a tuple into a view is then studied in detail, and the results are extended to the cases of deletion and replacement of a tuple.Finally, the explicit functional dependencies, a new kind of dependency that intuitively states that some part of the database information can be computed from the rest, are defined and studied.

We study the version of the traveling salesman problem in which a relatively small number of cities—say, six—must be visited a huge number of times—e.g., several hundred times each. (It costs to go from one city to itself.) We develop an algorithm for this problem whose running time is exponentialin the number of cities, but logarithmic in the number of visits. Our algorithm is a practical approach to the problem for instances of size in the range indicated above. The implementation and analysis of our algorithm give rise to a number of interesting graph-theoretic and counting problems.

We prove a sequence of results which characterize exactly the complexity of problems related to the evaluation of relational queries consisting of projections and natural joins. We show that testing whether the result of a given query on a given relation equals some other given relation is Dp complete (Dp is a class which includes both NP and co-NP, and was recently introduced in a totally different context [13]). We show that testing inclusion or equivalence of queries with respect to a fixed relation (or of relations with respect to a fixed query) is Π2p-complete. We also examine the complexity of estimating the number of tuples of the answer.

We study the problem of translating updates of database views. View updates are disambiguated by requning that a specified view complement (i.e. a second view which contnms all the information omitted from the given view) remains constant during the translation. We study some of the computational problems related to the application of this general methodology in the context of relational databases. We restrict our attention to projective views of databases which consist of a single relation and satisfy functional dependencies. We first characterize complementary views and show that finding a minimum complement of a given view is NP-complete. We then study in detail the problem of translating the insertion of a tuple into a view and extend our results to the cases of deletion and replacement of a tuple. Finally we define and study a new kind of dependencies the explicit functional dependencies, which intuitively state that some part of the database information can be computed from the rest.

We study the interaction between unary inclusion dependencies (UIND's) and other known classes of dependencies, in the context of both unrestricted and finite implication. We provide complete axiomatizations for unrestricted and finite implication of UIND's and functional dependencies, and polynomial-time algorithms for the inference problems. The inference problem becomes, however, NP-hard, if we require that some attribute have a bounded domain. We show that for unrestricted implication, the interaction between UIND's and unary functional dependencies completely characterizes the interaction between UIND's and embedded implicational dependencies. Also, for finite implication, the interaction between UIND's and unary functional dependencies completely characterizes the interaction between UIND's and full implicational dependencies (but not UIND's and embedded implicational dependencies).