Blog
About

151
views
0
recommends
+1 Recommend
1 collections
    4
    shares
      • Record: found
      • Abstract: found
      • Conference Proceedings: found
      Is Open Access

      Finite Query Languages for Sequence Databases

      ,

      Proceedings of the Fifth International Workshop on Database Programming Languages (DBPL-5)

      Database Programming Languages

      6-8 September 1995

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          This paper develops a query language for sequence databases, such as genome databases and text databases. Unlike relational data, queries over sequential data can easily produce infinite answer sets, since the universe of sequences is infinite, even for a finite alphabet. The challenge is to develop query languages that are both highly expressive and finite. This paper develops such a language. It is a subset of a recently developed logic called Sequence Datalog [19]. SequenceDatalog distinguishes syntactically between subsequence extraction and sequence construction. Extraction creates sequences of bounded length, and leads to safe recursion; while construction can create sequences of arbitrary length, and leads to unsafe recursion. In this paper, we develop syntactic restrictions for Sequence Datalog that allow sequence construction but preserve finiteness. The main idea is to use safe recursion to control and limit unsafe recursion. The main results are the definition of a finite form of recursion, called domain bounded recursion, and a characterization of its complexity and expressive power. Although finite, the resulting class of programs is highly expressive, since its data complexity is complete for the elementary functions.

          Related collections

          Most cited references 13

          • Record: found
          • Abstract: not found
          • Article: not found

          The Semantics of Predicate Logic as a Programming Language

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Contributions to the Theory of Logic Programming

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              An amateur's introduction to recursive query processing strategies

                Bookmark

                Author and article information

                Contributors
                Conference
                September 1995
                September 1995
                : 1-13
                Affiliations
                D.I.F.A., Università della Basilicata

                via della Tecnica, 3

                85100 Potenza, Italy
                Department of Computer Science

                University of Toronto

                Toronto, Ontario, Canada
                Article
                10.14236/ewic/DBPL1995.21
                © Giansalvatore Mecca et al. Published by BCS Learning and Development Ltd. Proceedings of the Fifth International Workshop on Database Programming Languages, Gubbio, Umbria, Italy

                This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

                Proceedings of the Fifth International Workshop on Database Programming Languages
                DBPL-5
                5
                Gubbio, Umbria, Italy
                6-8 September 1995
                Electronic Workshops in Computing (eWiC)
                Database Programming Languages
                Product
                Product Information: 1477-9358BCS Learning & Development
                Self URI (journal page): https://ewic.bcs.org/
                Categories
                Electronic Workshops in Computing

                Comments

                Comment on this article