Elmasri R., Navathe S.B. Fundamentals of Database Systems

Подождите немного. Документ загружается.

EQUIJOIN and NATURAL JOIN

variations, 159–161

hybrid hash-join, 696

implementing, 689–690

join selection factors, 693–694

multiple relation queries and

JOIN ordering, 718–719

nested-loop joins, 690–693

overview of, 157–158

partition-hash joins, 694–696

Join operations, in QBE, 1094–1095

Join selection factors, 693–694

Join selectivity ratio, 160, 715

Joined tables (relations), 123–124

JPEG image format, 966

K-means clustering algorithm,

1055–1056

KDD (Knowledge Discovery in

Databases), 1036

Key attribute, 209

Key constraints

on entity attributes, 208–209

integrity constraints in databases,

overview of, 68–70

specifying in SQL, 95–96

Key field, sorted files and, 603

Keys

candidate and primary in rela-

tional databases, 518–519

indexes on multiple, 660–661

methods for simple selection, 686

in ODMG object model, 388–390

specifying in XML schema, 430

Keyword queries

overview of, 39

searching with, 995

types of queries in IR systems,

1007

Kleinberg, Jon, 1021

Knowledge-based systems, 932, 1007

Knowledge Discovery in Databases

(KDD), 1036

Knowledge discovery process

data mining in, 1036–1037

goals of, 1037–1038

types of knowledge discovered,

1038–1039

KR (knowledge representation)

aggregation and association,

269–271

classification and instantiation,

268

compared with semantic data

models, 267–268

identification, 269

overview of, 245

specialization and generalization,

269

Label-based security

administrator defining policy for,

853

Oracle Label Security, 868–870

Label Security administrator, 853

Labels, semistructured data and, 417

LANs (local area networks), 44, 879

Large databases, 304

Latches, for short term locks, 802

Late (dynamic) binding, in ODMS,

368

Latency. See Rotational delay (rd)

Lattices, for specialization, 255–256

LCS (local conceptual schema), 889

LDAP (Lightweight Directory Access

Protocol), 919–921

Leaf classes, 265

Leaf-deep trees, 718

Leaf nodes, of tree structures, 646

Learning approaches

classification and, 1051

clustering and, 1054

neural networks and, 1058

Legacy data models, 51

Legacy database systems, 49, 60

Legal relation states (legal exten-

sions), 514

Levels of isolation, of transaction,

755

Libraries of functions. See Function

calls, database programming

with

Lifespan temporal attributes,

953–954

Lightweight Directory Access

Protocol (LDAP), 919–921

LIKE comparison operator, in string

pattern matching, 105

Linear hashing, 614–616

Linear regression, 1058

Linear searches

with brute force algorithm,

685–686

cost functions for

SELECT opera-

tions, 713

of file blocks on disk, 597

of files, 602

Lines, on maps, 960

Link structure, of Web pages,

1020–1021

Linked allocation, of file blocks on

disk, 597

Links, in UML class diagrams, 227

LIS (local internal schema), 889

List constructor, 359

Literals (values), 378–382

atomic formulas as, 973

atomic literals, 378

collection literals, 382

complex types for, 358–360

in OO systems, 358

structured literals, 378

Loading/converting data, in data-

base application life cycle, 308

Loading databases, initial state and,

Loading utility, for loading data files

to database, 42–43

Local area networks (LANs), 44, 879

Local conceptual schema (LCS), 889

Local internal schema (LIS), 889

Local query optimization, 902

Local schema, in federated database

architecture, 890

Localization, in distributed query

processing, 901

Location analysis, for spatial data-

bases, 959

Location transparency, 880

Lock compatibility table, 792

Lock manager subsystem, in DBMS,

779

Lock table, 779

Locking. See also Two-phase locking

for concurrency control, 777

granularity level in, 795–796

index locking and predicate lock-

ing, 801

multiple granularity level,

796–798

used in indexes, 798–800

Locks

binary, 778–780

certify locks, 792–793

conversion of, 782

shared/exclusive (read/write),

780–782

in two-phase locking, 778

Log buffers, 753–754

Log records, 753

Log sequence number (LSN), 822

Logic databases, 932. See also

Deductive database systems

Logic programming, 970

Logical (conceptual) level, goodness

of relation schemas and, 501

Logical data independence, in three-

schema architecture, 35–36

Logical data models, 341

1152 Index

Logical definitions, of domains, 61

Logical design, 9, 202

Logical field references, for relation-

ships between file records,

617

Logical indexes, vs. physical indexes,

668

Logical operators. See AND, OR,

NOT connectives

Logical ordering, secondary indexes

and, 642

Logical theory, in ontologies, 272

Logs/logging

auditing and, 839–840

database recovery and, 808

tracking transaction operations,

753–754

during undo process, 821

Long-haul networks, 879

Long text strings, in HTML files,

484

Loss of integrity, as security threat,

836

Lossless (nonadditive) join property

decomposition into 3NF rela-

tions, 560–563

decomposition into 4NF rela-

tions, 570

normal forms and, 518

overview of, 553–556

successive, 557

testing binary decompositions for,

557

Lossy design, 554

Lost updates, in concurrency con-

trol, 748–749

Low-level data models, 30

Low-level (procedural) DMLs,

37–38

LSN (log sequence number), 822

MAC (mandatory access control)

classification attributes, tuple

classification, and multilevel

relations, 848–850

comparing with discretionary

access control, 850–851

overview of, 847

security classes in, 847–848

Macro life cycle, 307

Magnetic tape

for archiving and backup, 586

as storage devices, 592–593

Main memory, 585

Main memory database, 585

Main or master files, 605

Maintenance

database, 6

of derived data, 943

maintenance costs in choosing

DBMS, 323

Maintenance personnel, 17

Mandatory access control. See MAC

(mandatory access control)

Manipulating databases

overview of, 5

University student database

example, 9

Manufacturing, applying data min-

ing to, 1060

Map data, as spatial data, 959

Mapping

data model mapping. See Data

model mapping

from EER model to relational

model. See EER-to-Relational

mapping

from EER schema to ODB

schema, 397–398

from ER model to relational

model. See ER-to-Relational

mapping

between levels of three-schema

architecture, 35

Query mapping, 901

SELECT command, 97

tuples, 64

Market-basket data, association

rules and, 1040

Marketing, applying data mining to,

1060

Mass storage devices, 585

Massively parallel processing

(MMP), 1079

Master files, 605

Materialized evaluation, converting

query trees into query execu-

tion plans, 710

Materialized views

active rules for maintaining con-

sistency of, 943

data warehouses compared with,

1079

Mathematical relations, 59, 63

Mathematical set theory, 104

MAX function

aggregate functions in SQL,

124–125

grouping and, 166

implementing, 698

MBR (minimum bounding rectan-

gle), in R-Trees, 962

Measurement operations, for spatial

databases, 958

Mechanical arm, on hard disks, 591

Memory hierarchies, storage devices

and, 584–586

Memory usage, cost components of

query execution, 711

Menu-based interfaces, 38

Merge phase, of sort-merge strategy,

683

Messages, passing to objects, 356

Meta-classes, in knowledge repre-

sentation, 268

Meta-data

in DBMS catalog, 33

DBMSs managing, 306

defined, 5

describing structure of primary

database, 10–11

Metadata repository, in data ware-

housing, 1078

Metasearch engines, 1018

Methods. See also Operations

of object classes, 50

of object operations, 356

Metric operators, as spatial operator,

961

Metrics, for evaluating relevance in

IR, 1015–1017

MGL (multiple granularity locking),

797–798

Micro life cycle, 307

Middle tier, in three-tier architec-

ture, 48

Middle-tier Web servers, PHP, 482

Middleware software

federated databases and, 886

heterogeneous DDBMSs and, 50

MIN function

aggregate functions in SQL,

124–125

grouping and, 166

implementing aggregate opera-

tions, 698

Minimal model, for interpretation

of rules in deductive databases,

976

Minimal sets, of functional depen-

dencies, 549–551

Minimum bounding rectangle

(MBR), in R-Trees, 962

Minimum cardinality constraint,

217

Miniworld, 4

MINUS operation, in relational

algebra, 152–155

Index 1153

Mirroring (shadowing), RAID, 619

Mixed fragmentation, in distributed

databases, 896

Mixed strategy

for schema design, 316

for view integration process, 319

Mixed transactions, 322

MMP (massively parallel process-

ing), 1079

Model mapping. See Data model

mapping

Model-theoretic interpretation, of

rules in deductive databases,

976

Models, data. See Data models

Models, for interpretation of rules

in deductive databases, 976

Models, spatial, 959–960

Modification anomalies, avoiding

redundant information in

tuples, 509

Modifier operations, objects, 362

Modify operations, on files, 600.

See also Update operations

Modules

client and server, 29

DBMS, 16

DBMS component, 40–42

MOLAP (multidimensional OLAP),

1079

Monitoring and maintenance phase,

in database application life

cycle, 308

Morphological analysis, in semantic

model for IR, 1006

Movable-head disks, 591

MPEG image format, 966

Multidatabase systems

recovery techniques for, 825–826

types of distributed databases,

885

Multidimensional associations,

1048–1049

Multidimensional data models

decision-support technologies,

1069

dimension tables and fact tables,

1073

indexing, 1074–1075

roll-up and drill-down displays,

1072

schemas, 1073–1074

Multidimensional OLAP (MOLAP),

1079

Multilevel indexes

B-trees, 649–652

B+-trees, 652–655

dynamic, 646–647

overview of, 643–646

search, insertion, deletion,

655–660

search trees compared with,

647–649

variations on B-trees and

B+-trees, 660

Multilevel relations, in mandatory

access control, 848

Multimedia databases

analysis of audio data sources,

969

analysis of images, 967–968

object recognition, 968–969

overview of, 965–967

semantic tagging of images, 969

types of databases, 3

Multiple granularity locking (MGL),

797–798

Multiple hashing, in collision reso-

lution, 609

Multiple inheritance

in ODBs (object databases), 368

ODL (object definition language)

and, 395

subclasses and, 256

Multiple relations

options for mapping specializa-

tion or generalization, 295

queries and JOIN ordering,

718–719

Multiplicities, in UML class dia-

grams, 227

Multiprocessor systems, 879

Multiprogramming operating

systems, 744–745

Multiset (bag), of tuples, 103–105,

150

Multiuser DBMS systems, 49

Multiuser transactions

in databases, 13–14

processing system, 744–745

Multivalued attributes

declaring, 397

in ER model, 206

mapping ER-to-Relational data

models, 291

Multivalued dependency. See MVD

(multivalued dependency)

Multiversion concurrency control,

777, 791–793

Multiway joins, 124, 689

Mutually exclusive role, in role-

based access control, 851

MVD (multivalued dependency)

4NF and, 531–533

formal definition of, 533

inference rules for, 568

relational model constraints, 68

N-ary

relationship types, 291–292

strategies for view integration

process, 319

N-tier architectures, for Web appli-

cations, 47–49

Named iterator, SQLJ, 461

Named queries, in OQL, 402–403

Namespaces, XML, 428–429

Naming conventions

for constraints, in SQL, 96–97

for relations, 62

for schema constructs, 222

Naming mechanism, object persis-

tence and, 363

Naming transparency, 880

NAS (network-attached storage),

622–623

Native XML format

DBMSs, 49

overview of, 425

storing, 431

NATURAL JOIN operations,

123–124, 159–161

Natural language interfaces, 39

Natural language queries, 1009

Navigational searches, 996

Nearest neighbor, in spatial queries,

961

Negation symbol, in QBE, 1096

Negative associations, 1049–1050

Negative literals, in Datalog lan-

guage, 973

Nested-loop joins

cost functions for, 716

factors impacting performance of,

690–693

implementing, 689

Nested queries

correlated, 119–120

innermost, 119

overview of, 117–119

Nested relations

INF and, 521

SQL and, 111

Network-attached storage (NAS),

622–623

Network data models

classifying DBMSs and, 49

overview of, 51

types of data models, 31

1154 Index

Network transparency, 880

Neural networks, 1058

NO-UNDO/REDO recovery tech-

nique

based on deferred update, 815–817

overview of, 807, 809

No waiting algorithm, for deadlock

prevention, 787

Nodes, of tree structures, 646

Non-identifying relationships, in

Rational Rose, 340

Nonadditive (lossless) join property

decomposition into 3NF rela-

tions, 560–563

decomposition into 4NF rela-

tions, 570

normal forms and, 518

overview of, 553–556

successive, 557

testing binary decompositions for,

557

Nonprime attributes, 519

Nonprocedural languages, relational

calculus as, 174

Nonrecoverable schedules, transac-

tions, 758

Nonrecursive queries, evaluating in

Datalog, 981–983

Nonrelevant sets, in probabilistic

model for IR, 1005

Nonrepeatable reads, transaction

support in SQL, 771

Nonserial schedules, 761

Nontime-varying attributes, 953

Nonvolatile storage, in databases,

586

Normal forms

based on primary keys, 516–517

Boyce-Codd normal form

(BCNF), 529–531, 559–560

domain-key normal form

(DKNF), 531–533, 574–575

fifth normal form (5NF), 534–535

first normal form (1NF), 65,

519–523

fourth normal form (4NF),

531–534, 568–570

insufficiency of, 552

normalization of relations, 517

practical use of, 518

second normal form (2NF), 523,

526–527

temporal normal form, 952

tests, 517

third normal form (3NF),

523–525, 528, 558–563

Normalization

algorithms. See algorithms, nor-

malization

automated tools for database

design, 344

functional dependencies and, 545

relational database design based

on, 60

of relational schema design, 516

of relations, 517–518

NOT EXISTS functions, SQL,

120–122

NOT logical connective. See AND,

OR, NOT connectives

NOT NULL, specifying attribute

defaults in SQL, 94

Notation

diagrammatic, 516

in ER diagrams, 221–223,

1083–1085

for Prolog/Datalog languages,

970–973

for query graphs, 179–180,

701–703

for query trees, 163–165, 701–703

in relational data model, 66–67

in UML class diagrams, 226–228

Notification application, for active

databases, 942

NULL values

access control integrity, 850

comparisons involving, 116–117

constraints, 68–70

in ER model, 206

examples illustrating, 116

grouping tuples with, 128

problems in relational design,

563–565

reducing in tuples, 509–510

specifying attribute defaults in

SQL, 94

in tuples, 65–66

Numeric arrays, PHP, 487

Numeric data types, in SQL, 92

Object Data Management Group.

See ODMG (Object Data

Management Group)

Object data management systems.

See ODMS (object data man-

agement systems)

Object data models

classifying DBMSs and, 49

converting to/from logical

models, 341

object modeling, 245

ODMG object model, 376

overview of, 50

spatial data, 960

types of data models, 31

Object databases. See ODBs (object

databases)

Object definition language. See ODL

(object definition language)

Object diagrams, UML, 330

Object Identifiers. See OIDs (object

identifiers)

Object identifiers, in SQL, 111

Object lifeline, in sequence dia-

grams, 332

Object-orientation (OO), 355–357

Object-oriented analysis (OOA),

1083

Object-oriented database manage-

ment systems (OODBMSs), 49

Object-oriented databases. See

OODBs (object-oriented data-

bases)

Object-oriented programming

languages. See OOPLs (object-

oriented programming

languages)

Object recognition, in images,

968–969

Object-relational database manage-

ment systems (ORDBMS), 354

Object-relational (extended rela-

tional) systems, 51, 111

Object-relational model

creating tables based on UDTs, 374

encapsulation of operations,

374–375

ODB extensions to SQL, 369–370

OIDs using reference types,

373–374

specifying inheritance and over-

loading of functions, 375–376

specifying relationships via refer-

ence, 376

UDT (user-defined types) and

complex structures, 370–373

Objects

atomic (user-defined) objects,

386–388

complex types for, 358

in ODMG object model, 377–378

operations, 362–363

persistence of, 19, 363–364

state and behavior components

of, 355

visible/hidden attributes of, 361

Occurrences, current set in database

state, 32

Index 1155

ODBC (Open Database

Connectivity)

client-side API for calling

DBMSs, 47

data mining tools using, 1060

library of functions, 448

ODBs (object databases)

bibliographic references, 412–413

complex types for objects and lit-

erals, 358–360

conceptual design, 395–396

encapsulation of operations,

361–363

extensions to SQL, 369–370

list of concepts in, 369

mapping EER schema to ODB

schema, 397–398

multiple and selective inheritance,

368

OID (object identifiers), 357–358

OO (object-orientation) concepts

and features, 355–357

overview of, 353–355

persistence of objects, 363–364

polymorphism (operator over-

loading), 367–368

selective inheritance, 368

summary and exercises, 408–411

type hierarchies and inheritance,

364–367

ODL (object definition language)

binding ODL constructs to C++,

407–408

inheritance and, 395

in ODMG standard, 376

supporting semantic constructs of

ODMG object model, 390

type constructors in, 359–360

University student database

example, 391–395

ODMG (Object Data Management

Group)

C++ language binding in, 407

OQL (object query language) in

ODMG standard, 398

standards, 354, 376

ODMG object model

atomic (user-defined) types,

386–388

built-in interfaces and classes,

383–385

extents, keys, and factory objects,

388–390

inheritance in, 383

literals in, 378–382

objects in, 377–378

ODL (object definition language)

and, 390–395

overview of, 376–377

ODMS (object data management

systems). See also ODBs (object

databases)

complex types for objects and lit-

erals, 358

early (static) binding and late

(dynamic) binding, 368

high-level query languages used

by, 361

list of concepts in, 369

OIDs, 357, 377–378

overview of, 353

standard for, 376

Offline, storing data, 587

OIDs (object identifiers)

comparing RDB design with

ODB design, 395–396

ODB features included in SQL,

370

in ODMG object model, 377–378

reference types, 373–374

unique identity and, 357–358, 369

Okapi relevance system, in proba-

bilistic model for IR, 1006

OLAP (online analytical processing)

data mining tools, 1061

data warehousing and, 1067–1068

overview of, 3

relational and multidimensional,

1079

OLTP (online transaction process-

ing)

classifying DBMSs by purpose, 50

database support for, 1068

sharing data and multiuser trans-

actions, 13

transaction processing and, 79

Online analytical processing. See

OLAP (online analytical pro-

cessing)

Online data storage, 587

Online directories, 919–921

Online transaction processing. See

OLTP (online transaction pro-

cessing)

Ontologies

concepts, 267–268

defined, 272

OWL (Web Ontology Language),

969

Semantic Web and, 272–273

Web content analysis and,

1023–1024

OO (object-orientation), 355–357

OOA (object-oriented analysis),

1083

OODBMSs (object-oriented data-

base management systems), 49

OODBs (object-oriented databases)

attribute versioning for incorpo-

rating time in, 953–954

complexity of data and, 24

persistent storage and, 19

OOPLs (object-oriented program-

ming languages)

bindings to, 376

class declarations of, 364

instance variables in, 356

ODBs closely coupled with, 363

OO concepts, 355–356

Open addresses, collision resolution,

608

Open Database Connectivity. See

ODBC (Open Database

Connectivity)

Open operation, on files, 599

Operating costs, in choosing a

DBMS, 323–324

Operating systems. See OSs (operat-

ing systems)

Operations. See also Functions;

Methods

comparing RDB design with

ODB design, 396

in data models, 30

database, 12

in database application life cycle,

308

database design and, 201

encapsulation of, 361–363, 369

on files, 599–601

objects, 362–363

in ODMG object model, 387

pipelining, 700

query processing and optimizing,

700

transaction, 751–752

transformation rules for relation-

al algebra operations, 706–708

in UML class diagrams, 227

Operations, in relational data model

Delete operation, 77–78

Insert operation, 76–77

overview of, 75–76

Update (Modify) operation, 78–79

Operators

arithmetic operators in SQL,

105–106

Boolean, 1007

1156 Index

collection operators in OQL,

403–405

comparison operators in SQL, 98

concatenate operator in PHP, 485

grouping operator in QBE,

1095–1098

logical connectives. See

AND, OR,

NOT connectives

overloading. See Polymorphism

(operator overloading)

relational, 980–981, 983

SELECT operator (σ), 147–149

spatial, 960–961

Operators, database workers behind

the scene, 17

Optical jukebox memories, 586

Optimization, in data mining, 1038

Optimizing queries. See Query pro-

cessing and optimizing

Optional fields, in file records, 595

OQL (object query language)

collection operators and, 403–405

extracting single elements from

singleton collections, 403

group by clause in, 405–406

in ODMG standard, 376, 398

ordered (indexed) collection

expressions, 405

overview of, 398–399

query results and path expres-

sions, 400–402

simple OQL queries, database

entry points, and iterator vari-

ables, 399–400

specifying views as named

queries, 402–403

OR logical connective. See AND, OR,

NOT connectives

Oracle

Cartridge, 931

distributed databases, 915–919

query optimization in, 721–722

Oracle Internet Directory, 919–921

Oracle Label Security

architecture of, 869

combining data labels and user

labels, 869–870

overview of, 868

virtual private database technolo-

gy, 868–869

ORDBMS (object-relational data-

base management systems), 354

ORDER BY clause, SQL

ordering query results, 106–107

in retrieval queries, 129–130

sorting query results, 682–683

Order preserving functions, hashing

and, 609

Ordered (indexed)

collection expressions in OQL, 405

cost functions for

SELECT opera-

tions, 713

query results in SQL, 106–107

Ordered (sorted files), in records,

603–606

Ordering field, file organization and,

603

Ordering key, sorted files and, 603

Organization context, for database

systems, 304–307

OSs (operating systems)

DBMS access and disk read/write,

multiprogramming, 744–745

support for transaction process-

ing in distributed databases,

909

OUTER JOIN operations

implementing, 699–700

vs. inner joins, 160–161

overview of, 169–170

in SQL, 123–124

Outer queries, 117

OUTER UNION operation, in rela-

tional algebra, 170–171

Outliers, spatial, 965

Overflow (transaction) files, 605

Overlapping

entity sets, 253

specialization and, 264

OWL (Web Ontology Language),

969

Owner accounts, granting/revoking

privileges, 843–844

Package diagrams, UML, 330

PageRank algorithm, 1021

Parallel architecture, for servers,

1079

Parallel database management

systems, vs. distributed archi-

tecture, 887–888

Parallel processing

on disks, 593–594

handling multiple processes, 745

Parameterized statements (bind

variables), protecting against

SQL injection, 858

Parameters

disk blocks (pages), 1087–1089

SQL/PSM (SQL/Persistent Stored

Modules), 474

Parametric users, interfaces for, 39

Parser, checking query syntax with,

679

Partial categories, 260

Partial dependencies, 523

Partial keys, 219

Partial order, of transaction sched-

ule, 757

Partial specialization, 253–254, 264

Partially committed state, transac-

tions, 752

Partially replicated catalogs, 913

Participation constraints, on binary

relationships, 217

Partition algorithm, for local fre-

quent itemsets, 1047

Partition-hash joins

methods for implementing joins,

690

overview of, 694–696

Partitioned hashing, 661–662

Passwords, DBAs assigning, 839

Path expressions

dot notation for build path

expressions in SQL, 376

in OQL, 400

specifying with XPath, 432–434

Patterns

analysis phase of Web usage

analysis, 1027

data mining for discovering, 1057

substring pattern matching in

SQL, 105–106

within time series, 1039

PEAR (PHP Extension and

Application Repository), 491

Peer-to-peer database systems, 915

Performance

advantages of distributed data-

bases for, 882

DBMS utilities for monitoring, 43

Persistence

collections, 367

data, 586

objects, 363–364, 378

Persistent storage, of program

objects in databases, 19

Persistent stored modules (PSM),

474–476

Personal databases, 305

Personalization, of information in

Web searches, 1019

Personnel costs, in choosing a

DBMS, 323–324

PGP (Pretty Good Privacy), 854

Phantom records, concurrency con-

trol techniques, 800–801

Index 1157

Phantoms, transaction support in

SQL, 771

PHP

arrays, 486–488

bibliographic references, 497

collecting data from forms and

inserting records, 493–494

connecting to databases, 491–493

features, 484–485

functions, 488–490

overview of, 481–482

retrieval queries, 494–495

server variables and forms,

490–491

simple example of, 482–484

summary and exercises, 496–497

variables, data types, and con-

structs, 485–486

PHP Extension and Application

Repository (PEAR), 491

Phrase queries, types of queries in

IR systems, 1008

Physical clustering, of records on

disks, 617

Physical data independence, in

three-schema architecture, 36

Physical data models, 30

Physical database design. See also

Database design

bibliographic references, 740

data organization in, 587

denormalization as design deci-

sion related to query speed,

731–732

in ER (Entity-Relationship)

model, 202

factors influencing, 727–729

indexing decisions, 730–731

overview of, 9, 326–327

summary and exercises, 739–740

tuning and, 735–736

Physical database file structures, 583

Physical database phase, in database

design, 311

Physical indexes

vs. logical, 668

ordering primary and clustering

indexes, 642

Physical problems/catastrophes,

recovery needed due to, 751

Physical relationships, between file

records, 617

Pile file (heap), 602

Pipelined evaluation, converting

query trees into query execu-

tion plans, 710

Pipelining, combining operations

using, 700

Pivoting (rotation)

functionality of data warehouses,

1078

working with data cubes,

1070–1072

PL/SQL

designing database programming

language from scratch, 449

impedance mismatch and, 450

writing database applications

with, 447

Plaintext, 864

Point events (facts), in temporal

databases, 946

Pointers, blocks of data and, 597

Points

on maps, 959–960

in temporal databases, 945

Policies

access control for e-commerce

and Web, 854–855

flow policies, 860

for label-based security, 853

security policies, 836

Polygons, on maps, 960

Polyinstantiation, in mandatory

access control, 849–850

Polymorphism (operator overload-

ing)

defined, 369

in OO systems, 357

overview of, 367–368

specifying in SQL, 375–376

populating (loading) databases, 33

Populations, in statistical database

security, 859

Positional iterator, SQLJ, 461–462

Positive literals, in Datalog language,

973

Precedence graph (serialization

graph), 763–765

Precision metrics

finding relevant information and,

1019

measures of relevance in IR,

1015–1017

Precision, vs. security, 841

Precompilers

DML commands and, 42

embedded SQL and, 452

in SQL programming, 449

Predicate-defined (condition-

defined) subclasses, 252, 264

Predicate dependency graph, 982

Predicate locking, 801

Predicates

as arity or degree of p, 973

built-in, 972–973

fact-defined and rule-defined, 978

interpretation of, 976

in Prolog languages, 970–972

relational schemas and, 66

Prediction, as goal of data mining,

1037

Preprocessors

embedded SQL and, 452

in SQL programming, 449

in Web usage analysis, 1025–1027

Presentation layer (client), in three-

tier client/server architecture,

892

Pretty Good Privacy (PGP), 854

Primary file organization

B-trees as, 651

data organization and, 587

Primary indexes

cost functions for

SELECT opera-

tions, 713

methods for simple selection, 686

for ordered records (sorted files),

605

overview of, 633–635

searching nondense multilevel

primary index, 646

tables comparing index types, 642

types of ordered indexes, 632

PRIMARY KEY clause, CREATE

TAB LE command, 95

Primary keys

defined, 519

normal forms based on, 516–517

primary indexes and, 633

relational model constraints, 69

Primary site, concurrency control

techniques for distributed data-

bases, 910–911

Primary storage, 584

Prime attributes, 519, 526

Printer servers, in client/server

architecture, 45

Privacy

information privacy vs. informa-

tion security, 841–842

issues in database security,

866–867

protecting in statistical databases,

859

Private keys, in public (asymmetric)

key algorithms, 864

Privileged software, 19

1158 Index

Privileges

discretionary, 842–844

granting/revoking, 111, 844–846

limits on propagation of, 846–847

unauthorized escalation and

abuse, 855, 858

views for specifying, 844

Proactive updates, valid time rela-

tions and, 949

Probabilistic model, for information

retrieval, 1005–1006

Procedural DMLs, 37–38

Process-driven design, 310

PROCESS RULES, in active data-

base systems, 938

Processes

in database design, 322

multiprogramming and, 744

Processors, parallel, 1079

Program-data independence, 11–12,

23–24

Program-operation independence, 12

Program variables, 599

Programming languages

advantages/disadvantages of, 477

approaches to database program-

ming, 449

DBMS, 36–38

impedance mismatch and, 450

object-orientation creating com-

patibility between, 369

Web databases. See PHP

XML, 432–436

Programs, insulation between pro-

grams and data, 11–13

PROJECT operations

algorithms for, 696–697

Query processing and optimizing,

696–697

in relational algebra, 149–150

Projection attributes,

SELECT com-

mand and, 98

Projective operators, types of spatial

operators, 961

Prolog language. See also Datalog

language

logic programming and, 970

notation, 970–973

Proof-theoretic interpretation, of

rules in deductive databases,

975

Properties, of association rules, 1041

Properties of relational decomposi-

tions

dependency preservation,

552–553

dependency-preserving and non-

additive join decomposition

into 3NF schemas, 560–563

dependency-preserving decompo-

sition into 3NF schemas,

558–559

insufficiency of normal forms

and, 552

nonadditive join decomposition

into BCNF schemas, 559–560

nonadditive (lossless) join,

553–556

overview of, 544, 551

successive nonadditive join

decompositions, 557

testing binary decompositions for

nonadditive join property,

553–556

Protocols

concurrency control, 777

deadlock prevention, 785–787

for ensuring serializability of

transaction schedules, 767–768

Proximity queries, 1008

PSM (Persistent stored modules),

474–476

Public (asymmetric) key algorithms,

863–865

Public keys, in public (asymmetric)

key algorithm, 864

Publishing XML documents, 431

Punctuation marks, text preprocess-

ing in information retrieval,

1011

Pure time conditions, 955

QBE (Query-By-Example)

basic retrieval in, 1091–1095

domain calculus and, 183, 185

grouping, aggregation, and data-

base modification in,

1095–1098

overview of, 1091

QMF (Query Management Facility),

185

Quadtrees, 963

Qualified aggregations, in UML class

diagrams, 228

Qualified associations, in UML class

diagrams, 228

Qualifier conditions, XPath, 432

Quality control, data warehousing

and, 1080

Quantifiers

collection operators in OQL,

403–405

existential and universal, 177–178

transforming, 180

using in queries, 180–182

Queries. See also OQL (object query

language); SQL (Structured

Query Language)

content-based retrieval, 965

database tuning and, 736–738

defined, 6

design decisions related to query

speed, 731–732

evaluating nonrecursive Datalog

queries, 981–983

information retrieval, 1007–1009

interactive interface for, 40

IR systems, 1007–1009

keyword-based, 39

modes of interaction in IR sys-

tems, 999

physical database design and,

728–729

processing in databases, 19–20

in Prolog languages, 973

retrieval queries from database

tables, 494–495

spatial, 958, 961

statistical, 859

TSQL2, 954–956

Query blocks, 681

Query-By-Example. See QBE

(Query-By-Example)

Query compilers, 41

Query decomposition, 905–907

Query execution plans

converting query trees into,

709–710

creating, 679

Query graphs

creating, 679

notation for, 179–180, 701–703

Query languages

DML as, 38

for federated databases, 886

SQL. See also SQL (Structured

Query Language)

TSQL2. See also SQL (Structured

Query Language)

Query Management Facility (QMF),

185

Query mapping, 901

Query modification, 135

Query optimizer, 41, 679

Query processing and optimizing

aggregate functions, 698–699

bibliographic references, 725

catalog information used in cost

functions, 712–713

Index 1159

converting query trees into query

execution plans, 709–710

cost components of query execu-

tion, 711–712

cost functions for

JOIN, 715–718

cost functions for

SELECT,

713–715

DBMS module for, 20

disjunctive selection conditions,

688

external sorting, 682–685

heuristic algebraic optimization

algorithm, 708–709

heuristic optimization of query

trees, 703–706

heuristics used in query optimiza-

tion, 700–701

hybrid hash-join, 696

implementing

JOIN operations,

689–690

implementing

SELECT opera-

tions, 685

join selection factors, 693–694

multiple relation queries and

JOIN ordering, 718–719

nested-loop joins, 690–693

notation for query trees and

query graphs, 701–703

operations, 700

OUTER JOIN operations, 699–700

overview of, 679–681

partition-hash joins, 694–696

PROJECT operations, 696–697

query optimization in Oracle,

721–722

search methods for complex

selection, 686–687

search methods for simple selec-

tion, 685–686

selectivity and cost estimates in

query optimization, 710–711

selectivity of conditions and,

687–688

semantic query optimization,

722–723

set operations, 697–698

summary and exercises, 723–725

transformation rules for relation-

al algebra operations, 706–708

translating SQL queries into rela-

tional algebra, 681–682

Query processing and optimizing, in

distributed databases

data transfer costs for distributed

query processing, 902–904

distributed query processing

using semijoin operation, 904

overview of, 901–902

query update and decomposition,

905–907

Query results

cursors for looping over tuples in,

450

ordering, 106–107

path expressions and, 400–402

retrieval queries from database

tables, 494–495

Query (transaction) server, in two-

tier client/server architecture,

Query trees

converting into query execution

plans, 709–710

creating, 679

notation for, 163–165, 701–703

optimization of, 703–706

R-Trees, for spatial indexing, 962

RAID (Redundant Array of

Inexpensive Disks)

levels, 620–621

overview of, 617–619

performance improvements,

619–620

reliability improvements, 619

RAM (Random Access Memory),

585

Random access storage devices, 592

Randomizing function (hash func-

tion), 606

Range queries, 686, 961

Range relations, of tuple variables,

175–176

Rational Rose

data modeler, 338

database design with, 337

tools and options for data model-

ing, 338–342

RBAC (role-based access control),

851–852

RBG (red, blue, green) colors, 967

RDBMS (relational database man-

agement systems)

creating indexes, 731

ORDBMS (object-relational data-

base management systems),

354

providing application flexibility,

23–24

two-tier client/server architec-

tures and, 46

RDBs (relational databases)

designing. See relational database

design

overview of, 395–396

schemas. See relational database

schemas

RDF (Resource Description

Framework), 436

Reachability, of objects, 363

Read command, hard disks, 591

Read-only transaction, 745

READ operation, transactions, 751

Read (or Get) operation, on files, 600

Read phase, of optimistic concur-

rency control, 794

Read-set, of transaction, 747

Read timestamp, 789

Read-write conflicts, in transaction

schedules, 757

Read/write heads, on hard disks, 591

Read/write, OSs controlling disk

read/write, 40

Read-write transactions, 745–747

read_item(X), 746

Real-time database technology, 3

Reasoning mechanisms, in knowl-

edge representation, 268

Recall metrics, in IR, 1015–1017,

1019

Recall/precision curve, in IR, 1017

Record-at-a-time DMLs, 38

Record-based data models, 31

Record pointers, 609

Records. See also Files (of records)

anchor record (block anchor), 633

blocking, 597

catalog information used in query

cost estimation, 712

fixed-length and variable-length,

595–597

inserting, 493–494

mixed, 616–617

ordered (sorted files), 603–606

phantom records, concurrency

control techniques, 800–801

placing file records on disk, 594

spanned/unspanned, 597–598

in SQL/CLI, 464–468

types of, 594–595

unordered (heap files), 601–602

Recoverability, transaction sched-

ules based o, 757–759

Recovery. See also Backup and

recovery; Database recovery

techniques

1160 Index

transaction management in dis-

tributed databases, 912–913

types of failures and, 750–751

Recursive closure operations, in

relational algebra, 168–169

Recursive relationships, 168, 215

Recursive rules, in Prolog languages,

972

Red, blue, green (RBG) colors, 967

REDO phase, of ARIES recovery

algorithm, 823

Redo transaction, 753

REDO, write-ahead logging and,

810–811

Redundancy, controlling in data-

bases, 17–18

Redundant Array of Inexpensive

Disks (RAID). See RAID

(Redundant Array of

Inexpensive Disks)

REF keyword, specifying relation-

ships via reference, 376

Reference types, OIDs using,

373–374

References

foreign key, 73

representing object relationships,

360

specifying relationships via

reference, 376

Referencing relations, 73

Referential integrity constraints

inclusion dependencies and, 571

integrity constraints in databases,

relational data model and, 73–74

specifying in SQL, 95–96

Reflexive associations, in UML class

diagrams, 227

Regression function, 1058

Regression, in data mining,

1057–1058

Regression rule, 1057

Regular entity types, 219, 287–288

Relation extension, 62

Relation intension, 62

Relation nodes

notation for, 703

in query graphs, 179

Relation schemas

domains and, 61

goodness of, 501–502

in relational databases, 501

Relation (table) level, assigning priv-

ileges at, 842–843

Relational algebra

aggregate functions and grouping,

166–168

bibliographic references, 194–195

CARTESIAN PRODUCT opera-

tion, 155–157

complete set of relational algebra

operations, 161, 164

DIVISION operation, 162–163

EQUIJOIN and NATURAL JOIN

operations, 159–161

examples of queries in, 171–174

generalized projection, 165–166

JOIN operation, 157–158

notation for query trees, 163–165

OUTER JOIN operations,

169–170

OUTER UNION operation,

170–171

overview of, 145–146

PROJECT operation, 149–150

recursive closure operations,

168–169

RENAME operation, 151–152

SELECT operation, 147–149

sequences of operations, 151

summary and exercises, 185–194

transformation rules for opera-

tions, 706–708

translating SQL queries into,

681–682

UNION, INTERSECTION, and

MINUS operations, 152–155

Relational calculus

domain (relational) calculus,

183–185

overview of, 146–147

tuple relational calculus. See Tuple

relational calculus

Relational completeness, of rela-

tional query languages, 174

Relational data model

bibliographic references, 85

characteristics of relations, 63–66

classifying DBMSs and, 49

concepts, 60–61

constraints, 67–70

correspondence to ER model, 293

Delete operation, 77–78

domains, attributes, tuples, and

relations, 61–63

formal languages for. See

Relational algebra; Relational

calculus

Insert operation, 76–77

integrity, referential integrity, and

foreign keys, 73–74

in list of data model types, 31

mapping from EER model to. See

EER-to-Relational mapping

mapping from ER model to. See

ER-to-Relational mapping

notation, 66–67

other types of constraints, 74–75

overview of, 50, 59–60

practical language for. See SQL

(Structured Query Language)

schemas, 70–73

SQL compared with, 97

summary and exercises, 79–85

transactions and, 79

update operations, 75–76, 78–79

Relational database design

algorithms for, 557, 566–567

attribute semantics in, 503–507

bibliographic references, 302, 579

bottom-up approach to, 544

Boyce-Codd normal form

(BCNF), 529–531

dependency preservation proper-

ties of decompositions,

552–553

dependency-preserving and non-

additive join decomposition

into 3NF schemas, 560–563

dependency-preserving decompo-

sition into 3NF schemas,

558–559

disallowing possibility for spuri-

ous tuples, 510–513

domain-key normal form

(DKNF), 574–575

equivalence of sets of functional

dependencies, 549

first normal form (1NF), 519–523

formal analysis of relational

schemas, 513

formal definition of fourth nor-

mal form, 533–534, 568–570

functional dependencies based on

arithmetic functions and pro-

cedures, 572–574

functional dependency and,

513–516

general definition of second nor-

mal form, 526–527

general definition of third normal

form, 528

goodness of relational schemas,

501–502

Index 1161