NoSQL Overview | Computer Science

NoSQL databases address limitations of relational databases for certain workloads:

• Horizontal scalability across commodity hardware.
• Flexible schemas (semi-structured data).
• High write throughput for simple access patterns.
• Handling unstructured or polymorphic data.

Store data as JSON/BSON documents. Each document can have a different structure.

Example (MongoDB):

{
  "_id": 1,
  "name": "Alice",
  "courses": ["CS101", "MATH201"],
  "address": { "city": "Cambridge", "zip": "02139" }
}

Strengths: Flexible schema, nested data, good for content management. Weaknesses: No joins (requires embedding or application-level joins), eventual consistency in Distributed mode, limited transaction support.

Simplest model: each item is a key-value pair. Values are opaque blobs.

Example (Redis):

SET user:1001 "{"name":"Alice","email":"alice@univ.edu"}'
GET user:1001
EXPIRE user:1001 3600

Strengths: Extremely fast (in-memory), simple API, caching, session management. Weaknesses: No queries beyond key lookup, limited data modelling.

Store nodes and edges with properties. Optimised for traversing relationships.

Example (Neo4j Cypher):

CREATE (a:Student {name: "Alice"})-[:ENROLLED_IN {grade: "A"}]->(c:Course {title: "Databases"})
MATCH (s:Student)-[:ENROLLED_IN]->(c:Course {title: "Databases"})
RETURN s.name, c.title

Strengths: Efficient for complex relationship queries, social networks, recommendation engines, Knowledge graphs. Weaknesses: Not suitable for simple CRUD, horizontal scaling is harder.

Store data in column families (groups of related columns). Each row can have different columns.

Example (Apache Cassandra):

CREATE TABLE grades (
    student_id text,
    course_id text,
    grade text,
    semester text,
    PRIMARY KEY ((student_id), course_id)
);

Strengths: High write throughput, efficient column-level reads, horizontal scalability, Time-series data. Weaknesses: No joins, limited query flexibility, eventual consistency.

Theorem 8.1 (Brewer’s CAP Theorem). A distributed data store can provide at most two of the Following three guarantees simultaneously:

• Consistency (C): Every read receives the most recent write.
• Availability (A): Every request receives a non-error response.
• Partition tolerance (P): The system continues to operate despite network partitions.

Since network partitions are inevitable in distributed systems, the real trade-off is between consistency and availability during a partition.

PACELC. Extension of CAP: in the absence of partitions, the trade-off is between latency And consistency.

flowchart TD
    A[8_Nosql Overview] --> B[Key Concepts]
    A --> C[Core Principles]
    A --> D[Practical Applications]
    B --> E[Fundamental definitions]
    C --> F[Design patterns]
    D --> G[Real-world usage]

NoSQL databases are like different types of filing cabinets. Document stores are folders with loose papers — each document can have a different structure. Key-value stores are like coat check tickets — you give a key and get back whatever you stored. Column-family stores are like spreadsheets where each row can have different columns. Graph databases are like mind maps, where relationships are first-class citizens. The CAP theorem is the law of physics for distributed systems — you can only pick two out of three: Consistency (everyone sees the same data), Availability (everyone can always read and write), and Partition tolerance (the system survives network failures). Since network partitions are unavoidable, you must choose between consistency and availability during a partition.

• Discrete Mathematics
• Algorithm Implementation

1. Confusing “NoSQL” with “no SQL.” NoSQL means “Not Only SQL,” not a rejection of SQL. Many NoSQL databases support SQL-like query languages (e.g., Cassandra CQL, MongoDB’s aggregation pipeline). The distinction is about data model flexibility, not about abandoning structured query syntax.

2. Assuming CAP means you pick exactly two. In practice, you cannot actually choose all three, but the trade-off is specifically during a partition. In normal operation (no partition), a system can provide both consistency and availability. The theorem constrains behaviour only when nodes cannot communicate.

3. Treating all NoSQL databases as interchangeable. Document stores, key-value stores, column-family stores, and graph databases have fundamentally different data models and query capabilities. Choosing a key-value store for a workload that requires complex relational queries will lead to poor performance and application complexity.

4. Ignoring schema design in document stores. Embedding vs. referencing is a critical design decision. Embedding all related data in a single document leads to unbounded document growth and update anomalies. Referencing requires additional queries but keeps documents bounded and updates localised.

5. Overlooking tunable consistency. Many NoSQL systems (e.g., Cassandra, DynamoDB) offer tunable consistency levels per operation. Using strong consistency everywhere negates the availability benefits, while using eventual consistency everywhere risks stale reads. Choose the consistency level appropriate for each operation.

This section provides detailed coverage of advanced concepts, including full derivations, proofs, and extended examples.

Complete mathematical derivations and proofs are provided where appropriate. Each step is explained to ensure understanding of the underlying reasoning.

Advanced examples demonstrate the application of concepts to complex problems. These examples go beyond standard exam questions to develop deeper understanding.

This material connects to current research and advanced applications in the field. Understanding these connections provides context for the study material.

Ensure you have mastered the prerequisite material before attempting this advanced content.