SQL and Relational Theory

Chapter 1 Setting the Scene 1

The relational model is much misunderstood 1

Some remarks on terminology 2

Principles not products 4

A review of the original model 5

Model vs. implementation 12

Properties of relations 14

Base vs. derived relations 18

Relations vs. relvars 19

Values vs. variables 21

Concluding remarks 22

Exercises 23

Chapter 2 Types and Domains 25

Types and relations 25

Equality comparisons 26

Data value atomicity 31

What’s a type? 34

Scalar vs. nonscalar types 37

Scalar types in SQL 39

Type checking and coercion in SQL 40

Collations in SQL 42

Row and table types in SQL 43

Concluding remarks 45

Exercises 46

Chapter 3 Tuples and Relations, Rows and Tables 49

What’s a tuple? 49

Rows in SQL 53

What’s a relation? 55

Relations and their bodies 57

Relations are n-dimensional 58

Relational comparisons 58

TABLE_DUM and TABLE_DEE 59

Tables in SQL 60

vi Contents

Column naming in SQL 62

Concluding remarks 64

Exercises 64

Chapter 4 No Duplicates, No Nulls 67

What’s wrong with duplicates? 67

Duplicates: further issues 72

Avoiding duplicates in SQL 72

What’s wrong with nulls? 74

Avoiding nulls in SQL 77

A remark on outer join 79

Concluding remarks 80

Exercises 80

Chapter 5 Base Relvars, Base Tables 85

Updating is set level 86

Relational assignment 88

More on candidate keys 92

More on foreign keys 94

Relvars and predicates 97

Relations vs. types 99

Exercises 101

Chapter 6 SQL and Relational Algebra I: The Original Operators 105

Some preliminaries 105

More on closure 108

Restriction 110

Projection 111

Join 112

Union, intersection, and difference 116

Which operators are primitive? 119

Formulating expressions one step at a time 119

What do relational expressions mean? 121

Evaluating SQL table expressions 122

Expression transformation 123

The reliance on attribute names 125

Exercises 127

Chapter 7 SQL and Relational Algebra II: Additional Operators 131

Exclusive union 131

Semijoin and semidifference 132

Extend 133

Image relations 135

Divide 138

Aggregate operators 139

Image relations bis 144

Summarization 146

Summarization bis 150

Group, ungroup, and relation valued attributes 152

“What if” queries 157

A note on recursion 159

What about ORDER BY? 163

Exercises 164

Chapter 8 SQL and Constraints 169

Type constraints 169

Type constraints in SQL 173

Database constraints 174

Database constraints in SQL 178

Transactions 180

Why database constraint checking must be immediate 180

But doesn’t some checking have to be deferred? 182

Constraints and predicates 185

Miscellaneous issues 186

Exercises 188

Chapter 9 SQL and Views 193

Views are relvars 194

Views and predicates 197

Retrieval operations 198

Views and constraints 199

Update operations 203

What are views for? 211

Views and snapshots 212

Exercises 213

Chapter 10 SQL and Logic 215

Why do we need logic? 216

Simple and compound propositions 217

Simple and compound predicates 222

Quantification 223

Relational calculus 227

More on quantification 234

Some equivalences 241

Concluding remarks 244

Exercises 244

Chapter 11 Using Logic to Formulate SQL Expressions 247

Some transformation laws 247

Example 1: Logical implication 250

Example 2: Universal quantification 251

Example 3: Implication and universal quantification 252

Example 4: Correlated subqueries 254

Example 5: Naming subexpressions 255

Example 6: More on naming subexpressions 258

Example 7: Dealing with ambiguity 259

Example 8: Using COUNT 261

Example 9: Join queries 262

Example 10: UNIQUE quantification 263

Example 11: ALL or ANY comparisons 265

Example 12: GROUP BY and HAVING 269

Exercises 270

Chapter 12 Miscellaneous SQL Topics 273

SELECT * 273

Explicit tables 274

Name qualification 274

Range variables 275

Subqueries 277

“Possibly nondeterministic” expressions 280

Empty sets 281

A simplified BNF grammar 281

Exercises 285

Appendix A The Relational Model 287

The relational model vs. others 288

The significance of theory 291

The relational model defined 293

Database variables 298

Objectives of the relational model 299

Some database principles 300

What remains to be done? 301

Appendix B SQL Departures from the Relational Model 305

Appendix C A Relational Approach to Missing Information 307

Vertical decomposition 308

Horizontal decomposition 309

What do the shaded entries mean? 311

Constraints 313

Queries 314

More on predicates 317

Exercises 320

Appendix D A Tutorial D Grammar 321

Appendix E Summary of Recommendations 325

Appendix F Answers to Exercises 329

Chapter 1 329

Chapter 2 335

Chapter 3 341

Chapter 4 346

Chapter 5 352

Chapter 6 358

Chapter 7 366

Chapter 8 379

Chapter 9 389

Chapter 10 395

Chapter 11 403

Chapter 12 405

Appendix C 407

Appendix G Suggestions for Further Reading 409

Index 419

Chapter 1 Setting the Scene 1The relational model is much misunderstood 1Some remarks on terminology 2Principles not products 4A review of the original model 5Model vs. implementation 12Properties of relations 14Base vs. derived relations 18Relations vs. relvars 19Values vs. variables 21Concluding remarks 22Exercises 23Chapter 2 Types and Domains 25Types and relations 25Equality comparisons 26Data value atomicity 31What’s a type? 34Scalar vs. nonscalar types 37Scalar types in SQL 39Type checking and coercion in SQL 40Collations in SQL 42Row and table types in SQL 43Concluding remarks 45Exercises 46Chapter 3 Tuples and Relations, Rows and Tables 49What’s a tuple? 49Rows in SQL 53What’s a relation? 55Relations and their bodies 57Relations are n-dimensional 58Relational comparisons 58TABLE_DUM and TABLE_DEE 59Tables in SQL 6