Week 4

• Data structure


  The most fundamental and building block concept in database design
• Data structure


  • A good knowledge of data structures is a must to design and develop efficient software systems
  • The way we store, organize, and group data is important for an efficient database system
  • The way we structure data in relation to other elements (to map these relationships in a structured way to represent the data)
• Examples of well structured data


  • Dictionary
  • Google Maps
  • Relational Data
  • Commercial database systems
• Hierarchical data structure


  Traditional method, still popular today but with limitations
• Hierarchical data structure


  • Each node may have zero-or-more children
  • Each child has one-and-only-one parent
  • Root node (top node) has no parent
• Hierarchical data structure cannot support many-to-many relationships
• File system shortcuts can overcome hierarchical limitations but make the system disorganised
• Advantages of hierarchical data structure


  • Clean and logical
  • Fast to navigate and search
  • Little duplication even of meta (descriptive) data
  • Everything is in its place and there is a place for everything
• Disadvantages of hierarchical data structure


  • Rarely models the real world
  • Often needs lots of workarounds (that are complicated)
• Set theory


  A more flexible solution to structure data
• Set theory data structure


  • Items of data (nodes) can belong to zero-or-more sets
  • Sets can contain zero-or-more data items
• Set operations


  1. Union

  2. Intersection

  3. Set Difference
• Hierarchical data structure


  Cannot support many-to-many relationships
• Set theory data structure


  Supports many-to-many relationships
• Union of two sets contains all items that are a member of either or both sets
• Intersection of two sets contains only the items that are members of both sets
• Set difference contains the items that are in one set but not the other