Database DesignPowerPoint PresentationSlide 3View and Logical LevelsConstraint DatabasesTwo Most Common Types of ConstraintsConstraints (1)Constraints (2)Constraints (3)Constraints (4)Boolean Atomic Constraints (1)Boolean Atomic Constraints (2)Boolean Atomic Constraints (3)Constraint Formulas (1)Constraint Formulas (2)Interpretation of free Boolean algebraConstants in constraints are also interpretedThe Constraint Data Model (1)The Constraint Data Model (2)The Constraint Data Model (3)The Constraint Data Model (4)The Constraint Data Model (5)The Constraint Data Model (6)The Constraint Data Model (7)The Constraint Data Model (8)The Constraint Data Model (9)Data Abstraction (1)Data Abstraction: View LevelData Abstraction: Logical LevelData Abstraction: Constraint LevelData Abstraction: Physical LevelDiscussion QuestionsSlide 33SolutionSlide 35Slide 36Questions for the Next Lecture2003SJSU -- CmpE L6-S1 Constraint DBDatabase Design Dr. M.E. Fayad, ProfessorComputer Engineering Department, Room #283I College of EngineeringSan José State UniversityOne Washington SquareSan José, CA 95192-0180 http://www.engr.sjsu.edu/~fayad2003SJSU – CmpE --- M.E. Fayad L6-S2 Constraint DB2Lesson 06:Constraint Databases2003SJSU – CmpE --- M.E. Fayad L6-S3 Constraint DB Lesson ObjectivesObjectives3 Understand Constraint Databases Learn How to Deal with Constraints Arithmetic Atomic Constraints Boolean Atomic Constraints Constraint Formulas Interpretations of Free Boolean Constraints Understand the Constraint Data Model Explore Data Abstraction2003SJSU – CmpE --- M.E. Fayad L6-S4 Constraint DBAre The highest level of data abstractionAre not suitable for computer to represent data. Why?Because the allow an infinite number of tuples or points.In this lecture we discuss constraint data model that is used to represent the logical level of data in a concise way.4View and Logical Levels2003SJSU – CmpE --- M.E. Fayad L6-S5 Constraint DBNext level of data abstraction: Constraint level – finitely represents by constraints the logical level5Constraint Databases2003SJSU – CmpE --- M.E. Fayad L6-S6 Constraint DBConstraints apply to two or more variables.Each variable takes its value from a domainCommon domains are:+ The set of nonnegative numbers (or natural numbers) N+ The set of integer numbers Z+ The set of rational number Q+ The set of real numbers ROther domains – Set of English words in the dictionary W6Two Most Common Types of Constraints2003SJSU – CmpE --- M.E. Fayad L6-S7 Constraint DBAssume u and v are variables or constantsB and ci are constantsLet ± denote + or - Let p be a polynomial function over variables X1, …., XnAny valid expression with constants, variables, addition, and multiplication symbolsWe define the most basic type of constraints, called the atomic constraints over any of the domains N, Z, Q, R as following:7Constraints (1)2003SJSU – CmpE --- M.E. Fayad L6-S8 Constraint DBArithmetic Atomic Constraints Equality: u = v Inequality: u ≠ v Lower bound: u ≥ b Upper bound: – u ≥ b Order: u ≥ v Gap-order: u – v ≥ b where b ≥ 0 Difference: u – v ≥ b8Constraints (2)2003SJSU – CmpE --- M.E. Fayad L6-S9 Constraint DBHalf-Addition: ± u ± v ≥ b where b ≥ 0Addition: ± u ± v ≥ bLinear: c1x1 + ……+ cnxn ≥ bPolynomial: p( x1,……..,xn ) ≥ b Note: Instead of ≥ we can also use >b is a bound which is restricted to be nonnegative in the case of gap-order and half addition constraints.ci is a coefficient in the linear constraint.9Constraints (3)2003SJSU – CmpE --- M.E. Fayad L6-S10 Constraint DBIf a constraint C is any of these types of constraints and the domain of the variables is Z and Q we talk of integer C constraints or rational C constraints, respectively.We consider each = constraint as the conjunction of two ≥ constraints.For example: linear equation 5x+7y = 8 can be expressed as the conjunction of the linear inequality constraints:5x +7y ≥ 8 and 5x +7y ≤ 8 This is why we do not consider linear equality as atomic constraints. Nevertheless, we will write constraints with = signs.10Constraints (4)2003SJSU – CmpE --- M.E. Fayad L6-S11 Constraint DBBoolean Algebra < D, Λ, V, ‘, 0, 1 > D – domain, 0 – zero element,1 – one element. such that the following axioms hold:11Boolean Atomic Constraints (1)2003SJSU – CmpE --- M.E. Fayad L6-S12 Constraint DBCommutative: x V y = y V x x Λ y = y Λ xDistributive: x V ( y Λ z ) = ( x V y ) Λ ( x V z ) x Λ ( y V z ) = ( x Λ y ) V ( x Λ z )Inverse: x V x’ = 1 x Λ x’ = 0Zero and one element properties: x V 0 = x x Λ 1 = x 0 ≠ 112Boolean Atomic Constraints (2)2003SJSU – CmpE --- M.E. Fayad L6-S13 Constraint DBBoolean equality constraints: T =B 0Boolean inequality constraints: T ≠B 0 where T is a Boolean term built from domain elements and operations of the boolean algebra.Example:( x’ Λ z ) V ( y Λ z ) V ( x Λ y’ Λ z’ ) =B 013Boolean Atomic Constraints (3)2003SJSU – CmpE --- M.E. Fayad L6-S14 Constraint DBeach atomic constraint if F and G are formulas, then (F and G) is a formula and (F or G) is a formula.if F is a formula, then (not F) is a formula.14Constraint Formulas (1)2003SJSU – CmpE --- M.E. Fayad L6-S15 Constraint DBLet F(x1,…,xn) be a formula with n rows, t = (c1,…,cn) a tuple with n constants.t satisfies F (t F) – substituting each xi by ci makes F true.15Constraint Formulas (2)2003SJSU – CmpE --- M.E. Fayad L6-S16 Constraint DBSymbols are interpreted to be concrete operators or values. Example: D – all subsets of 1 Λ – intersection V – union ‘ – complement 0 – emptyset 1 – set of names of all animals {cat, dog, parrot,…} Question: What would be the meaning of the example Boolean constraint under this interpretation ?16Interpretation of free Boolean algebra2003SJSU – CmpE --- M.E. Fayad L6-S17 Constraint DBExample: Suppose we have the constraint b Λ m = 0 and we interpret b as {canary, parrot, falcon} m as {cat, dog}Question:
View Full Document
Unlocking...