Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An algebra for pomsets

Extended abstract

  • Contributed Papers
  • Conference paper
  • First Online:
Database Theory — ICDT '95 (ICDT 1995)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 893))

Included in the following conference series:

Abstract

We study languages for manipulating partially ordered structures with duplicates (e.g. trees, lists). As a general framework, we consider the pomset (partially ordered multiset) datatype. We introduce an algebra for pomsets, which generalizes traditional algebras for (nested) sets, bags and lists. This paper is motivated by the study of the impact of different language primitives on the expressive power. We show that the use of partially ordered types increases the expressive power significantly. Surprisingly, it turns out that the algebra when restricted to both unordered (bags) and totally ordered (lists) intermediate types, yields the same expressive power as fixpoint logic with counting on relational databases. It therefore constitutes a rather robust class of relational queries. On the other hand, we obtain a characterization of PTIME queries on lists by considering only totally ordered types.

Work supported in part by the Esprit Project BRA FIDE 2. Work was done while the second author was visiting University of Toronto, and supported by the Institute for Robotics and Intelligent Systems.

The authors wish to thank Vassos Hadzilacos for technical remarks.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. S. Abiteboul and C. Beeri. On the power of languages for the manipulation of complex objects. In Proc. Int. Workshop on Theory and Applications of Nested Relations and Complex Objects (extended abstract), Darmstadt, 1987. INRIA research report n 846.

    Google Scholar 

  2. S. Abiteboul, S. Cluet, and T. Milo. Querying and updating the file. In Proc. 19th Int'l Conf. on Very Large Data Bases, 1993.

    Google Scholar 

  3. S. Abiteboul and P. Kanellakis. Object identity as a query language primitive. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 159–173, 1989.

    Google Scholar 

  4. S. Abiteboul and V. Vianu. Generic computation and its complexity. In Proc. ACM Symp. on Theory of Computing, New Orleans, May 1991.

    Google Scholar 

  5. C. Beeri and T. Milo. Functional and predicative programming in oodb's. In Proc. 11th Symp. on Principles of Database Systems, San Diego, 1992.

    Google Scholar 

  6. J. Van Den Bussche and J. Paredaens, The expressive power of structured values in pure oodb's. In Proc. 10th Symp. on Principles of Database Systems, 1991.

    Google Scholar 

  7. V. Breazu-Tannen, P. Buneman, and S. Naqvi. Structural recursion as a query language. In Proc. 3rd Int. Workshop on database programming languages, pages 9–19, Nafplion, Aug. 1991. Morgan Kaufman.

    Google Scholar 

  8. A. Chandra and D. Harel. Computable Queries for Relational Data Bases. Journal of Computer and System Sciences, 21(2):156–178, Oct. 1980.

    Article  Google Scholar 

  9. L.S. Colby, E.L. Robertson, L.V. Saxton and D. Van Gucht. A Query Language for List Based Complex-Objects. In Proc. 13th ACM Symp. on Principles of Database Systems, pages 179–189, Minneapolis, May 1993.

    Google Scholar 

  10. S. Grumbach and T. Milo. Towards tractable algebras for bags. In Proc. 12th ACM Symp. on Principles of Database Systems, pages 49–58, Washington, May 1993.

    Google Scholar 

  11. S. Grumbach, T. Milo, and Y. Kornatzky. Calculi for bags and their complexity. In 4th Int. Workshop on Database Programming Languages, New-York City, Septembre 1993. Morgan Kaufmann.

    Google Scholar 

  12. E. Graedel and M. Otto. Inductive definability with counting on finite structures. In Proc. of Computer Science Logic 92, pages 231–247. LNCS, n702, 1993.

    Google Scholar 

  13. S. Grumbach and V. Vianu. Playing games with objects. In Proc. Int. Conf. on Database Theory, pages 25–38, Paris, dec 1990.

    Google Scholar 

  14. S. Grumbach and V. Vianu. Tractable query languages for complex object databases. In Proc. 10th ACM Symp. on Principles of Database Systems, pages 315–327, Boulder, May 1991.

    Google Scholar 

  15. S. Ginsburg and X. Wang. Towards a unified approach to querying sequenced data. In Proc. 11th ACM Symp. on Principles of Database Systems, pages 293–300, San Diego, 1992.

    Google Scholar 

  16. R. Hull and J. Su. On the expressive power of database queries with intermediate types. In Proc. 7th ACM Symp. on Principles of Database Systems, 1988.

    Google Scholar 

  17. R. Hull and J. Su. Untyped Sets, Invention and Computable Queries. In Proc. 8th ACM Symp. on Principles of Database Systems, 1989.

    Google Scholar 

  18. J.E. Hopcroft and R.E. Tarjan. Efficient planarity testing. J. of the ACM, 21:549–568, 1974.

    Google Scholar 

  19. J.E. Hopcroft and J.K. Wong. Linear time algorithm for isomorphism of planar graphs. In Proc 6th ACM Symp. on Theory of Computing, pages 172–184, 1974.

    Google Scholar 

  20. N. Immerman. Relational queries computable in polynomial time. Inf. and Control, 68:86–104, 1986.

    Google Scholar 

  21. L. Libkin, L. Wong. New Techniques for Studying Set Languages, Bag Languages, and Aggregate Functions. In Proc. 13th ACM Symp. on Principles of Database Systems, pages 155–166, Minneapolis, May 1993.

    Google Scholar 

  22. R. H. Mohring. Algorithms and Order, I. Rival Ed., chapter Computationally Tractable Classes of ordered Sets, pages 105–193. Kluwer Academic Publishers, 1989.

    Google Scholar 

  23. V. Pratt. The pomset model of parallel processes: Unifying the temporal and the spatial. In Seminar on Concurrency, pages 180–196, Pittsburgh, 1984. LNCS 197.

    Google Scholar 

  24. J. Richardson. Supporting lists in a data model (a timely approach). In Proc. 18th Intl. Conf. on Very Large Databases, Vancouver, 1992.

    Google Scholar 

  25. D. Suciu. Bounded fixpoints for complex objects. In 4th Int. Workshop on Database Programming Languages, New-York City, Septembre 1993. Morgan Kaufmann.

    Google Scholar 

  26. B. Subramanian, S. B. Zdonik, and T. W. Leung. Ordered types in the aqua data model. In 4th Int. Workshop on Database Programming Languages, New-York City, Septembre 1993. Morgan Kaufmann.

    Google Scholar 

  27. J.D. Ullman. Database and Knowledge Base Systems. Computer Science Press, 1988.

    Google Scholar 

  28. M. Vardi. The Complexity of Relational Query Languages. In Proc. 14th ACM Symp. on Theory of Computing, pages 137–146, 1982.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. I.N.R.I.A. Rocquencourt, Le Chesnay, 78153, France

    Stéphane Grumbach

  2. Dept. Computer Science, Tel-Aviv University, Tel-Aviv, Israel

    Tova Milo

Authors
  1. Stéphane Grumbach
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tova Milo
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Georg Gottlob Moshe Y. Vardi

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Grumbach, S., Milo, T. (1995). An algebra for pomsets. In: Gottlob, G., Vardi, M.Y. (eds) Database Theory — ICDT '95. ICDT 1995. Lecture Notes in Computer Science, vol 893. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58907-4_16

Download citation

  • DOI: https://doi.org/10.1007/3-540-58907-4_16

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-58907-5

  • Online ISBN: 978-3-540-49136-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation