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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Serge Abiteboul and Catriel Beeri. On the power of languages for the manipulation of complex values. VLDB J., 4:727–794, 1995.
Serge Abiteboul and Paris C. Kanellakis. Object identity as a query language primitive. J. ACM, 45:798–842, 1998.
Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995.
Serge Abiteboul, Ioana Manolescu, Philippe Rigaux, Marie-Christine Rousset, and Pierre Senellart. Web Data Management. Cambridge University Press, 2012.
Andrea Acciarri, Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, Mattia Palmieri, and Riccardo Rosati. QuOnto: Querying ontologies. In Proc. AAAI, 2005.
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.
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.
Rudolf Bayer and Edward M. McCreight. Organization and maintenance of large ordered indices. Acta Inf., 1:173–189, 1972.
Catriel Beeri, Ronald Fagin, David Maier, Alberto Mendelzon, Jeffrey Ullman, and Mihalis Yannakakis. Properties of acyclic database schemes. In Proc. STOC, 1981.
Michael Benedikt and Christoph Koch. From XQuery to relational logics. ACM Trans. Database Syst., 34(4):1–48, 2009.
Luc Bouganim, Björn Þór Jónsson, and Philippe Bonnet. uFLIP: Understanding Flash IO patterns. In Proc. CIDR, 2009.
Wolfgang Breitling. Histograms – myths and facts. In Proc. Hotsos Symposium on Oracle System Performance, 2005.
Andrea Calì, Georg Gottlob, and Andreas Pieris. Advanced processing for ontological queries. PVLDB, 3(1):554–565, 2010.
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.
R. G. G. Cattell, editor. The Object Database Standard: ODMG 2.0. Morgan Kaufmann, 1997.
Donald D. Chamberlin and Raymond F. Boyce. SEQUEL: A structured english query language. In Proc. SIGFIDET/SIGMOD Workshop, volume 1, 1974.
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.
Ashok K. Chandra and Philip M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proc. STOC, 1977.
Surajit Chaudhuri. An overview of query optimization in relational systems. In Proc. PODS, 1998.
Chandra Chekuri and Anand Rajaraman. Conjunctive query containment revisited. Theor. Comput. Sci., 239(2):211–229, 2000.
David L. Childs. Description of a set-theoretic data structure. In Proc. AFIPS, 1968.
E. F. Codd. A relational model of data for large shared data banks. Commun. ACM, 13(6): 377–387, 1970.
E. F. Codd. Recent investigations in relational data base systems. In Proc. ACM Pacific, 1975
Douglas Comer. The ubiquitous B-tree. ACM Comput. Surv., 11(2):121–137, 1979.
Charles D. Cranor, Theodore Johnson, Oliver Spatscheck, and Vladislav Shkapenyuk. Gigascope: A stream database for network applications. In Proc. SIGMOD, 2003.
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.
Jeffrey Dean and Sanjay Ghemawat. MapReduce: simplified data processing on large clusters. Commun. ACM, 51(1):107–113, 2008.
O. Deux. The story of O2. IEEE Trans. on Knowl. and Data Eng., 2(1):91–108, 1990.
Robert A. Di Paola. The recursive unsolvability of the decision problem for the class of definite formulas. J. ACM, 16(2), 1969.
Ronald Fagin. Multivalued dependencies and a new normal form for relational databases. ACM Trans. Database Syst., 2(3):262–278, 1977.
Ronald Fagin. Normal forms and relational database operators. In Proc. SIGMOD, 1979.
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.
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.
Financial Times. The world’s largest companies. Technical Report ft500, Financial Times, 2010.
Raphael A. Finkel and Jon Louis Bentley. Quad trees: A data structure for retrieval on composite keys. Acta Inf., 4:1–9, 1974.
Hector Garcia-Molina and Kenneth Salem. Main memory database systems: An overview. IEEE Trans. Knowl. Data Eng., 4(6):509–516, 1992.
Hector Garcia-Molina, Jeffrey D. Ullman, and Jennifer Widom. Database Systems: The Complete Book. Prentice Hall Press, second edition, 2008.
Georg Gottlob and Christoph Koch. Monadic Datalog and the Expressive Power of Web Information Extraction Languages. J. ACM, 51(1):74–113, 2004.
Georg Gottlob, Christoph Koch, and Reinhard Pichler. Efficient Algorithms for Processing XPath Queries. In Proc. VLDB, 2002a.
Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci., 64(3):579–627, 2002b.
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.
Goetz Graefe. The Cascades framework for query optimization. IEEE Data Eng. Bull., 18(3): 19–29, 1995.
Jim Gray. A “Measure of transaction processing” 20 years later. IEEE Data Eng. Bull., 28(2): 3–4, 2005.
Stéphane Grumbach and Tova Milo. Towards tractable algebras for bags. In Proc. PODS, 1993.
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.
Ashish Gupta and Inderpal Singh Mumick. Maintenance of materialized views: Problems, techniques, and applications. IEEE Data Eng. Bull., 18(2):3–18, 1995.
Ashish Gupta, Inderpal Singh Mumick, and V. S. Subrahmanian. Maintaining views incrementally. In Proc. SIGMOD, 1993.
Antonin Guttman. R-trees: A dynamic index structure for spatial searching. In Proc. SIGMOD, 1984.
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.
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.
Thomas Haigh. “A veritable bucket of facts”: Origins of the data base management system. SIGMOD Record, 35(2):33–49, 2006.
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.
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.
Yannis E. Ioannidis and Viswanath Poosala. Balancing histogram optimality and practicality for query result size estimation. In Proc. SIGMOD, 1995.
ISO. ISO 9075:1987: SQL. International Standards Organization, 1987.
ISO. ISO/IEC 9075–4:1996: SQL. Part 4: Persistent Stored Modules (SQL/PSM). International Standards Organization, 1996.
ISO. ISO 9075:1999: SQL. International Standards Organization, 1999.
Theodore Johnson, S. Muthu Muthukrishnan, Vladislav Shkapenyuk, and Oliver Spatscheck. Query-aware partitioning for monitoring massive network data streams. In Proc. SIGMOD, 2008.
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.
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.
Arthur M. Keller. Algorithms for translating view updates to database updates for views involving selections, projections, and joins. In Proc. PODS, 1985.
Won Kim. On optimizing an SQL-like nested query. ACM Trans. Database Syst., 7(3):443–469, 1982.
Anthony C. Klug. Equivalence of relational algebra and relational calculus query languages having aggregate functions. J. ACM, 29(3):699–717, 1982.
C. Koch. On the complexity of nonrecursive XQuery and functional query languages on complex values. ACM Trans. Database Syst., 31(4):1215–1256, 2006.
Isaac Kunen and Dan Suciu. A scalable algorithm for query minimization. Technical Report 02-11-04, University of Washington, 2002.
Neal Leavitt. Whatever happened to object-oriented databases? Computer, 33(8):16–19, 2000.
Sang-Won Lee and Bongki Moon. Design of flash-based DBMS: an in-page logging approach. In Proc. SIGMOD, 2007.
Maurizio Lenzerini. Data integration: a theoretical perspective. In Proc. PODS, 2002.
Alon Y. Levy, Anand Rajaraman, and Joann J. Ordille. Querying heterogeneous information sources using source descriptions. In Proc. VLDB, 1996.
Leonid Libkin. Expressive power of SQL. Theor. Comput. Sci., 296(3):379–404, 2003.
Leonid Libkin. Elements of Finite Model Theory. Springer, 2004.
Leonid Libkin and Limsoon Wong. Some properties of query languages for bags. In Proc. DBPL, 1993.
Leonid Libkin and Limsoon Wong. Query languages for bags and aggregate functions. J. Comput. Syst. Sci., 55(2):241–272, 1997.
Witold Litwin. Linear hashing: A new tool for file and table addressing. In Proc. VLDB, 1980.
Diana Lorentz. Oracle Database SQL Language Reference. Oracle, 2010.
William C. McGee. The information management system (IMS) program product. IEEE Annals of the History of Computing, 31:66–75, 2009.
W. Y. Mok. A comparative study of various nested normal forms. IEEE Trans. on Knowl. and Data Eng., 14(2):369–385, 2002.
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.
T. William Olle. The Codasyl Approach to Data Base Management. John Wiley & Sons, Inc., 1978.
Z. Meral Ozsoyoglu and Li-Yan Yuan. A new normal form for nested relations. ACM Trans. Database Syst., 12(1):111–136, 1987.
M. Tamer Özsu and Patrick Valduriez. Principles of Distributed Database Systems. Springer, third edition, 2011.
Jan Paredaens and Dick Van Gucht. Converting nested algebra expressions into flat algebra expressions. ACM Trans. Database Syst., 17(1):65–93, 1992.
Jan Paredaens, Jan Van den Bussche, and Dirk Van Gucht. Towards a theory of spatial database queries. In Proc. PODS, 1994.
R. L. Patrick. IMS@Conception. IEEE Annals of the History of Computing, 31(4):62–65, 2009.
Viswanath Poosala, Yannis E. Ioannidis, Peter J. Haas, and Eugene J. Shekita. Improved histograms for selectivity estimation of range predicates. In Proc. SIGMOD, 1996.
J. A. Postley. Mark IV: evolution of the software product, a memoir. IEEE Annals of the History of Computing, 20(1):43–50, 1998.
Raghu Ramakrishnan and Johannes Gehrke. Database Management Systems. WCB/McGraw-Hill, third edition, 2002.
Arnon Rosenthal and César A. Galindo-Legaria. Query graphs, implementing trees, and freely-reorderable outerjoins. In Proc. SIGMOD, 1990.
Manfred Schmidt-Schaubß and Gert Smolka. Attributive concept descriptions with complements. Artif. Intell., 48(1):1–26, 1991.
Abraham Silberschatz, Henry F. Korth, and S. Sudarshan. Database Systems Concepts. McGraw-Hill, Inc., sixth edition, 2010.
P. M. Stocker, P. M. D. Gray, and M. P. Atkinson, editors. Databases – Role & Structure: An Advanced Course. Cambridge University Press, 1984.
Michael Stonebraker. Technical perspective – one size fits all: an idea whose time has come and gone. Commun. ACM, 51(12):76, 2008.
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.
Dan Suciu. Bounded fixpoints for complex objects. Theor. Comput. Sci., 176(1–2):283–328, 1997.
V. Tannen, P. Buneman, and L. Wong. Naturally embedded query languages. In Proc. ICDT, 1992.
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.
Boris A. Trakhtenbrot. Impossibility of an algorithm for the decision problem in finite classes. American Mathematical Society Translations Series 2, 23:1–5, 1963.
Jeffrey D. Ullman. Principles of Database and Knowledge-Base Systems, volume 1. Computer Science Press, 1988.
Jeffrey D. Ullman. Principles of Database and Knowledge-Base Systems, volume 2. Computer Science Press, 1989.
Moshe Y. Vardi. Querying logical databases. In Proc. PODS, 1985.
Victor Vianu. Databases and finite-model theory. In Proc. Descriptive Complexity and Finite Models, 1996.
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.
WinterCorp. 2005 TopTen award winners. Technical report, WinterCorp, 2005.
L. Wong. Normal forms and conservative extension properties for query languages over collection types. J. Comput. Syst. Sci., 52(3):495–505, 1996.
Carlo Zaniolo. A new normal form for the design of relational database schemata. ACM Trans. Database Syst., 7:489–499, 1982.
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
Corresponding author
Editor information
Editors and Affiliations
Rights 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)