Study Vault Search notes, aliases and full text
Study Vault
Graph
On this page
Next up ↓
CourseDBISEN

Databases and Information Systems

Lecturer Prof. H. BastSemester WiSe 2025/26Language English Exam Sources lecture-01 lecture-02 lecture-03 +10 moreOpen in graph ↗

Lectures

written lecture notes
VLDateLectureChapters
01Introduction, Inverted Index, Zipf's Law–
02Ranking and Evaluation–
03Database Basics–
04Query Planning Basics–
05Joins and more SQL–
06Indexing, Query Optimization, ACID–
07Knowledge Graphs, SPARQL, SPARQL to SQL–
08Fuzzy Search, Prefix Edit Distance, Q-Gram Index–
09Web Applications, Part 1–
10Web Applications, Part 2–
11Vector Space Model, Word Embeddings–
12N-gram Models, LLMs, RAG–
13Evaluation, Exam, Work in our Group–

Course info

from the course index note

Lectures Table#

Generated viewLecturesshown above

Exercises#

Knowledge#

Generated viewTopics and conceptsshown below

Exams#

URLS#

Topics & concepts of this course

13 topics · 78 concepts
Encodings and Compression

Prefix-free codes, entropy, Shannon's source coding theorem, and integer encoding schemes (unary, Golomb, Elias-Gamma, Elias-Delta, gap encoding) and UTF-8.

Evaluation

How to measure the quality of a ranking against a ground truth: P@k, AP and MAP for binary relevance, nDCG for graded relevance, bpref for incomplete judgments, and avoiding overfitting by a train/test split.

Fuzzy Search and Q-Grams

Error-tolerant (prefix) search over a dictionary with edit distance and prefix edit distance, made fast by filtering candidates with the q-gram lemma and a q-gram index.

Inverted Index and Ranking

Keyword search with an inverted index whose postings carry scores (tf, tf.idf, BM25) that are summed while merging the lists, plus Zipf's law for word frequencies.

Latent Semantic Indexing

Latent semantic indexing ranks documents with a rank-k approximation of the term-document matrix computed by singular value decomposition, so that a query also matches documents that share no term with it.

Linear Classifiers and Logistic Regression

Linear decision boundaries (hyperplanes, distance, separability), the perceptron, and logistic regression with the sigmoid, softmax and the cross-entropy loss trained by gradient steps.

List Intersection and Search

How sorted lists (inverted lists, sorted join columns) are intersected and merged: the linear-time zipper, binary search and galloping (exponential) search intersection, and when to use which.

Naive Bayes Classification

Classifying documents with Bayes' theorem and the assumption that words are independent given the class: training by counting, smoothing, prediction by an argmax over class scores.

POS-Tagging

Assigning a part-of-speech tag to every word of a sentence by modelling tags as a Hidden Markov Model and decoding the most likely tag sequence with the Viterbi algorithm.

SPARQL and Knowledge Graphs

RDF triples as the data model of knowledge graphs, SPARQL as their query language, Wikidata's statement-node scheme for n-ary facts, and the mechanical translation of basic SPARQL to SQL.

SQL and Query Planning

How relational data is stored and queried with SQL, how a query is translated into table operations, and how the cheapest query plan is chosen (joins, indexes, join ordering), plus transactions.

Web Applications

How a search web application works end to end: a socket server speaking HTTP, HTML/CSS pages with forms, JavaScript that updates the DOM with fetched JSON, URL and character encoding, and protection against code injection and cross-origin abuse.

Word Embeddings and Language Models

How documents and words become vectors (vector space model, one-hot encodings, word embeddings) that are compared by dot product or cosine similarity, and how language models from n-gram counts to LLMs predict the next token, combined in retrieval-augmented generation.

Foundations used by this course

marked as used in DBIS, or covered by its lectures
Linear Algebra1 topic · 2 concepts

Cosine Similarity · Singular Value Decomposition

Concept index

this course and the foundations it uses · 80
ACID ACID Properties → ACID Add-Epsilon Smoothing → Laplace Smoothing Add-One Smoothing → Laplace Smoothing Additive Smoothing → Laplace Smoothing AJAX → AJAX and Fetch API AJAX and Fetch API AP → Average Precision Average PrecisionB+ Tree B+-Tree → B+ Tree Benchmark → Ground Truth Best Match 25 → BM25 Bigram Model → N-Gram Model Binary Preference → BPref BM25 BPref bpref → BPref Bytes vs. Strings → Character EncodingCartesian Product Character Encoding Charset → Character Encoding Code Injection → Code Injection Protection Code Injection Protection CORS → Same-Origin Policy cos-similarity → Cosine Similarity Cosine Similarity Cross Product → Cartesian Product Cross-Origin Resource Sharing → Same-Origin Policy Cross-Product → Cartesian Product Cross-Site Scripting → Code Injection Protection CSS → HTML StructureDCG → Discounted Cumulative Gain DCG and nDCG → Discounted Cumulative Gain Decision Boundary → Linear Classifier Discounted Cumulative Gain Document Expansion → LSI Ranking Document Object Model → DOM Manipulation DOM → DOM Manipulation DOM ManipulationED → Edit Distance Edit Distance Elias-Delta Code Elias-Gamma Code Embedding Embeddings → Embedding Entropy Entropy-Optimal Code Exponential Searchfetch → AJAX and Fetch API Fetch API → AJAX and Fetch API Fuzzy Prefix Search → Fuzzy Search Fuzzy SearchGalloping Search → Exponential Search Gap Encoding Golomb Code Ground Truth group-by(T, cols, agg)Hidden Markov Model HMM → Hidden Markov Model HTML → HTML Structure HTML Form HTML Forms → HTML Form HTML Structure HTTP → HTTP Protocol HTTP Protocol HTTP Serveridf → TF-IDF Index B+ Tree → B+ Tree Inverse Document Frequency → TF-IDF Inverted IndexJoin $T_1 \bowtie T_2$Lagrange Multiplier → Lagrange Multipliers Lagrange Multipliers Lagrangian → Lagrange Multipliers Lagrangian Optimization → Lagrange Multipliers Language Model Laplace Smoothing Large Language Model Large Language Models → Large Language Model Latent Semantic Indexing Method → LSI Ranking Levenshtein Distance → Edit Distance Linear Classifier Linear Separability → Linear Classifier List Intersection LLM → Large Language Model Logistic Regression Low-Rank Approximation → Singular Value Decomposition Low-Rank Approximation of the Term-Document Matrix → LSI Ranking LSI → LSI Ranking LSI RankingMAP → Mean Average Precision Maximum Likelihood → Maximum Likelihood Estimation Maximum Likelihood Estimation Mean Average Precision Media Type → HTTP Protocol Mediator Entity → Reification Merge Join MIME Type → HTTP Protocol MLE → Maximum Likelihood Estimation MP@k → Mean Average Precision MP@R → Mean Average Precision Multinomial Naive Bayes → Naive Bayes ClassifierN-Gram Model N-gram Model → N-Gram Model Naive Bayes → Naive Bayes Classifier Naive Bayes Classifier nDCG → Discounted Cumulative Gain Network Socket Neural Language Model → Language Model Normalized Discounted Cumulative Gain → Discounted Cumulative GainOkapi BM25 → BM25 One-Hot Encoding ORDER BY → Ordering Ordering Overfitting (IR Evaluation)P@k → Precision at k P@R → Precision at k PED → Prefix Edit Distance Percent-Encoding → URL Encoding Perceptron Perceptron Algorithm → Perceptron Precision at k Precision at R → Precision at k Prefix Code → Prefix-Free Code Prefix Edit Distance Prefix-Free CodeQ-Gram Q-Gram Index Q-Gram Lemma Q-Grams → Q-Gram Query Optimization Query PlanRAG → Retrieval-Augmented Generation Rank-k Approximation → Singular Value Decomposition RDF Triple RDF Triples → RDF Triple Reduced SVD → Singular Value Decomposition Reification Relational Algebra Relational Model Relevance Judgments → Ground Truth Retrieval-Augmented GenerationSame-Origin Policy Search Server → HTTP Server Shannon Entropy → Entropy Sigmoid Singular Value Decomposition Singular Values → Singular Value Decomposition Singulärwertzerlegung → Singular Value Decomposition Socket → Network Socket Socket Communication → Network Socket Softmax SOP → Same-Origin Policy Sort-Merge Join → Merge Join SPARQL Query Structure SPARQL to SQL Translation Sparse Matrices → Sparse Matrix Sparse Matrix SQL Query Structure Statement Node → Reification Subqueries → Subquery Subquery SVD → Singular Value DecompositionTerm Frequencies → Term Frequency Term Frequency tf → Term Frequency TF-IDF tf.idf → TF-IDF tfidf → TF-IDF Trigram Model → N-Gram Model Truncated SVD → Singular Value DecompositionUnary Code Unigram Model → N-Gram Model URL Decoding → URL Encoding URL Encoding UTF-8Vector Space Model Viterbi → Viterbi Algorithm Viterbi Algorithm VSM → Vector Space ModelWeb Server → HTTP Server Wikidata Prefix SystemXSS → Code Injection ProtectionZipf → Zipf's Law Zipf's Law

Search

Type In
↑ ↓ move ↵ open ⇥ next section Ctrl↵ results page Prefix # to search text only