Skip to main content
SpringerLink
Log in

Databases

  • Chapter
  • First Online:
Computer Science

Abstract

This chapter is about database research (or as we abbreviate DBR). To people outside of computer science – and perhaps to many within – it will be unclear what this term means. First of all, what is a “database”? Used generally, it could mean any collection of information. It is obvious that there are deep scientific issues involved in managing information. But information and data are very general notions. Doesn’t much of computing deal with manipulating data or information? Isn’t everything data? Clearly the databases that DBR deals with must be something more specific.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 54.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  • Serge Abiteboul and Catriel Beeri. On the power of languages for the manipulation of complex values. VLDB J., 4:727–794, 1995.

    Article  Google Scholar 

  • Serge Abiteboul and Paris C. Kanellakis. Object identity as a query language primitive. J. ACM, 45:798–842, 1998.

    Article  MATH  MathSciNet  Google Scholar 

  • Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995.

    Google Scholar 

  • Serge Abiteboul, Ioana Manolescu, Philippe Rigaux, Marie-Christine Rousset, and Pierre Senellart. Web Data Management. Cambridge University Press, 2012.

    Google Scholar 

  • Andrea Acciarri, Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, Mattia Palmieri, and Riccardo Rosati. QuOnto: Querying ontologies. In Proc. AAAI, 2005.

    Google Scholar 

  • Peter M. G. Apers, Carel A. van den Berg, Jan Flokstra, Paul W. P. J. Grefen, Martin L. Kersten, and Annita N. Wilschut. PRISMA/DB: A parallel main memory relational DBMS. IEEE Trans. Knowl. Data Eng., 4(6):541–554, 1992.

    Article  Google Scholar 

  • Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, editors. The description logic handbook: theory, implementation, and applications. Cambridge University Press, 2003.

    Google Scholar 

  • Rudolf Bayer and Edward M. McCreight. Organization and maintenance of large ordered indices. Acta Inf., 1:173–189, 1972.

    Article  Google Scholar 

  • Catriel Beeri, Ronald Fagin, David Maier, Alberto Mendelzon, Jeffrey Ullman, and Mihalis Yannakakis. Properties of acyclic database schemes. In Proc. STOC, 1981.

    Google Scholar 

  • Michael Benedikt and Christoph Koch. From XQuery to relational logics. ACM Trans. Database Syst., 34(4):1–48, 2009.

    Article  Google Scholar 

  • Luc Bouganim, Björn Þór Jónsson, and Philippe Bonnet. uFLIP: Understanding Flash IO patterns. In Proc. CIDR, 2009.

    Google Scholar 

  • Wolfgang Breitling. Histograms – myths and facts. In Proc. Hotsos Symposium on Oracle System Performance, 2005.

    Google Scholar 

  • Andrea Calì, Georg Gottlob, and Andreas Pieris. Advanced processing for ontological queries. PVLDB, 3(1):554–565, 2010.

    Google Scholar 

  • Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Tractable reasoning and efficient query answering in description logics: The L-Lite family. J. Autom. Reasoning, 39(3):385–429, 2007.

    Article  MATH  Google Scholar 

  • R. G. G. Cattell, editor. The Object Database Standard: ODMG 2.0. Morgan Kaufmann, 1997.

    Google Scholar 

  • Donald D. Chamberlin and Raymond F. Boyce. SEQUEL: A structured english query language. In Proc. SIGFIDET/SIGMOD Workshop, volume 1, 1974.

    Google Scholar 

  • Donald D. Chamberlin, Morton M. Astrahan, Michael W. Blasgen, James N. Gray, W. Frank King, Bruce G. Lindsay, Raymond Lorie, James W. Mehl, Thomas G. Price, Franco Putzolu, Patricia Griffiths Selinger, Mario Schkolnick, Donald R. Slutz, Irving L. Traiger, Bradford W. Wade, and Robert A. Yost. A history and evaluation of System R. Commun. ACM, 24(10):632–646,1981.

    Article  Google Scholar 

  • Ashok K. Chandra and Philip M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proc. STOC, 1977.

    Google Scholar 

  • Surajit Chaudhuri. An overview of query optimization in relational systems. In Proc. PODS, 1998.

    Google Scholar 

  • Chandra Chekuri and Anand Rajaraman. Conjunctive query containment revisited. Theor. Comput. Sci., 239(2):211–229, 2000.

    Article  MATH  MathSciNet  Google Scholar 

  • David L. Childs. Description of a set-theoretic data structure. In Proc. AFIPS, 1968.

    Google Scholar 

  • E. F. Codd. A relational model of data for large shared data banks. Commun. ACM, 13(6): 377–387, 1970.

    Article  MATH  Google Scholar 

  • E. F. Codd. Recent investigations in relational data base systems. In Proc. ACM Pacific, 1975

    Google Scholar 

  • Douglas Comer. The ubiquitous B-tree. ACM Comput. Surv., 11(2):121–137, 1979.

    Article  MATH  Google Scholar 

  • Charles D. Cranor, Theodore Johnson, Oliver Spatscheck, and Vladislav Shkapenyuk. Gigascope: A stream database for network applications. In Proc. SIGMOD, 2003.

    Google Scholar 

  • Creative System Design. Databases. http://online.creativesystemdesigns.com/projects/databases.asp, 2010.

  • Umeshwar Dayal. Of nests and trees: A unified approach to processing queries that contain nested subqueries, aggregates, and quantifiers. In Proc. VLDB, 1987.

    Google Scholar 

  • Jeffrey Dean and Sanjay Ghemawat. MapReduce: simplified data processing on large clusters. Commun. ACM, 51(1):107–113, 2008.

    Article  Google Scholar 

  • O. Deux. The story of O2. IEEE Trans. on Knowl. and Data Eng., 2(1):91–108, 1990.

    Article  Google Scholar 

  • Robert A. Di Paola. The recursive unsolvability of the decision problem for the class of definite formulas. J. ACM, 16(2), 1969.

    Google Scholar 

  • Ronald Fagin. Multivalued dependencies and a new normal form for relational databases. ACM Trans. Database Syst., 2(3):262–278, 1977.

    Article  MathSciNet  Google Scholar 

  • Ronald Fagin. Normal forms and relational database operators. In Proc. SIGMOD, 1979.

    Google Scholar 

  • Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, and H. Raymond Strong. Extendible hashing – a fast access method for dynamic files. ACM Trans. Database Syst., 4(3):315–344, 1979.

    Article  Google Scholar 

  • Ronald Fagin, Phokion G. Kolaitis, Renée Miller, and Lucian Popa. Data exchange: semantics and query answering. Theor. Comput. Sci., 336(1):89–124, 2005.

    Article  MATH  MathSciNet  Google Scholar 

  • Financial Times. The world’s largest companies. Technical Report ft500, Financial Times, 2010.

    Google Scholar 

  • Raphael A. Finkel and Jon Louis Bentley. Quad trees: A data structure for retrieval on composite keys. Acta Inf., 4:1–9, 1974.

    Article  MATH  Google Scholar 

  • Hector Garcia-Molina and Kenneth Salem. Main memory database systems: An overview. IEEE Trans. Knowl. Data Eng., 4(6):509–516, 1992.

    Article  Google Scholar 

  • Hector Garcia-Molina, Jeffrey D. Ullman, and Jennifer Widom. Database Systems: The Complete Book. Prentice Hall Press, second edition, 2008.

    Google Scholar 

  • Georg Gottlob and Christoph Koch. Monadic Datalog and the Expressive Power of Web Information Extraction Languages. J. ACM, 51(1):74–113, 2004.

    Article  MathSciNet  Google Scholar 

  • Georg Gottlob, Christoph Koch, and Reinhard Pichler. Efficient Algorithms for Processing XPath Queries. In Proc. VLDB, 2002a.

    Google Scholar 

  • Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci., 64(3):579–627, 2002b.

    Article  MATH  MathSciNet  Google Scholar 

  • Naga K. Govindaraju, Jim Gray, Ritesh Kumar, and Dinesh Manocha. GPUTeraSort: high performance graphics co-processor sorting for large database management. In Proc. SIGMOD, 2006.

    Google Scholar 

  • Goetz Graefe. The Cascades framework for query optimization. IEEE Data Eng. Bull., 18(3): 19–29, 1995.

    Google Scholar 

  • Jim Gray. A “Measure of transaction processing” 20 years later. IEEE Data Eng. Bull., 28(2): 3–4, 2005.

    Google Scholar 

  • Stéphane Grumbach and Tova Milo. Towards tractable algebras for bags. In Proc. PODS, 1993.

    Google Scholar 

  • Stéphane Grumbach, Leonid Libkin, Tova Milo, and Limsoon Wong. Query languages for bags: expressive power and complexity. SIGACT News, 27(2):30–44, 1996.

    Article  Google Scholar 

  • Ashish Gupta and Inderpal Singh Mumick. Maintenance of materialized views: Problems, techniques, and applications. IEEE Data Eng. Bull., 18(2):3–18, 1995.

    Google Scholar 

  • Ashish Gupta, Inderpal Singh Mumick, and V. S. Subrahmanian. Maintaining views incrementally. In Proc. SIGMOD, 1993.

    Google Scholar 

  • Antonin Guttman. R-trees: A dynamic index structure for spatial searching. In Proc. SIGMOD, 1984.

    Google Scholar 

  • Marc Gyssens and Dirk Van Gucht. The powerset algebra as a natural tool to handle nested database relations. J. Comput. Syst. Sci., 45(1):76–103, 1992.

    Article  MATH  Google Scholar 

  • Marc Gyssens, Dan Suciu, and Dirk Van Gucht. Equivalence and normal forms for the restricted and bounded fixpoint in the nested algebra. Information and Computation, 164 (1):85–117, 2001.

    Article  MATH  MathSciNet  Google Scholar 

  • Thomas Haigh. “A veritable bucket of facts”: Origins of the data base management system. SIGMOD Record, 35(2):33–49, 2006.

    Article  Google Scholar 

  • Sven Hartmann, Sebastian Link, and Klaus-Dieter Schewe. Functional and multivalued dependencies in nested databases generated by record and list constructor. Ann. Math. Artif. Intell., 46(1–2):114–164, 2006.

    Article  MATH  MathSciNet  Google Scholar 

  • Ian Horrocks, Peter F. Patel-Schneider, and Frank van Harmelen. From SHIQ and RDF to OWL: the making of a Web ontology language. Web Semantics: Science, Services and Agents on the World Wide Web, 1(1):7–26, 2003.

    Article  Google Scholar 

  • Yannis E. Ioannidis and Viswanath Poosala. Balancing histogram optimality and practicality for query result size estimation. In Proc. SIGMOD, 1995.

    Google Scholar 

  • ISO. ISO 9075:1987: SQL. International Standards Organization, 1987.

    Google Scholar 

  • ISO. ISO/IEC 9075–4:1996: SQL. Part 4: Persistent Stored Modules (SQL/PSM). International Standards Organization, 1996.

    Google Scholar 

  • ISO. ISO 9075:1999: SQL. International Standards Organization, 1999.

    Google Scholar 

  • Theodore Johnson, S. Muthu Muthukrishnan, Vladislav Shkapenyuk, and Oliver Spatscheck. Query-aware partitioning for monitoring massive network data streams. In Proc. SIGMOD, 2008.

    Google Scholar 

  • Paris C. Kanellakis. Elements of relational database theory. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics (B), pages 1073–1156. Elsevier and MIT Press, 1990.

    Google Scholar 

  • Kothuri Venkata Ravi Kanth, Siva Ravada, and Daniel Abugov. Quadtree and R-tree indexes in Oracle Spatial: a comparison using GIS data. In Proc. SIGMOD, 2002.

    Google Scholar 

  • Arthur M. Keller. Algorithms for translating view updates to database updates for views involving selections, projections, and joins. In Proc. PODS, 1985.

    Google Scholar 

  • Won Kim. On optimizing an SQL-like nested query. ACM Trans. Database Syst., 7(3):443–469, 1982.

    Article  MATH  Google Scholar 

  • Anthony C. Klug. Equivalence of relational algebra and relational calculus query languages having aggregate functions. J. ACM, 29(3):699–717, 1982.

    Article  MATH  MathSciNet  Google Scholar 

  • C. Koch. On the complexity of nonrecursive XQuery and functional query languages on complex values. ACM Trans. Database Syst., 31(4):1215–1256, 2006.

    Article  Google Scholar 

  • Isaac Kunen and Dan Suciu. A scalable algorithm for query minimization. Technical Report 02-11-04, University of Washington, 2002.

    Google Scholar 

  • Neal Leavitt. Whatever happened to object-oriented databases? Computer, 33(8):16–19, 2000.

    Article  Google Scholar 

  • Sang-Won Lee and Bongki Moon. Design of flash-based DBMS: an in-page logging approach. In Proc. SIGMOD, 2007.

    Google Scholar 

  • Maurizio Lenzerini. Data integration: a theoretical perspective. In Proc. PODS, 2002.

    Google Scholar 

  • Alon Y. Levy, Anand Rajaraman, and Joann J. Ordille. Querying heterogeneous information sources using source descriptions. In Proc. VLDB, 1996.

    Google Scholar 

  • Leonid Libkin. Expressive power of SQL. Theor. Comput. Sci., 296(3):379–404, 2003.

    Article  MATH  MathSciNet  Google Scholar 

  • Leonid Libkin. Elements of Finite Model Theory. Springer, 2004.

    Google Scholar 

  • Leonid Libkin and Limsoon Wong. Some properties of query languages for bags. In Proc. DBPL, 1993.

    Google Scholar 

  • Leonid Libkin and Limsoon Wong. Query languages for bags and aggregate functions. J. Comput. Syst. Sci., 55(2):241–272, 1997.

    Article  MATH  MathSciNet  Google Scholar 

  • Witold Litwin. Linear hashing: A new tool for file and table addressing. In Proc. VLDB, 1980.

    Google Scholar 

  • Diana Lorentz. Oracle Database SQL Language Reference. Oracle, 2010.

    Google Scholar 

  • William C. McGee. The information management system (IMS) program product. IEEE Annals of the History of Computing, 31:66–75, 2009.

    Article  MathSciNet  Google Scholar 

  • W. Y. Mok. A comparative study of various nested normal forms. IEEE Trans. on Knowl. and Data Eng., 14(2):369–385, 2002.

    Article  MathSciNet  Google Scholar 

  • Wai Yin Mok, Yiu-Kai Ng, and David W. Embley. A normal form for precisely characterizing redundancy in nested relations. ACM Trans. Database Syst., 21(1):77–106, 1996.

    Google Scholar 

  • T. William Olle. The Codasyl Approach to Data Base Management. John Wiley & Sons, Inc., 1978.

    Google Scholar 

  • Z. Meral Ozsoyoglu and Li-Yan Yuan. A new normal form for nested relations. ACM Trans. Database Syst., 12(1):111–136, 1987.

    Google Scholar 

  • M. Tamer Özsu and Patrick Valduriez. Principles of Distributed Database Systems. Springer, third edition, 2011.

    Google Scholar 

  • Jan Paredaens and Dick Van Gucht. Converting nested algebra expressions into flat algebra expressions. ACM Trans. Database Syst., 17(1):65–93, 1992.

    Article  Google Scholar 

  • Jan Paredaens, Jan Van den Bussche, and Dirk Van Gucht. Towards a theory of spatial database queries. In Proc. PODS, 1994.

    Google Scholar 

  • R. L. Patrick. IMS@Conception. IEEE Annals of the History of Computing, 31(4):62–65, 2009.

    Article  MathSciNet  Google Scholar 

  • Viswanath Poosala, Yannis E. Ioannidis, Peter J. Haas, and Eugene J. Shekita. Improved histograms for selectivity estimation of range predicates. In Proc. SIGMOD, 1996.

    Google Scholar 

  • J. A. Postley. Mark IV: evolution of the software product, a memoir. IEEE Annals of the History of Computing, 20(1):43–50, 1998.

    Article  Google Scholar 

  • Raghu Ramakrishnan and Johannes Gehrke. Database Management Systems. WCB/McGraw-Hill, third edition, 2002.

    Google Scholar 

  • Arnon Rosenthal and César A. Galindo-Legaria. Query graphs, implementing trees, and freely-reorderable outerjoins. In Proc. SIGMOD, 1990.

    Google Scholar 

  • Manfred Schmidt-Schaubß and Gert Smolka. Attributive concept descriptions with complements. Artif. Intell., 48(1):1–26, 1991.

    Article  Google Scholar 

  • Abraham Silberschatz, Henry F. Korth, and S. Sudarshan. Database Systems Concepts. McGraw-Hill, Inc., sixth edition, 2010.

    Google Scholar 

  • P. M. Stocker, P. M. D. Gray, and M. P. Atkinson, editors. Databases – Role & Structure: An Advanced Course. Cambridge University Press, 1984.

    Google Scholar 

  • Michael Stonebraker. Technical perspective – one size fits all: an idea whose time has come and gone. Commun. ACM, 51(12):76, 2008.

    Article  Google Scholar 

  • Michael Stonebraker, Daniel J. Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, Edmond Lau, Amerson Lin, Samuel Madden, Elizabeth J. O’Neil, Patrick E. O’Neil, Alex Rasin, Nga Tran, and Stanley B. Zdonik. C-store: A column-oriented DBMS. In Proc. VLDB, 2005.

    Google Scholar 

  • Dan Suciu. Bounded fixpoints for complex objects. Theor. Comput. Sci., 176(1–2):283–328, 1997.

    Article  MATH  MathSciNet  Google Scholar 

  • V. Tannen, P. Buneman, and L. Wong. Naturally embedded query languages. In Proc. ICDT, 1992.

    Google Scholar 

  • Zahir Tari, John Stokes, and Stefano Spaccapietra. Object normal forms and dependency constraints for object-oriented schemata. ACM Trans. Database Syst., 22(4):513–569, 1997.

    Article  Google Scholar 

  • Boris A. Trakhtenbrot. Impossibility of an algorithm for the decision problem in finite classes. American Mathematical Society Translations Series 2, 23:1–5, 1963.

    Google Scholar 

  • Jeffrey D. Ullman. Principles of Database and Knowledge-Base Systems, volume 1. Computer Science Press, 1988.

    Google Scholar 

  • Jeffrey D. Ullman. Principles of Database and Knowledge-Base Systems, volume 2. Computer Science Press, 1989.

    Google Scholar 

  • Moshe Y. Vardi. Querying logical databases. In Proc. PODS, 1985.

    Google Scholar 

  • Victor Vianu. Databases and finite-model theory. In Proc. Descriptive Complexity and Finite Models, 1996.

    Google Scholar 

  • W3C. XML path language (XPath). http://www.w3.org/TR/xpath/, November 1999.

  • W3C. XML path language (XPath) 2.0. http://www.w3.org/TR/xpath20/, January 2007a.

  • W3C. XQuery 1.0: An XML query language. http://www.w3.org/TR/xquery/, January 2007b.

  • Marianne Winslett. Moshe Vardi speaks out on the proof, the whole proof, and nothing but the proof. SIGMOD Record, 35(1):56–64, 2006.

    Article  Google Scholar 

  • WinterCorp. 2005 TopTen award winners. Technical report, WinterCorp, 2005.

    Google Scholar 

  • L. Wong. Normal forms and conservative extension properties for query languages over collection types. J. Comput. Syst. Sci., 52(3):495–505, 1996.

    Article  MATH  Google Scholar 

  • Carlo Zaniolo. A new normal form for the design of relational database schemata. ACM Trans. Database Syst., 7:489–499, 1982.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

We would like to thank Serge Abiteboul, Georg Gottlob, Evgeny Kharlamov, Yann Ollivier, as well as the editor of this book, Edward K. Blum, for valuable feedback about the content of this chapter.

Author information

Authors and Affiliations

  1. University of Oxford, Oxford, UK

    Michael Benedikt

  2. Télécom ParisTech, Paris, France

    Pierre Senellart

Authors
  1. Michael Benedikt
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pierre Senellart
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michael Benedikt .

Editor information

Editors and Affiliations

  1. , Mathematics Department, University of Southern California, Los Angeles, 90089, California, USA

    Edward K. Blum

  2. , Department of Computer Science, Columbia University, New York, 10027, New York, USA

    Alfred V. Aho

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer Science+Business Media, LLC

About this chapter

Cite this chapter

Benedikt, M., Senellart, P. (2011). Databases. In: Blum, E., Aho, A. (eds) Computer Science. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-1168-0_10

Download citation

  • DOI: https://doi.org/10.1007/978-1-4614-1168-0_10

  • Published:

  • Publisher Name: Springer, New York, NY

  • Print ISBN: 978-1-4614-1167-3

  • Online ISBN: 978-1-4614-1168-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation