Hongxu Xu

PhD Student (May 2025 – Present)
Supervised by Prof. Chengnian Sun
Cheriton School of Computer Science
University of Waterloo, Canada

B.Sc. in Computer Science (Sep 2014 – Jun 2018)
Beijing Normal University, China

Research Interests

• Software Engineering
• Programming Languages

without a focus yet…

Socials

• GitHub: https://github.com/xuhongxu96
• LinkedIn: https://www.linkedin.com/in/xuhongxu/
• Email: h4️⃣4️⃣5️⃣xu 🌀 uwaterloo.ca

If you’d like to hear more about my thoughts and life, consider following me on:

• Substack: https://hongxuxu.substack.com/ (English only)
  Subscribe to my newsletter on Substack to get my latest updates.

• 微信公众号: xuhongxu_it (Chinese only)
  Scan the QR code on the right to follow my WeChat Official Account.
  扫描右侧二维码 关注我的微信公众号。

Misc.

• Chinese Name: 许宏旭
  • Literally means “宏: Great 旭: Rising Sun”
  • Pronunciation: Hong-shyoo (IPA: [xʊŋ ɕy])

Publications

Papers

Nothing yet…

Books

• Feb 2024 CMake构建实战：项目开发卷 (CMake Build Practice: Project Development Volume)
  Published by 人民邮电出版社 (Posts & Telecom Press, China)
  Produced by 异步图书 (epubit)

Experience

PhD Student (May 2025 – Present)

Supervised by Prof. Chengnian Sun

Cheriton School of Computer Science
University of Waterloo, Canada

Senior SDE (Sep 2022 – Mar 2025)

Seed/Data Speech Team
ByteDance, Shanghai, China

Led the development of the Text-to-Speech engine and contributed to the Doubao AI assistant application.

SDE-2 (Aug 2021 – Sep 2022)

MSAI Team
Microsoft STC-Asia, Suzhou, China

Led the development of Microsoft WordBreaker and initiated a modern NLP toolkit for Office 365.

SDE (Jul 2018 – Aug 2021)

MSAI Team
Microsoft STC-Asia
Beijing, China (Relocated to Suzhou, Jiangsu, China in May 2019)

Worked on 20-year-old Microsoft WordBreaker.

Short-Term Contributor (Nov 2020 – Jan 2021)

Windows APS Team (temporary assignment)
Microsoft STC-Asia, Suzhou, China

Contributed to the formation of the new team, and Windows 11 application development.

B.Sc. in Computer Science (Sep 2014 – Jun 2018)

Beijing Normal University, China

SDE Intern (Jul 2017 – Dec 2017)

Bing Search Relevance Team
Microsoft STC-Asia, Beijing, China

Answer triggering model development for Bing Search.

Awards

• Outstanding Graduate, Beijing Normal University, 2018
• Top Ten Volunteer, Beijing Normal University, 2015
• First Prize, National Olympiad in Informatics in Provinces (NOIP), 2013

Teaching

Note

IA : Instructional Apprentice
TA : Teaching Assistant

What’s the difference between TAs and IAs?

• IA, CS 136L - Tools and Techniques for Software Development, Winter 2026
• IA, CS 246 - Object-Oriented Software Development, Fall 2025
• TA, CS 246 - Object-Oriented Software Development, Spring 2025

My Thoughts and Life

Note

I share technical content on this website, including course notes, projects, and research.

For more personal thoughts and life updates, please check out my Substack newsletter and WeChat Official Account below.

Tip

Follow me on Substack and WeChat!

• Substack: https://hongxuxu.substack.com/ (English only)
  Subscribe to my newsletter on Substack to get my latest updates.

• 微信公众号: xuhongxu_it (Chinese only)
  Scan the QR code on the right to follow my WeChat Official Account.
  扫描右侧二维码 关注我的微信公众号。

Selected Substack Posts

My 2025

G1 Pain Points

CS 452/652: Real-Time Programming (the Train Course)

Spring 25

I dropped this course after I learned that it is really time-consuming.

However, before I dropped it, I did some research and found some useful resources, which I summarized in MarklinSim All-in-One repo.

In short, follow the readme in the repo to set up:

1. MarklinSim (an emulator for the train kit)
2. QEMU (an emulator for the Raspberry Pi 4B)
3. Example Image (your real-time system).

I believe it will save you a lot of time. Good luck!

CS 480/680: Introduction to Machine Learning

Spring 25

This is not a hard course.

• Download PDF
• Download LaTeX Sources

CS 848: Advanced Topics in Database: Algorithmic Aspects of Database Query Processing

Fall 25

https://cs.uwaterloo.ca/~xiaohu/courses/CS848/CS848-F25.html

My Notes

My course on database theory, specifically regarding Query Processing algorithms, is coming to an end soon. It has been very rewarding, so I’m writing this down to record what I’ve learned.

I originally chose this course as a challenge because I couldn’t understand a single paper mentioned in the syllabus—I didn’t even know what problems they were trying to solve. After a semester of struggling to grasp just the surface, I discovered that this is actually quite an interesting—albeit still very difficult—field.

I am writing this note to document the relatively simple and fundamental parts. I also want to organize the logical thread—what is the problem, how is it solved, what new problems arise from that solution, and how are those solved? I hope this will help me pick it up quickly if I need it in the future, and also serve as a simple introduction for readers.

Note

These notes were originally written in Chinese, and translated by Gemini.
Therefore, some expressions may seem a bit unnatural in English. I will gradually refine them over time.

From Pairwise Join to Global Perspective

Motivating Example: Different Orders of Pairwise JOINs

Table 1: Student_Teacher

Table 2: Teacher_Lab

Table 3: Lab_Device

Assume we have the 3 tables above in a database. We allow the same student to have multiple teachers, and the same teacher to guide multiple students, etc. Now, we want to see which devices each student can access via the laboratories their teachers belong to.

Any reader who has used SQL should know how to query this (the SQL below is simplified for demonstration and is not standard syntax):

SELECT * FROM Student_Teacher
    INNER JOIN Teacher_Lab ON Teacher
    INNER JOIN Lab_Device ON Lab

So, how do we obtain the execution results of this SQL statement in the database?

Since this involves three data tables, it is easy to see that we can perform Pairwise Joins. There are several options for the order:

Order 1 (Join Table 1 and Table 2 first)

Intermediate_Result = SELECT * FROM Student_Teacher INNER JOIN Teacher_Lab ON Teacher
Final_Result = SELECT * FROM Intermediate_Result INNER JOIN Lab_Device ON Lab

Order 2 (Join Table 2 and Table 3 first)

Intermediate_Result = SELECT * FROM Teacher_Lab INNER JOIN Lab_Device ON Lab
Final_Result = SELECT * FROM Student_Teacher INNER JOIN Intermediate_Result ON Teacher

Order 3 (Join Table 1 and Table 3 first)

Intermediate_Result = SELECT * FROM Student_Teacher CROSS JOIN Lab_Device
Final_Result = SELECT * FROM Intermediate_Result INNER JOIN Teacher_Lab ON Teacher, Lab

graph BT
    subgraph "Order 3"
        direction BT
        T3_A[("Student_Teacher")]:::table
        T3_C[("Lab_Device")]:::table
        T3_B[("Teacher_Lab")]:::table

        J3_1{{"CROSS JOIN (Cartesian)"}}:::op
        Res3["_Final Result_<br>JOIN ON Teacher & Lab"]:::result

        %% Cross join first
        T3_A --> J3_1
        T3_C --> J3_1
        
        %% Then join with the middle table
        J3_1 --> Res3
        T3_B --> Res3
    end

    subgraph "Order 2"
        direction BT
        T2_A[("Student_Teacher")]:::table
        T2_B[("Teacher_Lab")]:::table
        T2_C[("Lab_Device")]:::table

        J2_1{{"JOIN ON Lab"}}:::op
        Res2["_Final Result_<br>JOIN ON Teacher"]:::result

        T2_B --> J2_1
        T2_C --> J2_1
        
        T2_A --> Res2
        J2_1 --> Res2
    end
    
    subgraph "Order 1"
        direction BT
        T1_A[("Student_Teacher")]:::table
        T1_B[("Teacher_Lab")]:::table
        T1_C[("Lab_Device")]:::table
        
        J1_1{{"JOIN ON Teacher"}}:::op
        Res1["_Final Result_<br>JOIN ON Lab"]:::result

        T1_A --> J1_1
        T1_B --> J1_1
        
        J1_1 --> Res1
        T1_C --> Res1
        
        %% Labeling the final join edge for clarity
        linkStyle 2 stroke-width:2px,fill:none,stroke:green;
        linkStyle 3 stroke-width:2px,fill:none,stroke:green;
    end

Which one is better? Order 3 involves a CROSS JOIN (Cartesian product), so it can basically be ruled out immediately.

For any execution order, the input data (database/tables) is the same, and the output final result must also be the same. The only place where differences can occur is in the intermediate results. Let’s simulate the execution process.

The intermediate result for Order 1 is as follows, with a total of 6 rows:

The intermediate result for Order 2 is as follows, with a total of 3 rows:

Regardless of the order, the final result is as follows, with a total of 2 rows:

It is evident that Order 2 is superior because it outputs fewer intermediate results. These intermediate results not only take up memory but also participate in subsequent JOIN calculations, so obviously, the fewer the better.

This is exactly what modern Database Management Systems (DBMS) usually do: use Pairwise JOINs while selecting a potentially optimal JOIN order based on statistics and rules.

A More Intuitive View

We can represent this database as the path graph below, where each edge represents a row of data in a table:

graph LR
    %% Define styling to match the handwritten dot style
    classDef dot stroke-width:2px;

    %% Layer definitions for alignment
    subgraph Students
        S0(( S0 ))
        S1(( S1 ))
        S2(( S2 ))
    end

    subgraph Teachers
        T0(( T0 ))
        T1(( T1 ))
        T2(( T2 ))
        T3(( T3 ))
    end

    subgraph Labs
        L0(( L0 ))
        L1(( L1 ))
        L2(( L2 ))
        L3(( L3 ))
    end

    subgraph Devices
        GPU0(( GPU0 ))
        GPU1(( GPU1 ))
    end

    S0 --- T0
    S0 --- T1
    S1 --- T2
    S2 --- T2
    
    T0 --- L0
    T0 --- L1
    T1 --- L0
    T1 --- L1
    T2 --- L2
    T3 --- L3
    
    L2 --- GPU0
    L3 --- GPU0
    L3 --- GPU1

    %% Apply styling
    class S0,S1,S2,T0,T1,T2,T3,L0,L1,L2,L3,GPU0,GPU1 dot;

Consider Order 1, which looks for paths that can traverse all fields completely from Left to Right:

graph LR
    %% Define styling to match the handwritten dot style
    classDef dot stroke-width:2px;
    classDef thick-line stroke-width:10px;

    %% Layer definitions for alignment
    subgraph Students
        S0(( S0 ))
        S1(( S1 ))
        S2(( S2 ))
    end

    subgraph Teachers
        T0(( T0 ))
        T1(( T1 ))
        T2(( T2 ))
        T3(( T3 ))
    end

    subgraph Labs
        L0(( L0 ))
        L1(( L1 ))
        L2(( L2 ))
        L3(( L3 ))
    end

    subgraph Devices
        GPU0(( GPU0 ))
        GPU1(( GPU1 ))
    end

    S0 === T0
    S0 === T1
    S1 === T2
    S2 === T2
    
    T0 === L0
    T0 === L1
    T1 === L0
    T1 === L1
    T2 === L2
    T3 --- L3
    
    L2 === GPU0
    L3 --- GPU0
    L3 --- GPU1

    %% Apply styling
    class S0,S1,S2,T0,T1,T2,T3,L0,L1,L2,L3,GPU0,GPU1 dot;

The intermediate result of Order 1 contains three fields: “Student”, “Teacher”, and “Lab”. There are a total of 6 paths that can go from “Student” to “Lab” (Left to Right), which is exactly the number of rows in the intermediate result.

Similarly, consider Order 2, looking for paths from Right to Left:

graph RL
    %% Define styling to match the handwritten dot style
    classDef dot stroke-width:2px;
    classDef thick-line stroke-width:10px;

    %% Layer definitions for alignment
    subgraph Students
        S0(( S0 ))
        S1(( S1 ))
        S2(( S2 ))
    end

    subgraph Teachers
        T0(( T0 ))
        T1(( T1 ))
        T2(( T2 ))
        T3(( T3 ))
    end

    subgraph Labs
        L0(( L0 ))
        L1(( L1 ))
        L2(( L2 ))
        L3(( L3 ))
    end

    subgraph Devices
        GPU0(( GPU0 ))
        GPU1(( GPU1 ))
    end
    
    T0 --- S0
    T1 --- S0
    T2 === S1
    T2 === S2

    L0 --- T0
    L1 --- T0
    L0 --- T1
    L1 --- T1
    L2 === T2
    L3 === T3
    
    GPU0 === L2
    GPU0 === L3
    GPU1 === L3

    %% Apply styling
    class S0,S1,S2,T0,T1,T2,T3,L0,L1,L2,L3,GPU0,GPU1 dot;

The number of rows in the intermediate result for Order 2 is also equal to the number of paths from the “Device” field to the “Teacher” field.

In fact, whether choosing Left-to-Right or Right-to-Left, both orders produce some waste in the intermediate results:

• When going Left-to-Right, reaching L0 and L1 is a dead end (cannot reach a Device).
• When going Right-to-Left, reaching T3 is a dead end (cannot reach a Student).

Taking it to the Extreme

graph LR
    %% Define styling to match the handwritten dot style
    classDef dot stroke-width:2px;
    classDef thick-line stroke-width:4px;

    %% Layer definitions for alignment
    subgraph Students
        S0(( S0 ))
        S1(( S1 ))
        S2(( S2 ))
        S3(( S3 ))
        S4(( S4 ))
    end

    subgraph Teachers
        T0(( T0 ))
        T1(( T1 ))
        T2(( T2 ))
        T3(( T3 ))
    end

    subgraph Labs
        L0(( L0 ))
        L1(( L1 ))
        L2(( L2 ))
        L3(( L3 ))
    end

    subgraph Devices
        GPU0(( GPU0 ))
        GPU1(( GPU1 ))
        GPU2(( GPU2 ))
        GPU3(( GPU3 ))
        GPU4(( GPU4 ))
    end

    S0 --- T0
    S1 --- T0
    S2 --- T0
    S3 --- T0

    T0 --- L0
    T0 --- L1
    
    T1 --- L2
    T2 --- L2
    
    L2 --- GPU0
    L2 --- GPU1
    L2 --- GPU2
    L2 --- GPU3
    
    S4 --- T3 --- L3 --- GPU4

    %% Apply styling
    class S0,S1,S2,S3,S4,T0,T1,T2,T3,L0,L1,L2,L3,GPU0,GPU1,GPU2,GPU3,GPU4 dot;

The example shown above is very extreme: almost all students (S0-S3) chose the same teacher (T0), and almost all devices (GPU0-GPU3) are concentrated in the same lab (L2). However, the most popular teacher (T0) belongs to labs (L0/L1) that don’t have a single machine…

Assuming this is reality, it is easy to see that after performing the same JOIN query on this database instance, the result should contain only one row:

However, if we adopt the “Pairwise JOIN” scheme, regardless of which JOIN order is chosen, the intermediate results will have 9 rows (interactions between T0’s students and L2’s devices or similar paths). When the data volume is larger and similar Data Skew exists, the waste of computing resources can be immense.

What should we do?

Global Perspective

Let’s continue to observe this extreme example. What causes the waste in intermediate results are those dead-end paths. So, is it possible to filter out these dead ends before generating intermediate results?

Yes, but the Pairwise JOIN method obviously won’t work; we need a Global Perspective.

The cause of data expansion is that data rows joining on the same field value in two tables create a Cartesian product. Therefore, we need to avoid performing a JOIN (or strictly speaking, avoid performing an INNER JOIN) before completing the filtering.

Why speak strictly? Because we actually still have to JOIN, but it is a special kind of JOIN: SEMI JOIN. It is perfectly suited for this filtering task.

First Pass: Left to Right

To filter out rows in the right table that cannot JOIN.

Teacher_Lab_1 = SELECT * FROM Teacher_Lab WHERE EXISTS(
    SELECT * FROM Student_Teacher WHERE (Student_Teacher.Teacher = Teacher_Lab.Teacher)
)

Lab_Device_1 = SELECT * FROM Lab_Device WHERE EXISTS(
    SELECT * FROM Teacher_Lab_1 WHERE (Teacher_Lab_1.Lab = Lab_Device.Lab)
)

graph LR
    %% Define styling to match the handwritten dot style
    classDef dot stroke-width:2px;
    classDef dotrm fill:#aaa,stroke:#666,stroke-width:2px;

    %% Layer definitions for alignment
    subgraph Students
        S0(( S0 ))
        S1(( S1 ))
        S2(( S2 ))
        S3(( S3 ))
        S4(( S4 ))
    end

    subgraph Teachers
        T0(( T0 ))
        T1(( T1 ))
        T2(( T2 ))
        T3(( T3 ))
    end

    subgraph Labs
        L0(( L0 ))
        L1(( L1 ))
        L2(( L2 ))
        L3(( L3 ))
    end

    subgraph Devices
        GPU0(( GPU0 ))
        GPU1(( GPU1 ))
        GPU2(( GPU2 ))
        GPU3(( GPU3 ))
        GPU4(( GPU4 ))
    end

    S0 --- T0
    S1 --- T0
    S2 --- T0
    S3 --- T0

    T0 --- L0
    T0 --- L1
    
    T1 ~~~ L2
    T2 ~~~ L2
    
    L2 ~~~ GPU0
    L2 ~~~ GPU1
    L2 ~~~ GPU2
    L2 ~~~ GPU3
    
    S4 --- T3 --- L3 --- GPU4

    %% Apply styling
    class S0,S1,S2,S3,S4,T0,T3,L0,L1,L3,GPU4 dot;
    class T1,T2,L2,GPU0,GPU1,GPU2,GPU3 dotrm;

We guarantee that the filtered data in the right-side table can definitely JOIN with all data tables to its left (including non-adjacent ones). Therefore, after completing the first pass of filtering, the data remaining in the right-most table is guaranteed to participate in the final result.

Second Pass: Right to Left

To filter out rows in the left table that cannot JOIN.

Teacher_Lab_2 = SELECT * FROM Teacher_Lab_1 WHERE EXISTS(
    SELECT * FROM Lab_Device_1 WHERE (Teacher_Lab_1.Lab = Lab_Device_1.Lab)
)

Student_Teacher_1 = SELECT * FROM Student_Teacher WHERE EXISTS(
    SELECT * FROM Teacher_Lab_2 WHERE (Student_Teacher.Teacher = Teacher_Lab_2.Teacher)
)

graph LR
    %% Define styling to match the handwritten dot style
    classDef dot stroke-width:2px;
    classDef dotrm fill:#aaa,stroke:#666,stroke-width:2px;

    %% Layer definitions for alignment
    subgraph Students
        S0(( S0 ))
        S1(( S1 ))
        S2(( S2 ))
        S3(( S3 ))
        S4(( S4 ))
    end

    subgraph Teachers
        T0(( T0 ))
        T1(( T1 ))
        T2(( T2 ))
        T3(( T3 ))
    end

    subgraph Labs
        L0(( L0 ))
        L1(( L1 ))
        L2(( L2 ))
        L3(( L3 ))
    end

    subgraph Devices
        GPU0(( GPU0 ))
        GPU1(( GPU1 ))
        GPU2(( GPU2 ))
        GPU3(( GPU3 ))
        GPU4(( GPU4 ))
    end

    S0 ~~~ T0
    S1 ~~~ T0
    S2 ~~~ T0
    S3 ~~~ T0

    T0 ~~~ L0
    T0 ~~~ L1
    
    T1 ~~~ L2
    T2 ~~~ L2
    
    L2 ~~~ GPU0
    L2 ~~~ GPU1
    L2 ~~~ GPU2
    L2 ~~~ GPU3
    
    S4 --- T3 --- L3 --- GPU4

    %% Apply styling
    class S4,T3,L3,GPU4 dot;
    class S0,S1,S2,S3,T0,L0,L1 dotrm;
    class T1,T2,L2,GPU0,GPU1,GPU2,GPU3 dotrm;

We guarantee that the filtered data in the left-side table can definitely JOIN with all data tables to its right (including non-adjacent ones). Since the first pass guaranteed the right-most data participates in the final result, the second pass ensures that the remaining data in ALL tables will participate in the final result.

Third Pass: Left to Right

To complete the JOIN.

At this point, all paths that do not participate in the final JOIN result have been cleared away. We can now safely perform Pairwise JOINs.

Summary: Yannakakis Algorithm (Simplified)

What is introduced here is the Yannakakis Algorithm specialized for linear JOIN queries. Compared to Pairwise JOIN, its advantage lies in being sensitive to the result size.

The complexity of Pairwise JOIN is independent of the JOIN result size. Therefore, even if the final result is actually very small, it may produce a massive amount of intermediate results. For the database instance mentioned above, the time complexity of Pairwise JOIN is $O(N^2)$, whereas the time complexity of the Yannakakis algorithm shown here is $O(N+OUT)$, where $N$ is the data size and $OUT$ is the size of the JOIN result.

The worst-case time complexity for both is consistent. Assuming there are $K$ data tables with no common attributes, equivalent to doing a full Cartesian product: Pairwise JOIN time complexity is $O(N^K)$, and Yannakakis time complexity is $O(N+OUT)$, where $OUT=N^K$.

JOIN algorithms with $O(N+OUT)$ complexity are also known as Output-Optimal algorithms. Regardless of the JOIN algorithm, one must read all the data ($O(N)$) and output all the results ($O(OUT)$), so $O(N+OUT)$ is already optimal for a specific output size.

Graphical Representation of Joins

In the previous note, we discussed the specialized version of the Yannakakis algorithm for linear JOIN queries. However, queries in practice go far beyond just linear structures. So, how do we generalize the Yannakakis algorithm to various types of JOIN queries?

Graphical Representation

Recap: Path Graph of a Database Instance

Previously, we showed the path graph of a database instance. This represents the specific data content of a database instance (where every edge represents a row of data in a table):

graph LR
    %% Define styling to match the handwritten dot style
    classDef dot stroke-width:2px;

    %% Layer definitions for alignment
    subgraph Students
        S0(( S0 ))
        S1(( S1 ))
        S2(( S2 ))
    end

    subgraph Teachers
        T0(( T0 ))
        T1(( T1 ))
        T2(( T2 ))
        T3(( T3 ))
    end

    subgraph Labs
        L0(( L0 ))
        L1(( L1 ))
        L2(( L2 ))
        L3(( L3 ))
    end

    subgraph Devices
        GPU0(( GPU0 ))
        GPU1(( GPU1 ))
    end

    S0 --- T0
    S0 --- T1
    S1 --- T2
    S2 --- T2
    
    T0 --- L0
    T0 --- L1
    T1 --- L0
    T1 --- L1
    T2 --- L2
    T3 --- L3
    
    L2 --- GPU0
    L3 --- GPU0
    L3 --- GPU1

    %% Apply styling
    class S0,S1,S2,T0,T1,T2,T3,L0,L1,L2,L3,GPU0,GPU1 dot;

But now, we want to represent the structure of the JOIN query itself graphically, without involving specific database instances—in other words, in a data-independent way.

Graphical Representation of Query Plans

Now, disregarding data content, the path graph above transforms into paths between data tables. Considering the Left-to-Right and Right-to-Left orders, we can draw the following two charts:

flowchart TD
    subgraph Order 2
    direction BT
    A2["Student_Teacher (Student, Teacher)"]
    B2["Teacher_Lab (Teacher, Lab)"]
    C2["Lab_Device (Lab, Device)"]
    C2 --> B2 --> A2
    end
    subgraph Order 1
    direction BT
    A["Student_Teacher (Student, Teacher)"]
    B["Teacher_Lab (Teacher, Lab)"]
    C["Lab_Device (Lab, Device)"]
    A --> B --> C
    end

In a path graph, paths can only be linked if adjacent tables share common attributes. We can mark these common attributes on the edges of the graph. Additionally, if we view this as an undirected graph, we don’t need to distinguish between the two orders.

flowchart BT
    A["Student_Teacher (Student, Teacher)"]
    B["Teacher_Lab (Teacher, Lab)"]
    C["Lab_Device (Lab, Device)"]
    A--Teacher---B 
    B--Lab---C

Now, let’s consider a slightly more complex example.

Graphical Representation of Star JOIN Queries

Star JOIN query structures are very common in practice, primarily existing in scenarios using foreign keys. Assume we have the following data tables:

1. Orders (Order_ID, Warehouse_ID, Product_ID, Buyer_ID)
2. Warehouses (Warehouse_ID, Warehouse_Address)
3. Products (Product_ID, Product_Name)
4. Buyers (Buyer_ID, Buyer_Name, Buyer_Address)

We want to retrieve all order details:

SELECT * FROM Orders
    JOIN Warehouses ON Warehouse_ID
    JOIN Products ON Product_ID
    JOIN Buyers ON Buyer_ID

The graphical representation of this query is as follows:

flowchart TB
    B[Warehouses]
    A[Orders]
    C[Products]
    D[Buyers]
    
    A --Warehouse_ID --- B
    A --Product_ID --- C
    D --Buyer_ID --- A

At first glance, this graph might not seem “star-shaped”; it looks more like a tree. However, if the Orders table had more foreign keys, I believe the reader would understand why this category of queries is called a Star Query.

Additionally, calling it a tree is also correct; a star structure is essentially a tree. In fact, the graphical representation of a JOIN query is called a Join Tree.

Hypergraphs and Join Trees

We have gained a superficial understanding of Join Trees, but we have not yet provided a formal definition because we are missing a tool—the Hypergraph. Hypergraphs can also be used to visually display JOIN queries; the difference is that Hypergraphs merely represent the structure of the JOIN query, while Join Trees imply information about the query execution plan.

Hypergraph

A Hypergraph $H=(V,E)$ consists of a finite number of vertices and a set of hyperedges, where $V$ represents the finite set of vertices and $E$ represents the set of hyperedges.

Unlike edges in a standard Graph which can only connect two endpoints, a Hyperedge $e\in E$ can connect multiple vertices simultaneously, represented as a subset of vertices in the hypergraph, i.e., $e\subseteq V$.

Hypergraphs map very naturally to JOIN queries:

• Each vertex represents a column (attribute) in the data tables.
• Each hyperedge contains multiple vertices, thus representing a data table.

Using the Star Query mentioned earlier as an example:

Note

In this hypergraph, a “circle” is actually a hyperedge, corresponding to a data table (the table name is connected by a dashed line); each word inside the circle is a vertex, corresponding to a column.

It took me some time to get used to the graphical representation of hypergraphs—after all, the “edges” in the graphs we usually encounter are represented by thin lines, unlike these “hyperedges” which actually have area.

Join Tree

The formal definition of a Join Tree corresponds to that of a hypergraph.

Given a hypergraph $H=(V,E)$, its corresponding Join Tree is a tree $T$ that satisfies the following two conditions:

1. The nodes of tree $T$ correspond one-to-one with the hyperedges ($e\in E$) of hypergraph $H$.
2. For any hypergraph vertex $v\in V$, the set of tree nodes in $T$ corresponding to the hyperedges containing $v$ forms a connected subgraph. (This is often called the Running Intersection Property).

Let’s stick with the previous example. The hypergraph has 4 hyperedges, corresponding to 4 data tables: Buyers, Orders, Warehouses, Products.

Its corresponding Join Tree is as follows. We can see that the Join Tree has 4 nodes, corresponding one-to-one with the 4 hyperedges, thus satisfying the first condition.

flowchart TB
    B["Warehouses(Warehouse_ID, Address)"]
    A["Orders(Order_ID, Warehouse_ID, Product_ID, Buyer_ID)"]
    C["Products(Product_ID, Name)"]
    D["Buyers(Buyer_ID, Name, Address)"]
    
    A --Warehouse_ID --- B
    A --Product_ID --- C
    D --Buyer_ID --- A

The phrasing of the second condition is slightly more complex, but understanding it is quite easy:

• “Hyperedges containing a common vertex $v\in V$” simply means data tables that share a common field (e.g., “Buyers” and “Orders” share the “Buyer_ID” field).
• “Corresponding nodes in tree $T$” refers to finding the tree nodes corresponding to these data tables in the Join Tree (since condition 1 requires a one-to-one mapping).
• “Forms a connected subgraph”: This is a basic graph theory concept. For a tree (an undirected graph), if there is a path between two points, they are connected (the path doesn’t have to be a direct edge; it can pass through multiple edges).

In the Join Tree above, we can see that the two nodes “Buyers” and “Orders”, which share the common field “Buyer_ID”, are indeed connected. Iterating through every field can prove that this Join Tree satisfies the second condition.

Yannakakis Algorithm (Full Version)

With the Join Tree, we can now complete the Yannakakis algorithm introduced earlier on this tree. Unlike before, where we only performed JOINs on a linear sequence of tables, we can now perform JOINs on a tree, thereby supporting more types of queries.

Let’s Recap

The simplified algorithm flow mentioned in the previous note was:

1. First Pass: Left to Right, filter out rows in the right-side table that cannot JOIN.
   • After the first pass, data remaining in the right-most table is guaranteed to participate in the final result.
2. Second Pass: Right to Left, filter out rows in the left-side table that cannot JOIN.
   • The second pass guarantees that the remaining data in ALL tables will participate in the final result.
3. Third Pass: Left to Right, complete the JOIN.

Generalizing to Join Trees

The characteristics of the two-pass filtering can easily be generalized to a tree structure.

1. First Pass: Bottom-Up (from leaf nodes up to the root), filtering out rows in parent nodes that cannot JOIN with any child node.
   • After the first pass, the data remaining in the root node is guaranteed to participate in the final result.
2. Second Pass: Top-Down, filtering out rows in child nodes that cannot JOIN with the parent node.
   • The second pass guarantees that the remaining data in ALL tables will participate in the final result.
3. Third Pass: Bottom-Up, complete the JOIN.

Pseudo-code

Input: Join Tree $\mathcal{T}$, Set of Relations $\mathcal{R}$, Root Node $r$. Output: Result of the JOIN ${\bowtie }_{e\in \mathcal{T}}{R}_e$.

1. Preprocessing: Determine Parent-Child Relationships
   For each node $e$ in $\mathcal{T}$:
   $p_e\leftarrow$ the parent node of node $e$ in tree $\mathcal{T}$;
2. Bottom-Up Phase
   Visit node $e$ of $\mathcal{T}$ in Bottom-Up order (excluding root $r$):
   $R_{p_e}\leftarrow R_{p_e}⋉R_e$
   // Filter tuples in parent relation that do not match using child relation
3. Top-Down Phase
   Visit node $e$ of $\mathcal{T}$ in Top-Down order (excluding root $r$):
   $R_e\leftarrow R_e⋉R_{p_e}$
   // Filter tuples in child relation that do not match using parent relation
4. Compute and Return JOIN Result
   At this point, all relations have reached “Global Consistency” (every tuple is guaranteed to appear in the final JOIN result):
   Return the natural join of all relations: ${\bowtie }_{e\in \mathcal{T}}{R}_e$

New Problem: Does Every Query Correspond to a Join Tree?

Suppose we have three data tables: $R(a,b),S(b,c),T(c,a)$.

Consider the following query:

SELECT * FROM R, S, T WHERE R.a = T.a AND R.b = S.b AND S.c = T.c

Can you find the Join Tree that corresponds to it?

Notes for Foundations of Databases

Foundations of Databases (The Alice Book)

The Alice Book is helpful for understanding the basic notations in database theory. I recommend to read the first two chapters to get familiar with the notations used in this course.

That said, the book is not required. In fact, paying real attention to the first several lectures should be sufficient to survive the course, and it turns out to be interesting.

In this section, I summarize some key concepts from the first two chapters of the Alice Book.

The Relational Model

Informal Terminology

• Relation: table
  • Relation Name: name of the table
• Attribute: column name
• Tuple/Record: line in the table
• Domain: set of constants that entries of tuples can take
• Database Schema: specifying the structure of the database
• Database Instance: specifying the actual content in the database

Formal Definitions

• $\text{att}$: a countably infinite set of attributes
  • assume $\text{att}$ is fixed
• ${\le }_{\text{att}}$: a total order on $\text{att}$
  • the elements of a set of attributes $U$ are written according to ${\le }_{\text{att}}$ unless otherwise specified
• $\text{dom}$: a countably infinite set of domains (disjoint from $\text{att}$)
  • assume $\text{dom}$ is fixed
  • a constant is an element of $\text{dom}$
  • for most cases, the same domain of values is used for all attributes;
    • otherwise, assume a mapping $\text{Dom}$ on $\text{att}$, where $\text{Dom}(A)$ is a set called the domain of attribute $A$
• $\text{relname}$: a countably infinite set of relation names (disjoint from $\text{att}$ and $\text{dom}$)
• $\text{sort}$: a function from $\text{relname}$ to ${\mathcal{P}}^{\text{fin}}(\text{att})$ (the finitary powerset of $\text{att}$)
  • ${\text{sort}}^{-1}(U)$ is inifinite for each (possibly empty) finite set of attributes $U$
    • which allows multiple relations to have the same set of attributes
  • $\text{sort}(R)$ is called the $\text{sort}$ of a relation name $R$
  • $\text{arity}(R)=|\text{sort}(R)|$: the $\text{arity}$ of relation name $R$
• $R$: a relation name or a relation schema
  • Alternative notations:
    • $R[U]$: indicating $\text{sort}(R)=U$
    • $R[n]$: indicating $\text{arity}(R)=n$
• $\text{R}$: a database schema
  • a nonempty finite set of relation names
  • might be written as $\text{R}=\{R_1[U_1],\dots ,R_n[U_n]\}$

Examples

Table Movies

Table Location

Table Pariscope

• The database schema $\text{CINEMA}=\{\text{Movies},\text{Location},\text{Pariscope}\}$
• The sorts of the relation names
  • $\text{sort}(\text{Movies})=\{\text{Title},\text{Director},\text{Actor}\}$
  • $\text{sort}(\text{Location})=\{\text{Theater},\text{Address},\text{Phone}\}$
  • $\text{sort}(\text{Pariscope})=\{\text{Theater},\text{Title},\text{Schedule}\}$

Named v.s. Unnamed Attributes/Tuples

Named Perspective

E.g. $⟨A:5,B:3⟩$

a tuple over a finite set of attributes $U$ (or over a relation schema $R[U]$) is a total mapping (viewed as a function) $u$ from $U$ to $\text{dom}$.

• $u(U)$: $u$ is a tuple over $U$
• $u(A)$: the value of $u$ on an attribute $A$ in $U$ ($A\in U$)
• $u[V]=u{|}_V$: the restriction of $u$ to a subset $V\subseteq U$, i.e., $u[V]$ denotes the tuple $v$ over $V$ such that $v(A)=u(A)$ for all $A\in V$

Unnamed Perspective

E.g. $⟨5,3⟩$

a tuple is an ordered n-tuple ($n\ge 0$) of constants (i.e., an element of the Cartesian product ${\text{dom}}^n$)

• $u(i)$: the $i$-th coordinate of $u$

Correspondence

Because of the total order ${\le }_{\text{att}}$, a tuple $⟨A_1:a_1,A_2:a_2⟩$ (defined as a function) can be viewed as an ordered tuple with $(A_1:a_1)$ as a first component and $(A_2:a_2)$ as a second component. Ignoring the names, this tuple can be viewed as the ordered tuple $⟨a_1,a_2⟩$.

Conversely, the ordered tuple $t=⟨a_1,a_2⟩$ can be viewed as a function over the set of integers $\{1,2\}$ with $t(i)=a_i$ for each $i$.

Conventional v.s. Logic Programming Relational Model

Conventional Perspective

a relation (instance) over a relation schema $\text{R}[U]$ is a finite set of tuples $I$ with sort $U$.

a database instance of database schema $\text{R}$ is a mapping $\text{I}$ with domain $\text{R}$, such that $\text{I}(\text{R})$ is a relation over $\text{R}$ for each $\text{R}\in \text{R}$.

Logic Programming Perspective

This perspective is used primarily with the ordered-tuple perspective on tuples.

A fact over $\text{R}$ is an expression of the form $\text{R}(a_1,\dots ,a_n)$, where $a_i\in \text{dom}$ for $i\in [1,n]$.
If $u=⟨a_1,\dots ,a_n⟩$, we sometimes write $\text{R}(u)$ for $\text{R}(a_1,\dots ,a_n)$.

a relation (instance) over a relation schema $\text{R}$ is a finite set of facts over $\text{R}$.

a database instance of database schema $\text{R}$ is a finite set $\text{I}$ that is the union of relation instances over $\text{R}$ for all $\text{R}\in \text{R}$.

Examples

Assume $\text{sort}(R)=AB,\text{sort}(S)=A$.

Named and Conventional

$$\begin{array}{rlr}I(R)=\{f_1,f_2,f_3\}& & \\ & f_1(A)=a& f_1(B)=b\\ & f_2(A)=c& f_2(B)=b\\ & f_3(A)=a& f_3(B)=a\\ I(S)=\{g\}& & \\ & g(A)=d& \end{array}$$

Unnamed and Conventional

$$\begin{array}{rlr}I(R)=\{⟨a,b⟩,⟨c,b⟩,⟨a,a⟩\}& & \\ I(S)=\{⟨d⟩\}& & \end{array}$$

Named and Logic Programming

$$\{R(A:a,B:b),R(A:c,B:b),R(A:a,B:a),S(A:d)\}$$

Unnamed and Logic Programming

$$\{R(a,b),R(c,b),R(a,a),S(d)\}$$

Variables

an infinite set of variables $\text{var}$ will be used to range over elements of $\text{dom}$.

• a free tuple over $U$ or $\text{R}(U)$ is a function $u$ from $U$ to $\text{dom}\cup \text{var}$
• an atom over $\text{R}$ is an expression of the form $\text{R}(e_1,\dots ,e_n)$, where $n=\text{arity}(\text{R})$ and each term $e_i\in \text{dom}\cup \text{var}$
• a ground atom is an atom with no variables, i.e., a fact (see Logic Programming Perspective)

Notations

Conjunctive Queries

a query (mapping) is from (or over) its input schema and to its output schema.

• query: a syntactic object
• query mapping: a function defined by a query interpreted under a specified semantics
  • its domain: the family of all instances of an input schema
  • its range: the family of instances of an output schema
  • we often blur query and query mapping when the meaning is clear from context
• input schema: a specified relation or database schema
• output schema: a relation schema or database schema
  • For a relation schema, the relation name may be specified as part of the query syntax or by the context
• $q_1\equiv q_2$ denotes two queries $q_1$ and $q_2$ over $\text{R}$ are equivalent, i.e., they have the same output schema and $q_1(\text{I})=q_2(\text{I})$ for each instance $\text{I}$ over $\text{R}$.

Logic-Based Perspective

Three versions of conjunctive queries:

1. Rule-Based Conjunctive Queries
2. Tableau Queries
3. Conjunctive Calculus

Rule-Based Conjunctive Queries

Definition

A rule-based conjunctive query (or often more simply called rules) $q$ over a relation schema $\text{R}$ is an expression of the form $$\text{ans}(u)\leftarrow {\text{R}}_1(u_1),\dots ,{\text{R}}_n(u_n)$$ where $n\ge 0$, ${\text{R}}_1,\dots ,{\text{R}}_n$ are relation names in $\text{R}$; $\text{ans}$ is a relation name not in $\text{R}$; and $u,u_1,\dots ,u_n$ are free tuples (i.e., may use either variables or constants).

• $\text{var}(q)$: the set of variables occurring in $q$.
• body: ${\text{R}}_1(u_1),\dots ,{\text{R}}_n(u_n)$
• head: $\text{ans}(u)$
• range restricted: each variable occurring in the head also occurs in the body
  • all conjunctive queries considered here are range restricted
• valuation: a valuation $v$ over $V$, a finite subset of $\text{var}$, is a total function $v$ from $V$ to $\text{dom}$ (of constants)
  • extended to be identity on $\text{dom}$ (so that the domain can contain both variables and constants)
  • extended to map free tuples to tuples (so that the domain/range can be in the tuple form)

Semantics

Let $q$ be the query, and let $\text{I}$ be a database instance of schema $\text{R}$. The image of $\text{I}$ under $q$ is:

$$q(\text{I})=\{v(u)\mid v\text{ is a valuation over }\text{var}(q)\text{ and }v(u_i)\in \text{I}({\text{R}}_i)\text{ for each }i\in [1,n]\}$$

• active domain
  • of a database instance $\text{I}$, denoted $\text{adom}(\text{I})$, is the set of constants that occur in $\text{I}$
  • of a relation instance $I$, denoted $\text{adom}(I)$, is the set of constants that occur in $I$
  • of a query $q$, denoted $\text{adom}(q)$, is the set of constants that occur in $q$
  • $\text{adom}(q,\text{I})$ is an abbreviation for $\text{adom}(q)\cup \text{adom}(\text{I})$
    • $\text{adom}(q(\text{I}))\subseteq \text{adom}(q,\text{I})$
• extensional relations: relations in the body of the query, i.e., ${\text{R}}_1,\dots ,{\text{R}}_n$
  • because they are known/provided by the input instance $\text{I}$
• intensional relation: the relation in the head of the query, i.e., $\text{ans}$
  • because it is not stored and its value is computed on request by the query
• extensional database (edb): a database instance associated with the extensional relations
• intensional database (idb): the rule itself
• idb relation: the relation defined by the idb

Properties

Conjunctive queries are:

• monotonic: a query $q$ over $\text{R}$ is monotonic if for each $\text{I},\text{J}$ over $\text{R}$, $\text{I}\subseteq \text{J}⟹q(\text{I})\subseteq q(\text{J})$
• satisfiable: a query $q$ is satisfiable if there exists a database instance $\text{I}$ such that $q(\text{I})\ne \varnothing$

Tableau Queries

A tableau query is simply a pair $(\text{T},u)$ where $\text{T}$ is a tableau and each variable in $u$ also occurs in $\text{T}$.

This is closest to the visual form provided by Query-By-Example (QBE).

• summary: the free tuple $u$ representing the tuples included in the answer to the query
• embedding: a valuation $v$ for the variables occurring in $\text{T}$ such that $v(\text{T})\subseteq \text{I}$
  • the output of $(\text{T},u)$ on $\text{I}$ consists of all tuples $v(u)$ for each embedding $v$ of $\text{T}$ into $\text{I}$
• typed: a tableau query $q=(\text{T},u)$ under the named perspective, where $\text{T}$ is over relation schema $R$ and $\text{sort}(u)\subseteq \text{sort}(R)$, is typed if no variable of $\text{T}$ is associated with two distinct attributes in $q$

Examples

Table Movies

Table Location

Table Pariscope

The above tableau query is typed because each variable is associated with only one attribute:

• $x_{ti}$: $\text{Title}$
• $x_{ac}$: $\text{Actor}$
• $x_{th}$: $\text{Theater}$
• $x_{ad}$: $\text{Address}$
• $x_p$: $\text{Phone}$
• $x_s$: $\text{Schedule}$

However, the following tableau query is untyped:

Table Movies

Because $x_{ac}$ is associated with both $\text{Director}$ and $\text{Actor}$.

Conjunctive Calculus

The conjunctive query

$$\text{ans}(u)\leftarrow {\text{R}}_1(u_1),\dots ,{\text{R}}_n(u_n)$$

can be expressed as the following conjunctive calculus query that has the same semantics:

$$\left\{e_1,\dots ,e_m|\exists x_1,\dots ,x_k\left(\text{R}(u_1)\wedge \dots \wedge \text{R}(u_n)\right)\right\}$$

where $x_1,\dots ,x_k$ are all the variables occurring in the body and not the head.

Conjunctive Calculus Formula

Let $\text{R}$ be a relation schema. A (well-formed) formula over $\text{R}$ for the conjunctive calculus is an expression having one of the following forms:

1. an atom over $\text{R}$;
2. $\phi \wedge \psi$, where $\phi$ and $\psi$ are formulas over $\text{R}$; or
3. $\exists x\phi$, where $x$ is a variable and $\phi$ is a formula over $\text{R}$.

An occurrence of a variable $x$ in formula $\phi$ is free if:

1. $\phi$ is an atom; or
2. $\phi =(\psi \wedge \xi )$ and the occurrence of $x$ is free in $\psi$ or $\xi$; or
3. $\phi =\exists y\psi$, $x\ne y$, and the occurrence of $x$ is free in $\psi$.

$\text{free}(\phi )$: the set of free variables in $\phi$.

An occurrence of a variable that is not free is bound.

Conjunctive Calculus Query

A conjunctive calculus query over database schema $\text{R}$ is an expression of the form

$$\{e_1,\dots ,e_m\mid \phi \}$$

where

• $\phi$ is a conjunctive calculus formula,
• $⟨e_1,\dots ,e_m⟩$ is a free tuple, and
• the set of variables occurring in $⟨e_1,\dots ,e_m⟩$ is exactly $\text{free}(\phi )$.

For named perspective, the above query can be written as:

$$\{⟨e_1,\dots ,e_m⟩:A_1,\dots ,A_m\mid \phi \}$$

Note: In the previous chapter, a named tuple was usually denoted as:

$$⟨A_1:a_1,\dots ,A_m:a_m⟩$$

But here we denote the named tuple as:

$$⟨e_1,\dots ,e_m⟩:A_1,\dots ,A_m$$

Not sure which one is better or whether the author did this intentionally.

Semantics

Valuation

A valuation over $V\subset \text{var}$ is a total function $v$ from $V$ to $\text{dom}$, which can be viewed as a syntactic expression of the form:

$$\{x_1/a_1,\dots ,x_n/a_n\}$$

where

• $x_1,\dots ,x_n$ is a listing of $V$,
• $a_i=v(x_i)$ for each $i\in [1,n]$.

Interpretation as a Set

If $x\notin V$, and $c\in \text{dom}$, then $v\cup \{x/c\}$ is the valuation over $V\cup \{x\}$ that agrees with $v$ on $V$ and maps $x$ to $c$.

Satisfaction

Let $\text{R}$ be a database schema, $\phi$ a conjunctive calculus formula over $\text{R}$, and $v$ a valuation over $\text{free}(\phi )$. Then $\text{I}\models \phi [v]$, if

1. $\phi =\text{R}(u)$ is an atom and $v(u)\in \text{I}(\text{R})$; or
2. $\phi =(\psi \wedge \xi )$ and $\text{I}\models \psi [v{|}_{\text{free}(\psi )}]$ and $\text{I}\models \xi [v{|}_{\text{free}(\xi )}]$; or
3. $\phi =\exists x\psi$ and there exists a constant $c\in \text{dom}$ such that $\text{I}\models \psi [v\cup \{x/c\}]$.

Image

Let $q=\{e_1,\dots ,e_m\mid \phi \}$ be a conjunctive calculus query over $\text{R}$. For an instance $\text{I}$ over $\text{R}$, the image of $\text{I}$ under $q$ is: $$q(\text{I})=\{v(⟨e_1,\dots ,e_m⟩)\mid v\text{ is a valuation over }\text{free}(\phi )\text{ and }\text{I}\models \phi [v]\}$$

• active domain
  • of a formula $\phi$, denoted $\text{adom}(\phi )$, is the set of constants that occur in $\phi$
  • $\text{adom}(\phi ,\text{I})$ is an abbreviation for $\text{adom}(\phi )\cup \text{adom}(\text{I})$
  • If $\text{I}\models \phi [v]$, then the range of $v$ is contained in $\text{adom}(\text{I})$
    • to evaluate a conjunctive calculus query, one need only consider valuations with range constrained in $\text{adom}(\phi ,\text{I})$, i.e., only a finite number of them
• equivalent: conjunctive calculus formulas $\phi$ and $\psi$ over $\text{R}$ are equivalent, if
  • they have the same free variables and,
  • for each $\text{I}$ over $\text{R}$ and valuation $v$ over $\text{free}(\phi )=\text{free}(\psi )$, $\text{I}\models \phi [v]$ if and only if $\text{I}\models \psi [v]$

Normal Form

$$\exists x_1,\dots ,x_m\left({\text{R}}_1(u_1)\wedge \dots \wedge {\text{R}}_n(u_n)\right)$$

Each conjunctive calculus query is equivalent to a conjunctive calculus query in normal form.

Expressiveness of Query Languages

Let ${\mathcal{Q}}_1$ and ${\mathcal{Q}}_2$ be two query languages.

• ${\mathcal{Q}}_1⊑{\mathcal{Q}}_2$: ${\mathcal{Q}}_1$ is dominated by ${\mathcal{Q}}_2$ (or ${\mathcal{Q}}_2$ is weaker than ${\mathcal{Q}}_1$), if for each query $q_1\in {\mathcal{Q}}_1$, there exists a query $q_2\in {\mathcal{Q}}_2$ such that $q_1\equiv q_2$.
• ${\mathcal{Q}}_1\equiv {\mathcal{Q}}_2$: ${\mathcal{Q}}_1$ and ${\mathcal{Q}}_2$ are equivalent, if ${\mathcal{Q}}_1⊑{\mathcal{Q}}_2$ and ${\mathcal{Q}}_2⊑{\mathcal{Q}}_1$.

The rule-based conjunctive queries, tableau queries, and conjunctive calculus queries are all equivalent.

Incorporating Equality

The conjunctive query

$$\begin{array}{rl}\text{ans}(x_{th},x_{ad})\leftarrow & \text{Movies}(x_{ti},\text{"Bergman"},x_{ac}),\\ & \text{Location}(x_{th},x_{ad},x_p),\text{Pariscope}(x_{th},x_{ti},x_s)\end{array}$$

can be expressed as:

$$\begin{array}{rl}\text{ans}(x_{th},x_{ad})\leftarrow & \text{Movies}(x_{ti},x_d,x_{ac}),x_d=\text{"Bergman"},\\ & \text{Location}(x_{th},x_{ad},x_p),\text{Pariscope}(x_{th},x_{ti},x_s)\end{array}$$

Problem 1: Infinite Answers

Unrestricted rules with equality may yield infinite answers:

$$\text{ans}(x,y)\leftarrow \text{R}(x),y=z$$

A rule-based conjunctive query with equality is a range-restricted rule-based conjunctive query with equality.

Problem 2: Unsatisfiable Queries

Consider the following query:

$$\text{ans}(x)\leftarrow \text{R}(x),x=a,x=b$$

where $\text{R}$ is a unary relation and $a,b\in \text{dom}$ with $a\ne b$.

Each satisfiable rule with equality is equivalent to a rule without equality.
No expressive power is gained if the query is satisfiable.

Query Composition and Views

a conjunctive query program (with or without equality) is a sequence $P$ of rules having the form:

$$\begin{array}{rl}{S}_1(u_1)& \leftarrow {\text{body}}_1\\ S_2(u_2)& \leftarrow {\text{body}}_2\\ & ⋮\\ S_m(u_m)& \leftarrow {\text{body}}_m\end{array}$$

where

• each $S_i$ is a distinct relation name not in $\text{R}$,
• for each $i\in [1,m]$, the only relation names that may occur in ${\text{body}}_i$ are in $\text{R}\cup \{S_1,\dots ,S_{i-1}\}$.

Closure under Composition

If conjunctive query program $P$ defines final relation $S$, then there is a conjunctive query $q$, possibly with equality, such that on all input instances $\text{I}$, $q(\text{I})=P(\text{I})(S)$.

If $P$ is satisfiable, then there is a $q$ without equality.

Composition and User Views

views are specified as queries (or query programs), which may be

• materialized: a physical copy of the view is stored and maintained
• virtual: relevant information about the view is computed as needed
  • queries against the virtual view generate composed queries against the underlying database

Algebraic Perspectives

The Unnamed Perspective: The SPC Algebra

Unnamed conjunctive algebra:

• Selection ($\sigma$)
• Projection ($\pi$)
• Cross-Product (or Cartesian Product, $\times$)

Selection (“Horizontal” Operator)

Primitive Forms: ${\sigma }_{j=a}$ and ${\sigma }_{j=k}$
where $j,k$ are positive integers, and $a\in \text{dom}$ (constants are usually surrounded by quotes).

$${\sigma }_{j=a}(I)=\{t\in I\mid t(j)=a\}$$

${\sigma }_{j=k}$ is sometimes called atomic selection.

Projection (“Vertical” Operator)

General Form: ${\pi }_{j_1,\dots ,j_n}$
where $n\ge 0$ and $j_1,\dots ,j_n$ are positive integers (empty sequence is written $[]$).

$${\pi }_{j_1,\dots ,j_n}(I)=\{⟨t(j_1),\dots ,t(j_n)⟩\mid t\in I\}$$

Cross-Product (or Cartesian Product)

$$I\times J=\{⟨t(1),\dots ,t(n),s(1),\dots ,s(m)⟩\mid t\in I,s\in J\}$$

Formal Inductive Definition

Let $\text{R}$ be a relation schema.

There are two kinds of base SPC (algebra) queries:

1. Input Relation: Expression $R$; with arity equal to $\text{arity}(R)$
2. Unary Singleton Constant: Expression $\{⟨a⟩\}$, where $a\in \text{dom}$; with arity equal to 1

The family of SPC (algebra) queries contains all above base SPC queries and, for SPC queries $q_1,q_2$ with arities ${\alpha }_1,{\alpha }_2$, respectively,

• Selection: ${\sigma }_{j=1}(q_1)$ and ${\sigma }_{j=k}(q_1)$, whenever $j,k\le {\alpha }_1$ and $a\in \text{dom}$; these have arity ${\alpha }_1$.
• Projection: ${\pi }_{j_1,\dots ,j_n}(q_1)$, where $j_1,\dots ,j_n\le {\alpha }_1$; this has arity $n$.
• Cross-Product: $q_1\times q_2$; this has arity ${\alpha }_1+{\alpha }_2$.

Unsatisifiable Queries

E.g. ${\sigma }_{1=a}({\sigma }_{1=b}(R))$ where $\text{arity}(R)\ge 1$ and $a\ne b$.

This is equivalent to $q^{\varnothing }$.

Generalized SPC Algebra

• Intersection ($\cap$): is easily simulated by selection and cross-product.
• Generalized Selection ($\sigma$): permits the specification of multiple conditions.
  • Positive Conjunctive Selection Formula: $F={\gamma }_1\wedge \dots \wedge {\gamma }_n(n\ge 1)$ where each ${\gamma }_i$ is either $j=k$ or $j=a$
  • Positive Conjunctive Selection Operator: an expression of the form ${\sigma }_F$, where $F$ is a positive conjunctive selection formula
  • can be simulated by a sequence of selections
• Equi-Join ($\bowtie$): a binary operator that combines cross-product and selection
  • Equi-Join Condition: $F={\gamma }_1\wedge \dots \wedge {\gamma }_n(n\ge 1)$ where each ${\gamma }_i$ is of the form $j=k$
  • Equi-Join Operator: an expression of the form $I{\bowtie }_{F}J$, where $F$ is an equi-join condition
  • can be simulated by ${\sigma }_{F^{\prime }}(I\times J)$, where $F^{\prime }$ is obtained from $F$ by replacing each condition $j=k$ with $j=\alpha (I)+k$

Normal Form

$${\pi }_{j_1,\dots ,j_n}(\{⟨a_1⟩\}\times \dots \times \{⟨a_m⟩\}\times {\sigma }_F(R_1\times \dots \times R_k))$$ where

• $n\ge 0;m\ge 0$;
• $a_1,\dots ,a_m\in \text{dom}$;
• $\{1,\dots ,m\}\subseteq \{j_1,\dots ,j_n\}$;
• $R_1,\dots ,R_k$ are relation names (repeats permitted);
• $F$ is a positive conjunctive selection formula.

For each (generalized) SPC query, there is an equivalent SPC query in normal form.

The proof is based on repeated application of the following equivalence-preserving SPC algebra rewrite rules (or transformations):

• Merge-Select: $${\sigma }_F({\sigma }_{F^{\prime }}(q))\equiv {\sigma }_{F\wedge F^{\prime }}(q)$$
• Merge-Project: $${\pi }_{\mathbf{j}}({\pi }_{\mathbf{k}}(q))\equiv {\pi }_{\mathbf{l}}(q),\text{ where }{l}_i=k_{j_i}\text{ for each term }{l}_i\text{ in }\mathbf{l}$$
• Push-Select-Though-Project: $${\sigma }_F({\pi }_{\mathbf{j}}(q))\equiv {\pi }_{\mathbf{j}}({\sigma }_{F^{\prime }}(q)),\text{ where }{F}^{\prime }\text{ is obtained from }F\text{ by replacing each }k\text{ with }{j}_k$$
• Push-Select-Though-Singleton: $${\sigma }_{1=j}(⟨a⟩\times q)\equiv ⟨a⟩\times {\sigma }_{(j-1)=a}(q)$$
• Associate-Cross: $$(q_1\times \dots \times q_n)\times q\equiv q_1\times \dots \times q_n\times q$$ $$q\times (q_1\times \dots \times q_n)\equiv q_1\times \dots \times q_n\times q$$
• Commute-Cross: $$(q\times q^{\prime })\equiv {\pi }_{\mathbf{j}{\mathbf{j}}^{\prime }}(q^{\prime }\times q)$$ where ${\mathbf{j}}^{\prime }=[1,\dots ,\text{arity}(q^{\prime })]$ and $\mathbf{j}=[\text{arity}(q^{\prime })+1,\dots ,\text{arity}(q^{\prime })+\text{arity}(q)]$
• Push-Cross-Though-Select: $${\sigma }_F(q)\times q^{\prime }\equiv {\sigma }_F(q\times q^{\prime })$$ $$q\times {\sigma }_F(q^{\prime })\equiv {\sigma }_{F^{\prime }}(q\times q^{\prime })$$ where $F^{\prime }$ is obtained from $F$ by replacing each $j$ with $\text{arity}(q)+j$
• Push-Cross-Though-Project: $${\pi }_{\mathbf{j}}(q)\times q^{\prime }\equiv {\pi }_{\mathbf{j}}(q\times q^{\prime })$$ $$q\times {\pi }_{\mathbf{j}}(q^{\prime })\equiv {\pi }_{{\mathbf{j}}^{\prime }}(q\times q^{\prime })$$ where ${\mathbf{j}}^{\prime }$ is obtained from $\mathbf{j}$ by replacing each $j$ with $\text{arity}(q)+j$

Notation for Rewriting

$$\begin{array}{rl}q& {\to }_{\mathcal{S}}{q}^{\prime }\text{or}\\ \text{simply}q& \to q^{\prime }\end{array}$$

• for a set $\mathcal{S}$ of rewrite rules and algebra expressions $q,q^{\prime }$,
• if $\mathcal{S}$ is understood from the context,
• if $q^{\prime }$ is the result of replacing a subexpression of $q$ according to one of the rules in $\mathcal{S}$.

${\to }_S^{\ast }$: the reflexive and transitive closure of $\to$.

A family $\mathcal{S}$ of rewrite rules is sound if $q{\to }_{\mathcal{S}}{q}^{\prime }$ implies $q\equiv q^{\prime }$. If $\mathcal{S}$ is sound, then $q{\to }_{\mathcal{S}}^{\ast }{q}^{\prime }$ implies $q\equiv q^{\prime }$.

The Named Perspective: The SPJR Algebra

Named conjunctive algebra:

• Selection ($\sigma$)
• Projection ($\pi$); repeats not permitted
• Join ($\bowtie$); natural join
• Renaming ($\delta$)

Selection

${\sigma }_{A=a},{\sigma }_{A=B}$ where $A,B\in \text{att},a\in \text{dom}$

These operators apply to any instance $I$ with $A,B\in \text{sort}(I)$.

Projection

${\pi }_{A_1,\dots ,A_n}$ where $n\ge 0$ and $A_1,\dots ,A_n\in \text{sort}(I)$

(Natural) Join

$$\begin{array}{rl}I\bowtie J=\{t\text{ over }V\cup W|& \text{ for some }v\in I\text{ and }w\in J,\\ & t[V]=v\wedge t[W]=w\}\end{array}$$ where $I$ and $J$ have sorts $V$ and $W$, respectively.

• When $\text{sort}(I)=\text{sort}(J)$, $I\bowtie J=I\cap J$.
• When $\text{sort}(I)\cap \text{sort}(J)=\varnothing$, $I\bowtie J=I\times J$.

Renaming

An attribute renaming for a finite set $U$ of attributes is a one-one mapping from $U$ to $\text{att}$.

$${\delta }_f(I)=\{v\text{ over }f[U]|\text{ for some }u\in I,v(f(A))=u(A)\text{ for each }A\in U\}$$ where

• input is an instance $I$ over $U$
• $f$ is an attribute renaming for $U$
  • which can be described by $(A,f(A))$, where $f(A)\ne A$
    • usually written as $A_1{A}_2\dots A_n\to B_1{B}_2\dots B_n$ to indicate that $f(A_i)=B_i$ for each $i\in [1,n](n\ge 0)$

Formal Inductive Definition

The base SPJR algebra queries are:

1. Input Relation: Expression $R$; with sort equal to $\text{sort}(R)$
2. Unary Singleton Constant: Expression $\{⟨A:a⟩\}$, where $a\in \text{dom}$; with $\text{sort}=A$

The remainder of the syntax and semantics of the SPJR algebra is defined in analogy to those of the SPC algebra.

Normal Form

$${\pi }_{B_1,\dots ,B_m}(\{⟨A_1:a_1⟩\}\bowtie \dots \bowtie \{⟨A_m:a_m⟩\}\bowtie {\sigma }_F({\delta }_{f_1}(R_1)\bowtie \dots \bowtie {\delta }_{f_k}(R_k)))$$ where

• $n\ge 0;m\ge 0$;
• $a_1,\dots ,a_m\in \text{dom}$;
• $\{A_1,\dots ,A_m\}$ occurs in $\{B_1,\dots ,B_n\}$;
• the $A_i$s are distinct;
• $R_1,\dots ,R_k$ are relation names (repeats permitted);
• ${\delta }_{f_i}$ is a renaming operator for $\text{sort}(R_i)$;
• no $A_i$ occur in any ${\delta }_{f_j}(R_j)$;
• the sorts of ${\delta }_{f_1}(R_1),\dots ,{\delta }_{f_k}(R_k)$ are pairwise disjoint;
• $F$ is a positive conjunctive selection formula.

For each SPJR query, there is an equivalent SPJR query in normal form.

Equivalence Theorem

• Lemma: The SPC and SPJR algebras are equivalent.
• Equivalence Theorem: The rule-based conjunctive queries, tableau queries, conjunctive calculus queries, satisifiable SPC algebra, and satisifiable SPJR algebra are all equivalent.

Adding Union

The following have equivalent expressive power:

• the nonrecursive datalog programs (with single relation target)
• the SPCU queries
• the SPJRU queries
  • union can only be applied to expressions having the same sort

Nonrecursive Datalog Program

A nonrecursive datalog program (nr-datalog program) over schema $\text{R}$ is a set of rules:

$$\begin{array}{rl}{S}_1& \leftarrow {\text{body}}_1\\ S_2& \leftarrow {\text{body}}_2\\ & ⋮\\ S_m& \leftarrow {\text{body}}_m\end{array}$$

where

• no relation name in $\text{R}$ occurs in a rule head
• the same relation name may appear in more than one rule head
• there is some ordering $r_1,\dots ,r_m$ of the rules such that the relation name in the head of $r_i$ does not occur in the body of any rule $r_j$ with $j\le i$

Union and the Conjunctive Calculus

Simply permitting disjunction (denoted $\vee$) in the formula of a conjunctive calculus along with conjunction can have serious consequences.

E.g.,

$$q=\{x,y,z|R(x,y)\vee R(y,z)\}$$

The answer of $q$ on nonempty instance $I$ will be

$$q(I)=(I\times \text{dom})\cup (\text{dom}\times I)$$

Because $R(x,y)$ decides that the first two components in $⟨x,y,z⟩$ are in $I$ and $z$ can be anything in $\text{dom}$, and $R(y,z)$ decides that the last two components in $⟨x,y,z⟩$ are in $I$ and $x$ can be anything in $\text{dom}$.