Topic: database queries, joins, and relational algebra

topics > computer science > database > Group: database model

access to data
relationship information

collection class
database agents
database implementation
database keys and indexing
database schema
external search and sort
information retrieval with queries
kinds of relationships between data
knowledge representation
relational database
searching compressed data
set construction
set operations


A relationship can be derived from other relationships in the database. A derived relationship defines a set. This allows someone to extract additional information from a database which is as much data as what was explicitly stored.

Much of the power of a relational database is its dependency on joins to derive relationships. Relations can also be derived by following links, selecting records, projecting record attributes, or by matching contents.

Since a derived relationship can not be modified, it limits what can be stored in the database, and it may say more than should be said. Normal forms for relational databases are designed to avoid problems with joins and the indirect specification of relationships. Derived relationships can be infinite. (cbb 1/90)

Subtopic: relational model up

Quote: relational model is structurally simple; gives a common understanding of data for all kinds of users [»coddEF2_1982]
Quote: relational model easier to use because of tabular data and ad hoc queries
Quote: use a tabular data model to query a database [»rohdWF12_1979]

Subtopic: order independent up

Quote: relations, joins, and group-by deliberately ignore the notion of order; called "area", "bundling", and "glumping" [»bosaR4_1962]

Subtopic: expressible relations up

Quote: the named set of a relational database is a very small subset of the expressible set of relations [»coddEF6_1970]
Quote: in database query languages, queries produce new, implicit types; in functional programming every type is explicit [»wongL9_2000]

Subtopic: relational algebra up

Quote: the relational model is as powerful as the first-order predicate logic in retrieving information [»coddEF_1990]
Quote: relational algebra expresses queries as operations on a relation; relational calculi as predicates that tuples must satisfy [»wegnP10_1986]
Quote: a database relation is a set of tuples, without duplicates [»dateCJ_1998]
Quote: information algebra deals with sets of points in a space; each entity has exactly one datum point in a given property space; e.g., (employee number, hourly payrate) [»bosaR4_1962]

Subtopic: relational queries up

Quote: query a relation using any combination of arguments as knowns and unknowns; an advantage of relational databases [»coddEF6_1970]
Quote: in data retrieval, queries and data descriptions are fairly precise; simple matching is sufficient [»blaiDC1_1996]
Quote: a relational database returns tuples for a query; applications may send updates to the database [»smitKE10_1987]
Quote: a database query returns a network path, i.e., a set of tuples [»rohdWF12_1979, OK]
Quote: select a record occurrence at the path level instead of the record level; this is effective, easy to use, and flexible [»rohdWF12_1979]

Subtopic: projection up

Quote: a projection is a relation without certain columns and without duplicates [»coddEF6_1970]

Subtopic: database joins up

Quote: a natural join is the result of combining two relations using a shared domain [»coddEF6_1970]
Quote: joins match symbols (e.g., employee number) instead of entities (e.g., an employee) [»kentW_1978]
Quote: the relational model defines relationships in two ways: by symbol matching in joins and by coexistence in a tuple [»kentW_1978]
Quote: relational model more flexible because relationships defined by joins [»smitKE10_1987]
Quote: criss-cross hash joins interleaves zoned partitions configured through page maps; low memory and I/O costs; even better if ordered [»gopaRD7_2001]
Quote: databases require efficient queries and joins; no worse than O(n log n) [»wongL9_2000]

Subtopic: group by up

Quote: a glumping function groups by equality; e.g., orders for a part in a back order file (PartNum, QuantityOrdered, Date) [»bosaR4_1962]

Subtopic: web queries up

Quote: for access to large databases, Web provides simple queries of user-entered data with results rendered as hypermedia [»fielRT5_2002]

Subtopic: comprehension syntax, nested relational calculus up

Quote: CPL includes named sub-queries; e.g., organism names [»wongL9_2000]
Quote: Kleisli uses the nested relational calculus (NRC); lambda calculus plus records, and sets [»wongL9_2000]
Quote: nested relational calculus decomposes sets using a restricted form of structural recursion
Quote: Kleisli extends NRC with equality, rationals, arithmetic; some power as SQL [»wongL9_2000]
Quote: neither SQL nor NRC can test if an unordered graph is a chain, along with other properties of unordered graphs

Subtopic: expression tree up

Quote: an expression tree, Expression, is an efficient, in-memory representation of a lambda expression; LINC translates expression trees into SQL [»bierGM10_2007]

Subtopic: query optimization up

Quote: databases require efficient queries and joins; no worse than O(n log n) [»wongL9_2000]
Quote: a variable-byte compression scheme is twice as fast as bitwise compression for query evaluation of web documents
Quote: need efficient translation from a high level data language to the stored representation; necessary for concurrent access to a large data bank [»coddEF6_1970]
Quote: incremental computation of database updates using comprehension syntax; maintains consistency while updating a value; efficient, strict or lazy updates [»nakaH10_2001]

Related Topics up

Group: access to data   (12 topics, 307 quotes)
Group: relationship information   (5 topics, 69 quotes)

Topic: collection class (11 items)
Topic: database agents (10 items)
Topic: database implementation (18 items)
Topic: database keys and indexing (18 items)
Topic: database schema (29 items)
Topic: external search and sort (23 items)
Topic: information retrieval with queries (18 items)
Topic: kinds of relationships between data (16 items)
Topic: knowledge representation (41 items)
Topic: relational database (35 items)
Topic: searching compressed data (9 items)
Topic: set construction (20 items)
Topic: set operations
(12 items)

Updated barberCB 5/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.