Database Theory

Mathematical Logic · Axiom Academy

Discover how model theory provides the mathematical foundation for modern databases and why finite structures behave differently than infinite ones Databases as Mathematical Structures Every database you interact with—from your bank's customer records to Netflix's movie catalog—is actually a mathematical structure in the sense of model theory! Just as model theory studies interpretations of logical formulas, database theory studies how to store, query, and reason about structured data. Satisfaction: Does structure satisfy formula? Query Result: Does data match query? A relational database is a first-order structure where: The domain consists of all values that can appear in the database Each table is a relation (a subset of tuples from the domain) A query is a first-order formula (or fragment thereof) Query evaluation is model checking : does the database satisfy the query? Let's construct a simple database as a mathematical structure. Consider a university database with students and courses. Domain D: Alice, Bob, Carol, Math101, CS201, Phys150 Student(x): unary relation - "x is a student" Course(x): unary relation - "x is a course" Enrolled(x,y): binary relation - "student x is enrolled in course y" Model-Theoretic Interpretation This database is the structure M = (D, Student^M, Course^M, Enrolled^M) where: Course^M = Math101, CS201, Phys150 Enrolled^M = (Alice, Math101), (Alice, CS201), (Bob, Math101), (Carol, Phys150) Queries as First-Order Formulas

This is the written version of the interactive lesson above. See the full Mathematical Logic course.