Motivated by old and new applications, we investigate Datalog as a language for sequence databases. We reconsider classical features of Datalog programs, such as negation, recursion, intermediate predicates, and relations of higher arities. We also consider new features that are useful for sequences, notably, equations between path expressions, and “packing”. Our goal is to clarify the relative expressiveness of all these different features, in the context of sequences. Towards our goal, we establish a number of redundancy and primitivity results, showing that certain features can, or cannot, be expressed in terms of other features. These results paint a complete picture of the expressiveness relationships among all possible Sequence Datalog fragments that can be formed using the six features that we consider.

Motivated by old and new applications, we investigate Datalog as a language for sequence databases. We reconsider classical features of Datalog programs, such as negation, recursion, intermediate predicates, and relations of higher arities. We also consider new features that are useful for sequences, notably, equations between path expressions, and "packing''. Our goal is to clarify the relative expressiveness of all these different features, in the context of sequences. Towards our goal, we establish a number of redundancy and primitivity results, showing that certain features can, or cannot, be expressed in terms of other features. These results paint a complete picture of the expressiveness relationships among all possible Sequence Datalog fragments that can be formed using the six features that we consider.

We propose a logical framework, based on Datalog, to study the foundations of querying JSON data. The main feature of our approach, which we call J-Logic, is the emphasis on paths. Paths are sequences of keys and are used to access the tree structure of nested JSON objects. J-Logic also features "packing" as a means to generate a new key from a path or subpath. J-Logic with recursion is computationally complete, but many queries can be expressed without recursion, such as deep equality. We give a necessary condition for queries to be expressible without recursion. Most of our results focus on the deterministic nature of JSON objects as partial functions from keys to values. Predicates defined by J-Logic programs may not properly describe objects, however. Nevertheless we show that every object-to-object transformation in J-Logic can be defined using only objects in intermediate results. Moreover we show that it is decidable whether a positive, nonrecursive J-Logic program always returns an object when given objects as inputs. Regarding packing, we show that packing is unnecessary if the output does not require new keys. Finally, we show the decidability of query containment for positive, nonrecursive J-Logic programs.

We discuss three well-known languages for querying and manipulating XML documents: XQuery, XPath and XSLT. They are considered to be the standard languages for processing XML documents. However, specifying their complete semantics in a formal way seems almost impossible. Indeed, an attempt by the W3C XML Query Working Group to do so for XQuery was ultimately abandoned. We introduce three sublanguages, called MiXPath, MiXQuery and MiXSLT, and describe their syntax and formal semantics. The syntax and semantics of these languages are chosen such that they are consistent with the ones given in the related W3C recommendations. As such this provides a practical foundation for research and teaching of XML languages. For this purpose the sublanguages are chosen such that they contain the most crucial features, constructs and expressions of each of these three languages.

Many data-intensive applications have to query a database that involves sequences of sets of objects. It is not uncommon that the order of the sets in such a sequence does not affect the result of the query. Such queries are called symmetric. In this paper, the authors wish to initiate research on symmetric queries. Thereto, a data model is proposed in which a binary relation between objects and set names encodes set membership. On this data model, two query languages are introduced, QuineCALC and SyCALC. They are correlated in a manner that is made precise with the symmetric Boolean functions of Quine, respectively symmetric relational functions, on sequences of sets of given length. The latter do not only involve the Boolean operations union, intersection, and complement, but also projection and Cartesian product. Quine's characterization of symmetric Boolean functions in terms of incidence information is generalized to QuineCALC queries. In the process, an incidence-based normal form for QuineCALC queries is proposed. Inspired by these desirable incidence-related properties of QuineCALC queries, counting-only queries are introduced as SyCALC queries for which the result only depends on incidence information. Counting-only queries are then characterized as quantified Boolean combinations of QuineCALC queries, and a normal form is proposed for them as well. Finally, it is shown that, while it is undecidable whether a SyCALC query is counting-only, it is decidable whether a counting-only query is a QuineCALC query.

We investigate the computational capabilities of Web browsers, when equipped with a standard finite automaton. We observe that Web browsers are Turing-complete. We introduce the notion of a navigational problem, and investigate the complexity of solving Web queries and navigational problems by Web browsers, where complexity is measured by the number of clicks.

We study the expressiveness of a positive fragment of path queries, denoted Path+, on documents that can be represented as node-labeled trees. The expressiveness of Path+ is studied from two angles. First, we establish that Path+ is equivalent in expressive power to two particular subfragments, as well as to the class of tree queries, a subclass of the first-order conjunctive queries defined over the label, parent–child and child–parent predicates. The translation algorithm from tree queries to Path+ yields a normal form for Path+ queries. Using this normal form, we can decompose a Path+ query into subqueries that can be expressed in a very small fragment of Path+ for which efficient evaluation strategies are available. Second, we characterize the expressiveness of Path+ in terms of its ability to resolve nodes in a document. This result is used to show that each tree query can be translated to a unique, equivalent and minimal tree query. The combination of these results yields an effective strategy to evaluate a large class of path queries on documents.

We give a language-independent characterization of the expressive power of the relational algebra on finite sets of source-target relation instance pairs. The associated decision problem is shown to be co-graph-isomorphism hard and in co NP. The main result is also applied in providing a new characterization of the generic relational queries.

The research presented in this paper is situated in the framework of constraint databases introduced by Kanellakis, Kuper, and Revesz in their seminal paper of 1990, specifically, the language with real polynomial constraints (FO+poly). For reasons of efficiency, this model is implemented with only linear polynomial constraints, but this limitation to linear polynomial constraints has severe implications on the expressive power of the query language. In particular, when used for modeling spatial data, important queries that involve Euclidean distance are not expressible. The aim of this paper is to identify a class of two‐dimensional constraint databases and a query language within the constraint model that go beyond the linear model and allow the expression of queries concerning distance. We seek inspiration in the Euclidean constructions, i.e., constructions by ruler and compass. We first present a programming language that captures exactly the first‐order ruler‐and‐compass constructions that are expressible in a first‐order language with real polynomial constraints. If this language is extended with a while operator, we obtain a language that is complete for all ruler‐and‐compass constructions in the plane. We then transform this language in a natural way into a query language on finite point databases, but this language turns out to have the same expressive power as FO+poly and is therefore too powerful for our purposes. We then consider a safe fragment of this language and use this to construct a query language that allows the expression of Euclidean distance without having the full power of FO+poly.

Recently proposed form-based web information systems liberate the capture and reuse of data in organizations by substituting the development of technical implementations of electronic forms for the conceptual modelling of forms' tree-structured schemas and their data access rules. Significantly, these instance-dependent rules also imply a workflow process associated to a form, eliminating the need for a costly workflow design phase. Instead, the workflows thus created in an ad hoc manner by unsophisticated end-users can be automatically analyzed, and incorrect forms rejected.This paper examines fundamental correctness properties of workflows that are implied by instance-dependent access rules. Specifically, we study the decidability of the form completability property and the semi-soundness of a form's workflow. These problems are affected by a choice of constraints on the path language used to express access rules and completion formulas, and on the depth of the form's schema tree. Hence, we study these problems by examining them in the context of several different fragments determined by such constraints.

Given a document D in the form of an unordered labeled tree, we study the expressibility on D of various fragments of XPath, the core navigational language on XML documents. We give characterizations, in terms of the structure of D, for when a binary relation on its nodes is definable by an XPath expression in these fragments. Since each pair of nodes in such a relation represents a unique path in D, our results therefore capture the sets of paths in D definable in XPath. We refer to this perspective on the semantics of XPath as the "global view." In contrast with this global view, there is also a "local view" where one is interested in the nodes to which one can navigate starting from a particular node in the document. In this view, we characterize when a set of nodes in D can be defined as the result of applying an XPath expression to a given node of D. All these definability results, both in the global and the local view, are obtained by using a robust two-step methodology, which consists of first characterizing when two nodes cannot be distinguished by an expression in the respective fragments of XPath, and then bootstrapping these characterizations to the desired results.

The relational data model has simple and clear foundations on which significant theoretical and systems research has flourished. By contrast, most research on data mining has focused on algorithmic issues. A major open question is: what's an appropriate foundation for data mining, which can accommodate disparate mining tasks? We address this problem by presenting a database model and an algebra for data mining. The database model is based on the 3W-model introduced by Johnson et al. [2000]. This model relied on black box mining operators. A main contribution of this article is to open up these black boxes, by using generic operators in a data mining algebra. Two key operators in this algebra are regionize , which creates regions (or models) from data tuples, and a restricted form of looping called mining loop . Then the resulting data mining algebra MA is studied and properties concerning expressive power and complexity are established. We present results in three directions: (1) expressiveness of the mining algebra; (2) relations with alternative frameworks, and (3) interactions between regionize and mining loop.

Enumerating all solutions of a relational algebra equation is a natural and powerful operation which, when added as a query language primitive to the nested relational algebra, yields a query language for nested relational databases, equivalent to the well-known powerset algebra. We study sparse equations, which are equations with at most polynomially many solutions. We look at their complexity and compare their expressive power with that of similar notions in the powerset algebra.

In the context of object databases, we study the application of an update method to a collection of receivers rather than to a single one. The obvious strategy of applying the update to the receivers one after the other, in some arbitrary order, brings up the problem of order independence. On a very general level, we investigate how update behavior can be analyzed in terms of certain schema annotations, called colorings. We are able to characterize those colorings that always describe order-independedent updates. We also consider a more specific model of update methods implemented in the relational algebra. Order-independence of such algebraic methods is undecidable in general, but decidable if the expressions used are positive. Finally, we consider an alternative parallel strategy for set-oriented applications of algebraic update methods and compare and relate it to the sequential strategy.

Abstract We investigate topological properties of subsetsSof the real plane, expressed by first-order logic sentences in the language of the reals augmented with a binary relation symbol forS. Two sets are called topologically elementary equivalent if they have the same such first-order topological properties. The contribution of this paper is a natural and effective characterization of topological elementary equivalence of closed semi-algebraic sets.

We investigate properties of finite relational structures over the reals expressed by first-order sentences whose predicates are the relations of the structure plus arbitrary polynomial inequalities, and whose quantifiers can range over the whole set of reals. In constraint programming terminology, this corresponds to Boolean real polynomial constraint queries on finite structures. The fact that quantifiers range over all reals seems crucial; however, we observe that each sentence in the first-order theory of the reals can be evaluated by letting each quantifier range over only a finite set of real numbers without changing its truth value. Inspired by this observation, we then show that when all polynomials used are linear, each query can be expressed uniformly on all finite structures by a sentence of which the quantifiers range only over the finite domain of the structure. In other words, linear constraint programming on finite structures can be reduced to ordinary query evaluation as usual in finite model theory and databases. Moreover, if only "generic" queries are taken into consideration, we show that this can be reduced even further by proving that such queries can be expressed by sentences using as polynomial inequalities only those of the simple form x < y.

We investigate properties of finite relational structures over the reals expressed by first-order sentences whose predicates are the relations of the structure plus arbitrary polynomial inequalities, and whose quantifiers can range over the whole set of reals. In constraint programming terminology, this corresponds to Boolean real polynomial constraint queries on finite structures. The fact that quantifiers range over all reals seems crucial; however, we observe that each sentence in the first-order theory of the reals can be evaluated by letting each quantifier range over only a finite set of real numbers without changing its truth value. Inspired by this observation, we then show that when all polynomials used are linear, each query can be expressed uniformly on all finite structures by a sentence of which the quantifiers range only over the finite domain of the structure. In other words, linear constraint programming on finite structures can be reduced to ordinary query evaluation as usual in finite model theory and databases. Moreover, if only "generic" queries are taken into consideration, we show that this can be reduced even further by proving that such queries can be expressed by sentences using as polynomial inequalities only those of the simple form z

In the context of object databases, we study the application of an update method to a collection of receivers rather than to a single one.The obvious strategy of applying the update to the receivers one after the other, in some arbkrary order, brings up the problem of order independence.On a very general level, we investigate how update behavior

We introduce G-Log, a declarative query language based on graphs, which combines the expressive power of logic, the modeling power of complex objects with identity and the representation power of graphs. G-Log is a nondeterministic complete query language, and thus allows the expression of a large variety of queries. We compare G-Log to well-known deductive database languages, and find that it is the only nondeterministic and computationally complete language that does not suffer from the copy-elimination problem. G-Log may be used in a totally declarative way, as well as in a "more procedural" way. Thus, it provides an intuitive, flexible graph-based formalism for nonexpert database users.>

The Abiteboul and Beeri algebra for complex objects can express a query whose meaning is transitive closure, but the algorithm naturally associated to this query needs exponential space. We show that any other query in the algebra which expresses transitive closure needs exponential space. This proves that in general the powerset is an intractable operator for implementing fixpoint queries. 1 Introduction Abiteboul and Beeri in [AB88] have shown that powerset can express transitive closure (tc), in a language for complex objects without fixpoints or any other form of iterations. But the obvious way of doing that is by a query whose naturally associated algorithm requires exponential space (and time). We prove here that in order to express tc with powerset, exponential space (and time) is indeed needed. This result is of a different nature than classical inexpressibility results (like transitive closure is not expressible in FO [AU79] or even is not expressible in FO+LFP), because it...

A simple model for representing the hierarchical structure of information is proposed. This model, called the grammatical model, is based on trees that are generated by grammars; the grammars describe the hierarchy of the information represented by the trees. Two methods for querying in this data model are given. The first, called the grammatical algebra, is based on a set of primitive grammar-oriented operators, the second, called the grammatical calculus, on local transformations on the trees. The semantics of both is formally defined. Decidability issues regarding the grammatical calculus are investigated. Finally, the two querying methods are proved to be equally expressive.

A graph-oriented object database model (GOOD) is introduced as a theoretical basis for database systems in which manipulation as well as conceptual representation of data is transparently graph-based. In the GOOD model, the scheme as well as the instance of an object database is represented by a graph, and the data manipulation is expressed by graph transformations. These graph transformations are described using five basic operations and a method construct, all with a natural semantics. The basic operations add and delete objects and edges as a function of the matchings of a pattern. The expressiveness of the model in terms of object-oriented modeling and data manipulation power is investigated.>

In this video session we demonstrate a graph oriented database management system called GOOD The scheme of a database is represented as a directed graph Also the database instance is conceptually represented as a graph However such an instance graph contains all information stored in the database and is therefore too complicated to be displayed completely on the computer screen in a user friendly way It would be almost impossible to nd the desired information not to men tion how di cult it would be to make directly changes in such a graph Therefore we devel oped a language that simpli es the information retrieval and modi cation

Nested relations generalize ordinary flat relations by allowing tuple values to be either atomic or set valued. The nested algebra is a generalization of the flat relational algebra to manipulate nested relations. In this paper we study the expressive power of the nested algebra relative to its operation on flat relational databases. We show that the flat relational algebra is rich enough to extract the same “flat information” from a flat database as the nested algebra does. Theoretically, this result implies that recursive queries such as the transitive closure of a binary relation cannot be expressed in the nested algebra. Practically, this result is relevant to (flat) relational query optimization.

We provide a general framework to study the notion of abstraction in pure object-oriented database models with query languages based on object creation.Abstraction is the key operation to express structured values like aggregates and sets in such languages.We use our general framework to investigate the expressive power of abstraction and to obtain a better understanding of particular features of recent work in the field.

A simple, graph-oriented database model, supporting object-identity, is presented. For this model, a transformation language based on elementary graph operations is defined. This transformation language is suitable for both querying and updates. It is shown that the transformation language supports both set-operations (except for the powerset operator) and recursive functions.

The current database research trend is towards systems which can deal with advanced data applications that go beyond the data standard "enterprise" of "office" database application. This trend is reflected in the research on extension architectures and object-oriented databases. Along with this trend, the need for better and easier-to-use database and end-user interfaces has been stressed. Therefore, we propose a graph-based data model which shares many features with existing data models, but which better facilitates the rigorous study of graphical database end-user interfaces. Graphs have been an integral part of the database design process ever since the introduction of semantic data models. Their usage in data manipulation languages, however, is far more sparse. To deal with data manipulation,typically, schemes in semantic data models are transformed into a conceptual data model such as the relational model. The required database language features then become those of the conceptual model. Object-oriented data models on the other hand, often offer computational complete, non-graphical data languages, usually in the style of object-oriented programming languages such as Smalltalk. Due to their expressiveness, however, these languages do not lend themselves easily as high-level data languages. The first graphical database end-user interfaces were developed for the relational model (for example Zloof's Query-By-Example (QBE)). The earliest graphical database end-user interfaces for semantic models were associated with the Entity-Relationship model. Subsequently graphical interfaces were developed for more complex semantic and object-oriented database models. These interfaces use graphs as their central tool, but as far as data languages, they are usually limited in expressive power. Graph-oriented end-user interfaces have also been developed for recursive data objects and queries. In an earlier publication we introduced the Graph-Oriented Object Database Model(GOOD). This model is built around a single mathematical tool, namely graphs, to both model and manipulate databases. We believe that this is an important step in the direction of rigorously studying and developing database end-user interfaces. In that publication we limited ourselves to describing a simple yet powerful transformation language and discussing its expressiveness. in this paper, we further develop and investigate GOOD. We show that it has many features generally present in existing semantic, object-oriented and deductive database models. Specifically, we demonstrate how the GOOD model is suitable for graphically describing, querying, browsing, restructuring and updating databases, and hence is ideally suited for the study and development of graphically-oriented database end-user interfaces. To demonstrate why GOOD is useful for advanced data applications, we describe how it can be seen as an object-oriented data model. In Section 2 we define the basic GOOD model. In Section 3, we discuss querying, browsing, restructuring and updating, and show that they all can be expressed naturally in a uniform, graphically-oriented and user-friendly manner. We also show how to use GOOD to manipulate and query database schemes. In Section 4, we show how to adapt the GOOD model to incorporate the features of object-oriented database systems.

A simple model for representing the hierarchical structure of information is proposed. This model, called the grammatical model, is based on trees that are generated by grammars; the grammars describe the hierarchy of the information represented by the trees. Two transformation languages, an algebra and a calculus, are presented and shown to be equally expressive.

The algebras and query languages for nested relations defined thus far do not allow us to “flatten” a relation scheme by disregarding the internal representation of data. In real life, however, the degree in which the structure of certain information, such as addresses, phone numbers, etc., is taken into account depends on the particular application and may even vary in time. Therefore, an algebra is proposed that does allow us to simplify relations by disregarding the internal structure of a certain class of information. This algebra is based on a careful manipulation of attribute names. Furthermore, the key operator in this algebra, called “copying,” allows us to deal with various other common queries in a very uniform manner, provided these queries are interpreted as operations on classes of semantically equivalent relations rather than individual relations. Finally, it is shown that the proposed algebra is complete in the sense of Bancilhon and Paredaens.

Article Free Access Share on Possibilities and limitations of using flat operators in nested algebra expressions Authors: Jan Paredaens Dept of Math and Computer Science, Unversity of Antwerp, B-2610 Antwerpen, Belgium Dept of Math and Computer Science, Unversity of Antwerp, B-2610 Antwerpen, BelgiumView Profile , Dirk Van Gucht Computer Science Dept, Indiana Unversity, Bloomington, IN Computer Science Dept, Indiana Unversity, Bloomington, INView Profile Authors Info & Claims PODS '88: Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsMarch 1988 Pages 29–38https://doi.org/10.1145/308386.308402Published:01 March 1988Publication History 35citation228DownloadsMetricsTotal Citations35Total Downloads228Last 12 Months9Last 6 weeks4 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

In [9] we proposed a method for decomposing join dependencies (jd's) in a relational database. Decomposing a jd can be useful for separating cyclic and acyclic parts of jd's, obtaining more insight in the structure of a jd or making integrity-checking more efficient. The decomposition methodology of [9] has many desirable properties. However, in general it cannot generate all the decompositions of a given jd. In this paper, we first recall this decomposition methodology and its most important properties. We then introduce a subclass of jd's, the unambiguous jd's. We show that this class represents exactly those jd's that have a unique decomposition (which can be obtained by our method). We also give a characterization of this decomposition in terms of the structure of the original jd. To prove our results, we make extensive use of hypergraph theory.