# CodeQL
CodeQL là một công cụ phân tích mã nguồn tự động, được sử dụng để tìm kiếm lỗ hổng bảo mật trong phần mềm.

- Tự động phân tích mã nguồn

- Phát hiện lỗ hổng bảo mật

- Kiểm tra ứng dụng đã triển khai

- Tùy chỉnh truy vấn bảo mật:

- Tích hợp với công cụ khác

## About the QL language
**Tổng quan về QL**
QL là một ngôn ngữ truy vấn mạnh mẽ, nền tảng cho CodeQL, được sử dụng để phân tích mã nguồn.

**Về ngôn ngữ truy vấn và cơ sở dữ liệu**
QL là một ngôn ngữ truy vấn khai báo và hướng đối tượng, được tối ưu hóa để phân tích các cấu trúc dữ liệu dạng cây (hierarchical data structures), đặc biệt là các cơ sở dữ liệu đại diện cho các thành phần của phần mềm.

**Cơ sở dữ liệu**: Một tập hợp dữ liệu có tổ chức. SQL (Structured Query Language) là ngôn ngữ truy vấn phổ biến nhất cho cơ sở dữ liệu quan hệ.

**Ngôn ngữ truy vấn**: Cung cấp nền tảng để đặt câu hỏi về dữ liệu lưu trữ trong cơ sở dữ liệu.
Các câu truy vấn thường tham chiếu đến các thực thể trong cơ sở dữ liệu và chỉ định các điều kiện (gọi là predicates) mà kết quả cần thỏa mãn.

**Các đặc điểm của một ngôn ngữ truy vấn tốt:**
**Khai báo (Declarative)**: Chỉ mô tả các thuộc tính mà kết quả cần thỏa mãn, không cung cấp quy trình tính toán cụ thể. Điều này giúp đơn giản hóa việc viết truy vấn.
**Biểu đạt mạnh mẽ (Expressiveness)**: Cho phép viết các truy vấn phức tạp, giúp áp dụng được cho nhiều trường hợp.
**Thực thi hiệu quả (Efficient execution)**: Xử lý nhanh các truy vấn phức tạp trên cơ sở dữ liệu lớn.

**Đặc điểm của QL**:
Cú pháp của QL tương tự SQL nhưng dựa trên Datalog, một ngôn ngữ lập trình logic khai báo.
QL là một ngôn ngữ logic, trong đó mọi thao tác đều là các phép toán logic.
QL hỗ trợ các **predicates** đệ quy (recursive predicates) từ Datalog và bổ sung thêm các hàm tổng hợp (aggregates) để viết truy vấn phức tạp một cách đơn giản.

**Ví dụ minh họa**: Một cơ sở dữ liệu chứa mối quan hệ cha-con. Để tìm số lượng hậu duệ của một người, ta thực hiện:

Tìm một hậu duệ của người đó (là con hoặc hậu duệ của con).
Đếm số hậu duệ từ bước trên.

Person getADescendant(Person p) {
  result = p.getAChild() or
  result = getADescendant(p.getAChild())
}

int getNumberOfDescendants(Person p) {
  result = count(getADescendant(p))
}

**Phân tích:**

Hàm getADescendant:
Sử dụng đệ quy để tìm tất cả các hậu duệ của p.
p.getAChild() trả về một người con trực tiếp của p.
Đệ quy kiểm tra các hậu duệ của con của p.
Hàm getNumberOfDescendants:
Sử dụng hàm tổng hợp count để đếm số lượng hậu duệ của p.

**QL và hướng đối tượng**:
QL hỗ trợ hướng đối tượng, cho phép:

Tăng tính mô đun hóa (modularity).
Che giấu thông tin (information hiding).
Tái sử dụng mã nguồn (code reuse).

Trong QL:

Lớp (class) được mô hình hóa như các predicates.
Kế thừa (inheritance) được mô hình hóa như các implication (phép kéo theo).

So sánh QL với các ngôn ngữ lập trình thông dụng:

QL không có tính chất mệnh lệnh (imperative) như gán biến hoặc thao tác hệ thống tệp.
QL hoạt động trên tập các tuples, giúp tự nhiên trong việc xử lý tập hợp giá trị.
Trong các ngôn ngữ hướng đối tượng, tạo đối tượng bằng cách cấp phát bộ nhớ để lưu trạng thái. Trong QL, các lớp chỉ là các thuộc tính logic mô tả tập giá trị đã tồn tại.

## Predicates
**Predicates là gì?**
Predicates mô tả các quan hệ logic trong chương trình QL và đánh giá ra tập hợp các tuples.
Mỗi predicate có arity (độ dài của tuple) là số lượng phần tử trong các tuple.

**Định nghĩa Predicate:**
Khi định nghĩa một predicate, cần xác định:
Loại Predicate:
Không có kết quả: Sử dụng từ khóa predicate.
Có kết quả: Loại trả về thay thế cho từ khóa predicate, với biến đặc biệt result.
Tên Predicate: Bắt đầu bằng chữ cái thường.
Tham số (nếu có): Xác định loại dữ liệu và tên biến.
Logic Body: Công thức logic trong cặp ngoặc {}.

**Ví dụ:**

- Predicate không có kết quả:
predicate isSmall(int i) {
i in [1 .. 9]
}
Predicate này kiểm tra xem i có phải là số nguyên dương nhỏ hơn 10 hay không.

- Predicate có kết quả:
int getSuccessor(int i) {
result = i + 1 and i in [1 .. 9]
}
Trả về số kế tiếp của i nếu i là số nguyên từ 1 đến 9.

**Các loại Predicate**:
Non-member predicates: Định nghĩa bên ngoài lớp, không thuộc về bất kỳ lớp nào.
Characteristic predicates: Xác định các thuộc tính đặc trưng của một lớp.
Member predicates: Định nghĩa trong lớp, hoạt động như phương thức của lớp.

class FavoriteNumbers extends int {
  FavoriteNumbers() { // Characteristic predicate
    this = 1 or this = 4 or this = 9
  }

  string getName() { // Member predicate
    this = 1 and result = "one"
    or this = 4 and result = "four"
    or this = 9 and result = "nine"
  }
}

**Recursive Predicates**:
Cho phép predicate gọi lại chính nó để giải quyết các bài toán phức tạp hơn.
Ví dụ: Mở rộng mối quan hệ hàng xóm sao cho quan hệ này đối xứng:

`string getANeighbor(string country) {
country = "France" and result = "Belgium"
or country = "France" and result = "Germany"
or country = getANeighbor(result)
}
`
**Binding Behavior**
Mọi predicate cần đảm bảo khả năng đánh giá trong thời gian hữu hạn.
Binding sets được sử dụng để ràng buộc phạm vi giá trị đầu vào.
Ví dụ:

bindingset[i]
    int multiplyBy4(int i) {
      result = i * 4
    }

    from int i
    where i in [1 .. 10]
    select multiplyBy4(i)

Predicates trong Cơ sở Dữ liệu:
Database predicates tương ứng với các bảng trong cơ sở dữ liệu.
Bạn không thể định nghĩa database predicates trong QL, chúng được xác định bởi cơ sở dữ liệu.

Ví dụ:
// Bảng "persons" trong cơ sở dữ liệu:
persons(x, firstName, _, age)

## Queries

Queries là đầu ra của một chương trình QL, và chúng trả về các tập hợp kết quả.

**Có 2 loại queries:**

**Select clause**: Được định nghĩa trong module hiện tại.
**Query predicates**: Predicate có gắn nhãn query để biểu diễn các tập hợp tuple.

**Cấu trúc của Select Clause:**

from /* ... biến khai báo ... */
where /* ... công thức logic ... */
select /* ... biểu thức ... */

from: Khai báo biến (tùy chọn).
where: Điều kiện lọc logic (tùy chọn).
select: Biểu thức để xuất kết quả.

Các từ khóa bổ sung:
as: Gán nhãn cho cột trong kết quả.
order by: Sắp xếp kết quả theo cột chỉ định (asc hoặc desc).

from int x, int y
where x = 3 and y in [0 .. 2]
select x, y, x * y as product, "product: " + product

Kết quả đầu ra:
x y product product string
3 0 0 product: 0
3 1 3 product: 3
3 2 6 product: 6

Nếu thêm order by y desc:
x y product product string
3 2 6 product: 6
3 1 3 product: 3
3 0 0 product: 0

**Query Predicates:**
Là các predicate không phải thành viên, có annotation query.
Trả về các tuple mà predicate đánh giá đúng.

query int getProduct(int x, int y) {
  x = 3 and
  y in [0 .. 2] and
  result = x * y
}

x y result
3 0 0
3 1 3
3 2 6

**Ưu điểm của Query Predicate:**
Có thể gọi trong các phần khác của code (tái sử dụng).
Hỗ trợ gỡ lỗi vì bạn có thể xem trực tiếp tập hợp tuple.

Ví dụ sử dụng Query Predicate trong class:
class MultipleOfThree extends int {
MultipleOfThree() { this = getProduct(_, _) }
}
Ở đây, MultipleOfThree mở rộng kiểu int và nhận các giá trị từ getProduct.


## Types

QL (Query Language) là một ngôn ngữ có kiểu tĩnh, nghĩa là mỗi biến phải được khai báo kiểu dữ liệu rõ ràng.

**Một số khái niệm cơ bản:**
Kiểu dữ liệu là tập hợp các giá trị. Ví dụ: int là tập hợp các số nguyên.
Một giá trị có thể thuộc về nhiều kiểu dữ liệu khác nhau, tức là nó có thể có nhiều kiểu.

**QL hỗ trợ các loại kiểu dữ liệu chính sau:**

Kiểu nguyên thủy (Primitive types).
Lớp (Classes).
Kiểu ký tự (Character types).
Kiểu miền lớp (Class domain types).
Kiểu đại số (Algebraic datatypes).
Hợp kiểu (Type unions).
Kiểu cơ sở dữ liệu (Database types).

**Kiểu nguyên thủy**

Các kiểu nguyên thủy được tích hợp sẵn và luôn khả dụng trong không gian tên toàn cục, không phụ thuộc vào cơ sở dữ liệu.

boolean: Chứa các giá trị true và false.
float: Chứa số thực 64-bit, ví dụ: 6.28, -0.618.
int: Chứa số nguyên 32-bit hai bù, ví dụ: -1, 42.
string: Chứa chuỗi ký tự 16-bit có độ dài hữu hạn.
date: Chứa ngày (và thời gian nếu có).

1.toString() // Trả về chuỗi "1"
Với QlBuiltins::BigInt, bạn có thể sử dụng kiểu số nguyên phạm vi tùy ý.

**Lớp (Classes)**

Lớp là cách định nghĩa kiểu dữ liệu riêng trong QL, giúp cấu trúc và tái sử dụng mã nguồn hiệu quả.

class <TênLớp> extends <Supertypes> {
  <NộiDung>
}

class OneTwoThree extends int {
  OneTwoThree() {
    this = 1 or this = 2 or this = 3
  }

  string getAString() {
    result = "One, two or three: " + this.toString()
  }

  predicate isEven() {
    this = 2
  }
}

Lớp OneTwoThree kế thừa từ int, chứa các giá trị 1, 2, 3.
Characteristic predicate: Mô tả logic đặc trưng, ví dụ: this = 1 or this = 2 or this = 3.
Member predicate: Định nghĩa hành vi riêng cho lớp, ví dụ: getAString trả về chuỗi dạng "One, two or three: n".

**Cụ thể hóa các khái niệm**
Characteristic predicates

Được định nghĩa bên trong lớp.
Dùng biến this để giới hạn giá trị của lớp.

Member predicates

Chỉ áp dụng cho các thành viên của một lớp.
Cho phép sử dụng như một phương thức.
Ví dụ:
1.(OneTwoThree).getAString() // Trả về "One, two or three: 1"
Có thể nối chuỗi với các phương thức khác:
1.(OneTwoThree).getAString().toUpperCase() // Trả về "ONE, TWO OR THREE: 1"

**Fields (Trường)**

Là các biến được khai báo bên trong lớp.
Được sử dụng trong các định nghĩa logic của lớp.

class DivisibleInt extends SmallInt {
  SmallInt divisor; // Trường `divisor`
  DivisibleInt() { this % divisor = 0 }

  SmallInt getADivisor() { result = divisor }
}

Trường divisor phải được giới hạn trong characteristic predicate.
Có thể truy xuất trường trong các member predicates.

**Các loại lớp**
Lớp cụ thể (Concrete classes)
Giá trị của lớp cụ thể là giao của các kiểu cha (supertypes) và thỏa mãn characteristic predicate.

Lớp trừu tượng (Abstract classes)
Được định nghĩa bởi hợp các lớp con.
`abstract class SqlExpr extends Expr { ... }`
Lớp SqlExpr đại diện cho tất cả các biểu thức SQL, có thể mở rộng cho các hệ quản trị khác nhau như PostgresSqlExpr, MySqlExpr.

**Tính kế thừa**:
Ghi đè Member predicates

Có thể ghi đè member predicates của kiểu cha bằng từ khóa override.

class OneTwo extends OneTwoThree {
  override string getAString() {
    result = "One or two: " + this.toString()
  }
}

Kết quả:
1 -> "One or two: 1"
2 -> "One or two: 2"
3 -> "One, two or three: 3"

Kế thừa nhiều lớp
Một lớp có thể kế thừa nhiều kiểu cha.

class Two extends OneTwo, TwoThree {}

Mở rộng cuối cùng (Final extensions)

Khi kế thừa từ các kiểu final, các member predicates không thể bị ghi đè.
Nếu một lớp được đánh dấu là final, bạn không thể kế thừa lớp đó. Tức là, lớp final không thể được sử dụng làm lớp cơ sở.

## Modules

Modules trong QL cung cấp cách tổ chức mã nguồn theo các nhóm có liên quan như kiểu, predicate, và các module khác.
Chúng giúp tránh lặp lại mã và cấu trúc hệ thống dễ quản lý hơn.

**Định nghĩa module:**
Module có thể được định nghĩa bằng cách:

Sử dụng từ khóa module để khai báo module rõ ràng.
Sử dụng tệp .ql hoặc .qll để định nghĩa module ngầm định.

module Example {
  class OneTwoThree extends int {
    OneTwoThree() {
      this = 1 or this = 2 or this = 3
    }
  }
}

**Các loại module:**
File Modules:
Được định nghĩa ngầm trong tệp .ql hoặc .qll.
Tên module tương ứng với tên tệp.

Library Modules:
Được định nghĩa trong các tệp .qll.
Các module thư viện chứa các phần tử tái sử dụng, không bao gồm select.

Tệp OneTwoThreeLib.qll định nghĩa module thư viện:

class OneTwoThree extends int {
  OneTwoThree() {
    this = 1 or this = 2 or this = 3
  }
}

Query Modules:
Được định nghĩa trong tệp .ql và phải chứa ít nhất một truy vấn (select).
Không thể import query modules vào các file khác.

import OneTwoThreeLib

from OneTwoThree ott
where ott = 1 or ott = 2
select ott

**Module tường minh (Explicit Modules):**
Có thể định nghĩa module bên trong module khác bằng cách dùng từ khóa module.

module ParentModule {
  module ChildModule {
    class Sample extends int {
      Sample() { this = 5 }
    }
  }
}

**Module tham số (Parameterized Modules):**
Hỗ trợ lập trình tổng quát bằng cách truyền tham số khi khởi tạo module.
Module có tham số là các predicate:

module M<transformer/1 first, transformer/1 second> {
  int applyBoth(int x) {
    result = second(first(x))
  }
}

int increment(int x) { result = x + 1 }

module IncrementTwice = M<increment/1, increment/1>;

select IncrementTwice::applyBoth(40) // Kết quả: 42

**Import Modules:**
Để sử dụng module trong module khác, cần import bằng lệnh import.

import <module_name>
import <module_name> as <alias>

**import Example as Ex**
**Các module tích hợp (Built-in Modules):**
**EquivalenceRelation**:
Hỗ trợ định nghĩa quan hệ tương đương.
Quan hệ tương đương là một loại quan hệ đặc biệt giữa các phần tử thỏa mãn ba tính chất: phản xạ (reflexive), đối xứng (symmetric), và bắc cầu (transitive). Module này cung cấp các công cụ để nhóm các phần tử vào các lớp tương đương dựa trên quan hệ được định nghĩa.
Ví dụ:

module Equiv = QlBuiltins::EquivalenceRelation<Node, base/2>;

predicate base(Node x, Node y) { ... }

from int x, int y
where Equiv::getEquivalenceClass(x) = Equiv::getEquivalenceClass(y)
select x, y

Định nghĩa module:

module Equiv = QlBuiltins::EquivalenceRelation<Node, base/2>;
Module Equiv sử dụng quan hệ cơ bản base/2 để xác định cách các phần tử thuộc về cùng một lớp tương đương.
Node là kiểu dữ liệu của các phần tử được so sánh trong quan hệ tương đương.

Predicate base:

base(Node x, Node y) định nghĩa quan hệ cơ bản giữa hai phần tử x và y.
Ví dụ: Nếu base định nghĩa quan hệ "cùng nhóm", thì các phần tử trong cùng một nhóm thuộc cùng một lớp tương đương.

Sử dụng lớp tương đương:

Equiv::getEquivalenceClass(x) trả về lớp tương đương của phần tử x.
Câu truy vấn where Equiv::getEquivalenceClass(x) = Equiv::getEquivalenceClass(y) kiểm tra xem hai phần tử x và y có thuộc cùng một lớp tương đương hay không.

Kết quả:
Truy vấn sẽ chọn tất cả các cặp (x, y) mà x và y thuộc cùng một lớp tương đương.

**Built-in Module: InternSets:**
Chức năng:

InternSets hỗ trợ tạo tập hợp các giá trị liên quan theo một khóa cụ thể. Tập hợp này thường được dùng để tổ chức và truy vấn dữ liệu theo từng nhóm liên kết.

module Sets = QlBuiltins::InternSets<int, int, getAValue/1>;

from int k, int v
where Sets::getSet(k).contains(v)
select k, v

Định nghĩa module:

module Sets = QlBuiltins::InternSets<int, int, getAValue/1>;
Module Sets tạo các tập hợp dựa trên các cặp giá trị khóa (k) và giá trị (v).

Hàm getAValue/1:

Đây là hàm định nghĩa cách lấy giá trị v từ một khóa k.
Ví dụ: getAValue(k) trả về các giá trị liên quan đến khóa k.

Sử dụng tập hợp:

Sets::getSet(k) trả về tập hợp chứa tất cả các giá trị liên quan đến khóa k.
Sets::getSet(k).contains(v) kiểm tra xem giá trị v có nằm trong tập hợp của khóa k hay không.

Kết quả:

Truy vấn sẽ chọn tất cả các cặp (k, v) mà v là một phần tử trong tập hợp được ánh xạ từ k.

**Built-in Module: BigInt**:
Chức năng:

BigInt cung cấp khả năng làm việc với số nguyên lớn vượt quá phạm vi của kiểu số nguyên tiêu chuẩn (như int hoặc long). Module này hữu ích cho các tính toán cần độ chính xác cao hoặc xử lý số lớn.
Sử dụng:

BigInt hoạt động tương tự các kiểu số nguyên thông thường nhưng có khả năng lưu trữ và thao tác trên các giá trị lớn hơn nhiều.
Các phép toán như cộng, trừ, nhân, chia, hoặc so sánh đều được hỗ trợ trên kiểu BigInt.

Ứng dụng:

Xử lý các giá trị số lớn trong mật mã học, khoa học dữ liệu, hoặc các thuật toán yêu cầu độ chính xác cao.

## Signatures
Signatures (chữ ký) đóng vai trò như một hệ thống kiểu dữ liệu cho các tham số trong các module được tham số hóa.
Chúng định nghĩa cấu trúc và hành vi mong đợi cho các predicate, type, hoặc module được sử dụng khi khởi tạo một module.

**Predicate Signatures**
Định nghĩa:

Predicate signatures định nghĩa giao diện cho các predicate mà một module có thể chấp nhận làm tham số.

Việc thay thế một predicate signature dựa trên structural typing. Nghĩa là các predicate không cần phải được định nghĩa tường minh là một phần của predicate signature, miễn là chúng có kiểu trả về và tham số khớp với định nghĩa.

Cách định nghĩa:

Predicate signature được định nghĩa giống như predicate thông thường, nhưng không có thân hàm (body). Cấu trúc bao gồm:

Từ khóa signature.
Từ khóa predicate (cho phép sử dụng predicate không có kết quả trả về) hoặc kiểu trả về của predicate.
Tên predicate signature (bắt đầu bằng chữ thường).
Danh sách tham số (bao gồm kiểu dữ liệu và tên biến tham số).
Dấu ; kết thúc.

signature int operator(int lhs, int rhs);

**Type Signatures**
Định nghĩa:

Type signatures định nghĩa các tham số kiểu dữ liệu mà một module có thể chấp nhận.
Các kiểu này có thể được mở rộng từ các kiểu dữ liệu khác và cần có các predicate thành viên được chỉ định.

Việc thay thế một type signature dựa trên structural typing. Nghĩa là các kiểu dữ liệu không cần phải được định nghĩa tường minh là một phần của type signature, miễn là chúng thỏa mãn các kiểu siêu lớp (supertypes) và các predicate được yêu cầu.

Cách định nghĩa:

Type signature được định nghĩa như sau:

Từ khóa signature.
Từ khóa class.
Tên của type signature (bắt đầu bằng chữ hoa).
(Tùy chọn) Từ khóa extends và danh sách các kiểu siêu lớp.
Danh sách các predicate thành viên, hoặc kết thúc bằng dấu ;.

signature class ExtendsInt extends int;

signature class CanBePrinted {
  string toString();
}

ExtendsInt là một type signature mở rộng từ kiểu int.
CanBePrinted yêu cầu kiểu dữ liệu có thành viên toString() trả về string.

**Module Signatures**
Định nghĩa:

Module signatures định nghĩa giao diện cho các module được dùng làm tham số trong các module khác. Chúng chỉ định các type, predicate, hoặc module mà một module cần chứa, với tên và chữ ký tương ứng.

Không giống như type signatures và predicate signatures, việc thay thế module signatures dựa trên nominal typing. Nghĩa là một module phải tường minh khai báo rằng nó thực thi một module signature cụ thể.

Cách định nghĩa:

Từ khóa signature.
Từ khóa module.
Tên module signature (bắt đầu bằng chữ hoa).
(Tùy chọn) Danh sách tham số cho module signature được tham số hóa.
Nội dung module signature, bao gồm:
Các type signatures.
Các predicate signatures.
Các predicate mặc định.

signature module MSig {
  class T;
  predicate restriction(T t);
  default string descr(T t) { result = "default" }
}

module Module implements MSig {
  newtype T = A() or B();

  predicate restriction(T t) { t = A() }
}

Module signature MSig định nghĩa:

Một type T.
Một predicate restriction hoạt động trên kiểu T.
Một predicate mặc định descr trả về chuỗi "default".

Module Module thực thi MSig, với kiểu T và định nghĩa cụ thể cho restriction.

**Parameterized Module Signatures**

Module signatures có thể được tham số hóa, giống như các module thông thường.
Điều này đặc biệt hữu ích khi kết hợp với kiểu dữ liệu phụ thuộc (dependent typing) của tham số module.

signature class NodeSig;

signature module EdgeSig<NodeSig Node> {
  predicate apply(Node src, Node dst);
}

module Reachability<NodeSig Node, EdgeSig<Node> Edge> {
  Node reachableFrom(Node src) {
    Edge::apply+(src, result)
  }
}

NodeSig là một type signature định nghĩa kiểu Node.
EdgeSig là một module signature tham số hóa với NodeSig.
Module Reachability sử dụng NodeSig và EdgeSig làm tham số, và định nghĩa một hàm reachableFrom dựa trên predicate apply từ EdgeSig.

**Aliases**
Alias (bí danh) là một tên thay thế cho một thực thể QL hiện có.
Sau khi định nghĩa bí danh, bạn có thể sử dụng tên mới này để tham chiếu đến thực thể trong phạm vi không gian tên của module hiện tại.

**Cách định nghĩa alias**

Bạn có thể định nghĩa alias trong thân của bất kỳ module nào. Cách thực hiện:

Từ khóa: Sử dụng module, class, hoặc predicate để định nghĩa alias tương ứng cho module, type, hoặc predicate không phải thành viên.
Tên alias: Tên này phải hợp lệ cho loại thực thể được alias. Ví dụ: Tên alias của một predicate phải bắt đầu bằng chữ thường.
Tham chiếu: Chỉ định thực thể QL gốc, bao gồm tên gốc của thực thể và, với predicate, bao gồm cả arity (số lượng tham số).

Bạn cũng có thể thêm annotation vào alias. Lưu ý rằng các annotation này áp dụng cho tên alias được tạo, chứ không phải thực thể QL gốc.

Aliases (Bí danh)

Alias (bí danh) là một tên thay thế cho một thực thể QL hiện có. Sau khi định nghĩa bí danh, bạn có thể sử dụng tên mới này để tham chiếu đến thực thể trong phạm vi không gian tên của module hiện tại.
Cách định nghĩa alias

Bạn có thể định nghĩa alias trong thân của bất kỳ module nào. Cách thực hiện:

Từ khóa: Sử dụng module, class, hoặc predicate để định nghĩa alias tương ứng cho module, type, hoặc predicate không phải thành viên.
Tên alias: Tên này phải hợp lệ cho loại thực thể được alias. Ví dụ: Tên alias của một predicate phải bắt đầu bằng chữ thường.
Tham chiếu: Chỉ định thực thể QL gốc, bao gồm tên gốc của thực thể và, với predicate, bao gồm cả arity (số lượng tham số).

Bạn cũng có thể thêm annotation vào alias. Lưu ý rằng các annotation này áp dụng cho tên alias được tạo, chứ không phải thực thể QL gốc.

**Alias cho module**

Sử dụng cú pháp sau để định nghĩa alias cho một module:

module ModAlias = ModuleName;

Ví dụ:

Nếu bạn tạo một module mới NewVersion để cập nhật OldVersion, bạn có thể làm cho tên OldVersion bị lỗi thời như sau:

deprecated module OldVersion = NewVersion;

Khi đó, cả hai tên sẽ tham chiếu đến cùng một module, nhưng việc sử dụng OldVersion sẽ hiển thị cảnh báo.

**Alias cho type**
Sử dụng cú pháp sau để định nghĩa alias cho một type:

class TypeAlias = TypeName;

Lưu ý:

Từ khóa class là bắt buộc, nhưng bạn có thể tạo alias cho bất kỳ kiểu dữ liệu nào (primitive, database type, hoặc user-defined class).
Ví dụ:
Rút gọn tên kiểu nguyên thủy boolean thành Bool:
class Bool = boolean;
Sử dụng một kiểu được định nghĩa trong một module khác:

import OneTwoThreeLib

class OT = M::OneTwo;
...
from OT ot
select ot

Alias cho predicate

Sử dụng cú pháp sau để định nghĩa alias cho một predicate không phải thành viên:

predicate PredAlias = PredicateName/Arity;

Cú pháp này hoạt động với predicate có hoặc không có kết quả trả về.
Có trả về:

int getSuccessor(int i) {
  result = i + 1 and
  i in [1 .. 9]
}

predicate succ = getSuccessor/1;

Không trả về:

predicate isSmall(int i) {
  i in [1 .. 9]
}

predicate lessThanTen = isSmall/1;

**Strong alias và Weak alias**

Mỗi alias định nghĩa sẽ thuộc một trong hai loại: strong hoặc weak.

Strong alias:
Chỉ có thể được định nghĩa với annotation final trong alias cho type.
Không cho phép sự mơ hồ giữa các strong alias khác nhau cho cùng một module/type/predicate.

Weak alias:
Cho phép sự mơ hồ giữa các weak alias khác nhau.
Trong trường hợp instantiation (khởi tạo) của các module tham số hóa, weak alias không tạo ra các instance riêng biệt, nhưng strong alias sẽ làm điều đó.

Strong Alias:

final class MyAlias = SomeType;

Weak Alias:

class MyAlias = SomeType;

=> Strong Alias: Không cho phép mơ hồ, phải dùng với từ khóa final. Mỗi strong alias tạo ra một instance riêng biệt khi khởi tạo module tham số hóa, dễ quản lý và duy trì trong các hệ thống phức tạp khi cần phân biệt rõ ràng các thực thể.
Weak Alias: Cho phép mơ hồ giữa các alias khác nhau. Không tạo instance riêng biệt khi khởi tạo module tham số hóa.
Dùng strong alias khi cần quản lý rõ ràng và độc lập.
Dùng weak alias khi muốn đơn giản hóa và tối ưu hiệu suất, giảm rủi ro lỗi khi nhiều module hoặc type tham chiếu cùng một thực thể.
## Variables
Biến trong QL được sử dụng tương tự như biến trong đại số hoặc logic. Chúng đại diện cho tập giá trị và các giá trị này thường bị giới hạn bởi một công thức.
Điều này khác với biến trong một số ngôn ngữ lập trình khác, nơi biến là đại diện cho vị trí bộ nhớ, và giá trị của nó có thể thay đổi theo thời gian.

Ví dụ:

Trong QL, n = n + 1 là một công thức đẳng thức và chỉ đúng khi n bằng n + 1 (điều này không xảy ra với bất kỳ giá trị số nào).
Trong Java, n = n + 1 là một lệnh gán, thay đổi giá trị của n bằng cách thêm 1 vào giá trị hiện tại.

**Khai báo biến (Declaring a variable)**

Tất cả các khai báo biến bao gồm:

Kiểu dữ liệu: xác định kiểu giá trị mà biến có thể lưu trữ (ví dụ: int, string).
Tên biến: bất kỳ định danh hợp lệ nào bắt đầu bằng chữ thường.

`int i, SsaDefinitionNode node, LocalScopeVariable lsv;`

Các biến i, node, và lsv lần lượt có kiểu int, SsaDefinitionNode, và LocalScopeVariable.

Khai báo biến có thể xuất hiện trong nhiều ngữ cảnh:

Trong câu lệnh select.
Bên trong một công thức định lượng (quantified formula).
Là tham số của một predicate.

**Khái niệm về biến**
Biến trong QL có thể hiểu như tập giá trị mà kiểu của nó cho phép, nhưng giá trị này có thể bị giới hạn bởi các ràng buộc thêm.

from int i
where i in [0 .. 9]
select i

Câu lệnh select dưới đây:
Biến i có kiểu int, nghĩa là nó có thể chứa tất cả các số nguyên.
Công thức i in [0 .. 9] giới hạn giá trị của i chỉ trong khoảng từ 0 đến 9.
Kết quả: 10 số nguyên từ 0 đến 9.

Nếu không có ràng buộc, như:

from int i
select i

Câu lệnh này sẽ gây lỗi biên dịch vì biến i không bị giới hạn, dẫn đến kết quả vô hạn.

**Biến tự do và bị ràng buộc (Free and Bound Variables)**

Biến tự do (Free Variable): Giá trị của biến ảnh hưởng trực tiếp đến giá trị của biểu thức hoặc tính đúng sai của công thức.
Biến bị ràng buộc (Bound Variable): Giá trị của biến bị giới hạn trong một tập hợp cụ thể và không thể thay đổi bởi người dùng.

Biến không có:

"hello".indexOf("l")

Tìm vị trí của "l" trong "hello".
Kết quả: 2 và 3 (dựa trên chỉ số bắt đầu từ 0).

Biến bị ràng buộc:

min(float f | f in [-3 .. 3])

Tìm giá trị nhỏ nhất trong khoảng [-3 .. 3].
Kết quả: -3.
Biến f chỉ là một placeholder và không ảnh hưởng đến kết quả.

Biến tự do:

(i + 7) * 3

Giá trị của biểu thức phụ thuộc vào giá trị của i.
So sánh thêm:
Công thức với biến tự do:
`(i + 7) * 3 instanceof int`

Công thức với biến bị ràng buộc:
`min(float f | f in [-3 .. 3]) = -3`

## Expressions

Biểu thức (Expressions):
Một biểu thức sẽ được tính toán để trả về một tập hợp giá trị và có một kiểu dữ liệu (type).
Ví dụ: Biểu thức 1 + 2 tính ra giá trị là 3 và có kiểu int, trong khi biểu thức "QL" có giá trị là chuỗi "QL" và kiểu string.

**1. Biểu thức (Expressions):**
Một biểu thức sẽ được tính toán để trả về một tập hợp giá trị và có một kiểu dữ liệu (type). Ví dụ: Biểu thức 1 + 2 tính ra giá trị là 3 và có kiểu int, trong khi biểu thức "QL" có giá trị là chuỗi "QL" và kiểu string.

**2. Tham chiếu biến (Variable References):**
Tham chiếu biến là tên của một biến đã được khai báo. Loại của biểu thức này giống với loại của biến mà nó tham chiếu đến. Ví dụ:
Nếu bạn khai báo một biến int i và một biến LocalScopeVariable lsv, thì biểu thức i có kiểu int và lsv có kiểu LocalScopeVariable.

**3. Hằng số (Literals):**
Các giá trị hằng số có thể được biểu diễn trực tiếp trong QL:
Hằng số boolean: true và false.
Hằng số số nguyên: Các dãy chữ số thập phân như 42 hoặc -2048.
Hằng số số thực: Ví dụ 2.0, 123.456.
Hằng số chuỗi: Các chuỗi ký tự được bao trong dấu ngoặc kép ("..."). Ví dụ: "hello" hoặc "They said, \"Please escape quotation marks!\"".
Lưu ý: Không có hằng số ngày tháng trong QL, nhưng bạn có thể chuyển đổi chuỗi thành ngày bằng cách sử dụng hàm toDate().

**4. Biểu thức trong dấu ngoặc (Parenthesized Expressions):**
Một biểu thức có thể được bao quanh bởi dấu ngoặc đơn ( ). Điều này giúp nhóm các biểu thức lại với nhau, làm cho mã dễ hiểu hơn.

**5. Khoảng giá trị (Ranges):**
Biểu thức phạm vi cho phép bạn chỉ định một phạm vi giá trị giữa hai biểu thức, ví dụ [3 .. 7] đại diện cho các số nguyên từ 3 đến 7 (bao gồm cả 3 và 7).

**6. Biểu thức hằng số tập hợp (Set Literals):**
Một biểu thức tập hợp cho phép bạn liệt kê một tập hợp các giá trị, ví dụ [2, 3, 5, 7]. Các phần tử trong tập hợp phải có kiểu dữ liệu tương thích.

**7. Biểu thức super (Super Expressions):**
Biểu thức super trong QL dùng để tham chiếu đến một định nghĩa của hàm trong lớp cha (superclass). Điều này hữu ích khi một lớp kế thừa nhiều định nghĩa hàm từ các lớp cha và bạn muốn gọi một hàm từ lớp cha mà không phải ghi đè lại.

**8. Lời gọi hàm (Calls to predicates):**
Lời gọi hàm có kết quả (predicate with result) là một biểu thức trả về giá trị của biến result trong hàm gọi. Ví dụ: a.getAChild() sẽ trả về tập hợp con của a.

**9. Tổng hợp (Aggregations):**
Tổng hợp là phép toán tính toán một giá trị kết quả từ tập hợp các giá trị đầu vào được chỉ định bởi một công thức.
Có các hàm tổng hợp như count (đếm), min (giá trị nhỏ nhất), max (giá trị lớn nhất), avg (trung bình), và sum (tổng).
Các hàm tổng hợp có thể có tham số bổ sung để xác định cách sắp xếp kết quả, chẳng hạn như sắp xếp theo tên đối tượng (order by).

**10. Các phép toán Monotonic (Monotonic aggregates):**
Các phép toán monotonic khác với các phép toán tổng hợp thông thường vì chúng xử lý giá trị của biểu thức khác nhau. Nếu có nhiều hơn một giá trị cho mỗi kết quả, hàm tổng hợp monotonic sẽ áp dụng với từng sự kết hợp giá trị.

**Tổng kết:**
Các biểu thức trong QL được chia thành nhiều loại như tham chiếu biến, hằng số, biểu thức phạm vi, biểu thức tập hợp và gọi hàm. Các phép toán tổng hợp và monotonic giúp xử lý và tính toán giá trị từ các tập hợp giá trị đầu vào một cách linh hoạt.

Tổng hợp đơn điệu (Monotonic Aggregates)
Tổng hợp đơn điệu là một loại tổng hợp đặc biệt, nơi kết quả của phép tổng hợp không thay đổi hoặc không "rút lui" khi dữ liệu được cập nhật. Những tổng hợp này thường được sử dụng khi bạn muốn truy vấn xử lý cập nhật dữ liệu một cách dự đoán được.

string getPerson() { result = "Alice" or
                     result = "Bob" or
                     result = "Charles" or
                     result = "Diane"
                   }
string getFruit(string p) { p = "Alice"   and result = "Orange" or
                            p = "Alice"   and result = "Apple" or
                            p = "Bob"     and result = "Apple" or
                            p = "Charles" and result = "Apple" or
                            p = "Charles" and result = "Banana"
                          }
int getPrice(string f) { f = "Apple"  and result = 100 or
                         f = "Orange" and result = 100 or
                         f = "Orange" and result =   1
                       }

predicate nonmono(string p, int cost) {
  p = getPerson() and cost = sum(string f | f = getFruit(p) | getPrice(f))
}

language[monotonicAggregates]
predicate mono(string p, int cost) {
  p = getPerson() and cost = sum(string f | f = getFruit(p) | getPrice(f))
}

from string variant, string person, int cost
where variant = "default"  and nonmono(person, cost) or
      variant = "monotonic" and mono(person, cost)
select variant, person, cost
order by variant, person


Trong ví dụ của bạn:

getPerson() trả về danh sách các người: Alice, Bob, Charles, Diane.
getFruit(p) trả về các loại trái cây dựa trên người (p).
getPrice(f) trả về giá của một loại trái cây (f).
Hai loại tổng hợp:
Tổng hợp mặc định (non-monotonic): Loại tổng hợp này cho phép nhiều kết quả và kết hợp chúng lại thành một kết quả duy nhất. Trong ví dụ này, nếu Alice mua nhiều loại trái cây với giá khác nhau (ví dụ: cam với giá 100 và

1), kết quả sẽ là tổng hợp của các giá này (ví dụ: 100 + 1 + 100 = 201).
Tổng hợp đơn điệu (monotonic): Loại tổng hợp này xử lý các tình huống khi nhiều kết quả cần tạo ra nhiều dòng kết quả trong output. Với Alice, điều này có nghĩa là có nhiều dòng dữ liệu cho mỗi cách cô ấy có thể mua hàng.
2. Cách hoạt động của Tổng hợp đơn điệu:
Khi Alice mua một quả cam và một quả táo, nếu có hai giá khác nhau cho quả cam (100 và 1), trong tổng hợp mặc định sẽ có một dòng dữ liệu duy nhất, nhưng với tổng hợp đơn điệu, sẽ có một dòng dữ liệu cho mỗi cách cô ấy có thể mua cam và táo (một dòng cho giá cam là 100 và một dòng cho giá cam là 1).

Với Charles, vì anh ta muốn mua một quả chuối mà không có giá bán (không có chuối trong cửa hàng), trong tổng hợp mặc định, anh ta vẫn có thể mua táo, và sẽ có dòng dữ liệu với tổng giá của táo. Tuy nhiên, với tổng hợp đơn điệu, sẽ không có dòng dữ liệu cho Charles vì không có chuối để bán.

Diane không mua gì cả, và trong cả hai kiểu tổng hợp, cô ấy đều có tổng chi phí là 0. Tuy nhiên, tổng hợp kiểu strictsum sẽ không bao gồm cô ấy trong kết quả nếu không có gì để cộng dồn.

3. Lý do sử dụng Tổng hợp đơn điệu:
Mặc dù trường hợp có nhiều dòng kết quả như với Alice không phải là phổ biến, trường hợp của Charles quan trọng hơn. Nếu sau này chúng ta biết được giá của chuối, chúng ta sẽ không cần phải xóa bất kỳ dòng kết quả nào đã được tạo ra trước đó. Điều này rất quan trọng khi làm việc với các phép tổng hợp đơn điệu, vì chúng phù hợp với những lý thuyết tính toán đệ quy (recursive semantics).

4. Tổng hợp đệ quy đơn điệu (Recursive Monotonic Aggregates):
Tổng hợp đơn điệu có thể được sử dụng trong các tình huống đệ quy, nhưng việc gọi đệ quy chỉ được phép xuất hiện trong biểu thức, không được xuất hiện trong phạm vi (range). Ví dụ:

Trong một đồ thị, để tính độ sâu của một node từ các lá cây, bạn có thể sử dụng phép tổng hợp đơn điệu đệ quy. Cụ thể, nếu một node không có con (no children), độ sâu của nó là 0. Nếu có con, độ sâu của nó là 1 cộng với độ sâu của các con của nó.

language[monotonicAggregates]
int depth(Node n) {
  if not exists(n.getAChild())
  then result = 0
  else result = 1 + max(Node child | child = n.getAChild() | depth(child))
}


Ví dụ về đồ thị:
Nếu bạn có đồ thị với các nút và các mối quan hệ (mũi tên từ con đến cha), quá trình tính độ sâu của các nút diễn ra qua các giai đoạn:

Giai đoạn 1: Các nút không có con sẽ có độ sâu là 0.
Giai đoạn 2: Các nút có con sẽ tính độ sâu của các con của mình. Ví dụ, nếu nút c có độ sâu là 1 vì các con của nó đã có độ sâu, thì nút a có thể tính độ sâu vì nó đã biết độ sâu của các con.
Giai đoạn 3: Quá trình này tiếp tục cho đến khi tất cả các nút có độ sâu hoàn chỉnh.
Điều quan trọng ở đây là nếu một nút không có giá trị độ sâu cho con của nó, thì không thể tính độ sâu cho nó, điều này giúp tránh kết quả sai.

5. Các phép toán và Biểu thức khác trong QL:

any(<variable declarations> | <formula> | <expression>)


Biểu thức any: Dùng để truy vấn tất cả giá trị thỏa mãn một điều kiện nhất định. Ví dụ:
any(File f) sẽ lấy tất cả các file trong cơ sở dữ liệu.
any(Element e | e.getName()) sẽ lấy tên của tất cả các phần tử trong cơ sở dữ liệu.
Phép toán đơn (Unary) và phép toán nhị phân (Binary): Các phép toán như cộng, trừ, nhân, chia, modulo, hay nối chuỗi có thể được sử dụng trong các biểu thức.
6. Biến không quan tâm (_):

from string s
where s = "hello".charAt(_)
select s

Biến không quan tâm được biểu thị bằng dấu gạch dưới (_). Nó đại diện cho bất kỳ giá trị nào mà không quan tâm đến giá trị cụ thể đó. Ví dụ:

s = "hello".charAt(_) sẽ trả về tất cả các ký tự trong chuỗi "hello" (h, e, l, l, o).
Kết luận:
Các khái niệm trong ví dụ chủ yếu liên quan đến cách tính toán tổng hợp trong các truy vấn dữ liệu, đặc biệt là sự khác biệt giữa tổng hợp đơn điệu và không đơn điệu, cách thức xử lý khi có cập nhật dữ liệu hoặc khi có các phép tính đệ quy. Monotonic aggregates có thể hữu ích khi bạn cần một cách xử lý ổn định và có thể mở rộng khi dữ liệu thay đổi.

## Formulas
Công thức là các biểu thức định nghĩa mối quan hệ logic giữa các biến tự do. Các biến này có thể nhận các giá trị khác nhau và công thức có thể đúng hoặc sai tùy vào những giá trị được gán cho các biến đó.

Ví dụ:
Công thức x = 4 + 5 sẽ đúng nếu x = 9, nhưng sẽ sai nếu x nhận giá trị khác.
Một số công thức không có biến tự do như 1 < 2 (luôn đúng) hoặc 1 > 2 (luôn sai).

**So sánh (Comparisons)**
Công thức so sánh dùng để so sánh giá trị của hai biểu thức và xác định mối quan hệ giữa chúng. Các toán tử so sánh bao gồm:

Lớn hơn, nhỏ hơn:
x > y: Kiểm tra nếu x lớn hơn y.
x <= y: Kiểm tra nếu x nhỏ hơn hoặc bằng y.
Bằng nhau, khác nhau:
x = y: Kiểm tra nếu x bằng y.
x != y: Kiểm tra nếu x khác y.

x = 5 + 6; // công thức này sẽ đúng nếu x = 11
x != 4; // công thức này sẽ đúng nếu x không bằng 4

Trong ví dụ trên, công thức x = 5 + 6 chỉ đúng khi giá trị của x là 11, còn x != 4 đúng khi x không bằng 4.

**Kiểm tra kiểu dữ liệu (Type checks)**
Kiểm tra kiểu dữ liệu xác định xem một biểu thức có phải là đối tượng của một kiểu dữ liệu cụ thể hay không.
<biểu thức> instanceof <kiểu>

x instanceof Person;  // Kiểm tra nếu x là một đối tượng thuộc kiểu Person

Nếu x là đối tượng của lớp Person, thì công thức này sẽ trả về giá trị đúng.

**Kiểm tra phạm vi (Range checks)**
Kiểm tra phạm vi là một loại công thức kiểm tra xem giá trị của một biểu thức có nằm trong một phạm vi số học nào đó hay không.
Cú pháp: <biểu thức> in <phạm vi>

x in [1..10];  // Kiểm tra nếu x nằm trong phạm vi từ 1 đến 10 (bao gồm cả 1 và 10)

Công thức trên sẽ đúng nếu giá trị của x nằm trong khoảng từ 1 đến 10.

**Gọi hàm predicate (Calls to predicates)**
Hàm predicate là các hàm logic được sử dụng để kiểm tra các điều kiện trong công thức. Một hàm predicate có thể được gọi với hoặc không có kết quả trả về.

isEven(x);  // Kiểm tra nếu x là số chẵn
x.isEven();  // Gọi phương thức isEven() từ đối tượng x, nếu x là số chẵn công thức này trả về đúng

Công thức trên sẽ trả về đúng nếu x là số chẵn. Trong đó isEven(x) có thể là một hàm kiểm tra xem số x có phải là số chẵn hay không.

**Kết nối logic (Logical connectives)**
Bạn có thể kết hợp nhiều công thức với nhau bằng các toán tử logic như and, or, not, và implies. Điều này giúp xây dựng các công thức phức tạp hơn.

not: Đảo ngược giá trị logic của một công thức.
and: Công thức kết hợp hai điều kiện, chỉ đúng khi cả hai đều đúng.
or: Công thức kết hợp hai điều kiện, đúng nếu ít nhất một trong hai điều kiện đúng.
implies: Đúng nếu điều kiện trước (A) đúng thì điều kiện sau (B) cũng đúng

A and B implies C;  // Điều kiện này đúng nếu A và B đều đúng, và C cũng phải đúng

Trong ví dụ trên, nếu cả A và B đều đúng, thì C cũng phải đúng mới làm công thức này thành đúng.

**Công thức có điều kiện (Conditional formulas)**
Bạn có thể sử dụng cú pháp if ... then ... else để viết công thức có điều kiện.

visibility(Class c) {
  if c.isPublic() then result = "public"
  else result = "private"
}

Ví dụ trên sẽ kiểm tra nếu lớp c là lớp công khai (isPublic), kết quả sẽ là "public", nếu không sẽ là "private".

**Công thức với lượng từ (Quantified formulas)**
Các công thức với lượng từ như exists, forall cho phép bạn biểu diễn các công thức tổng quát hơn, bao gồm việc xác định có tồn tại một giá trị thỏa mãn điều kiện hay không, hoặc mọi giá trị đều thỏa mãn một điều kiện nào đó.

exists: Tồn tại ít nhất một giá trị thỏa mãn công thức.
forall: Mọi giá trị phải thỏa mãn công thức.

exists(int i | i < 5);  // Tồn tại ít nhất một giá trị của i thỏa mãn i < 5
forall(int i | i < 5 | i > 0);  // Mọi giá trị của i nhỏ hơn 5 phải lớn hơn 0

**Công thức với this (Implicit this receivers)**
Khi bạn gọi các hàm predicate hoặc phương thức trong các lớp, nếu không chỉ rõ đối tượng gọi (receiver), mặc định sẽ sử dụng this (tức là đối tượng hiện tại).

class OneTwoThree extends int {
  OneTwoThree() { this = 1 or this = 2 or this = 3 }
  predicate isEven() { this = 2 }
  predicate isOdd() { not isEven() }
}

Trong ví dụ này, isEven() và isOdd() là các hàm predicate kiểm tra xem giá trị của this có phải là số chẵn hay không.

**Kết luận**
Các công thức trong QL cho phép bạn thực hiện các truy vấn phức tạp với sự kết hợp của các toán tử so sánh, logic, kiểm tra kiểu và phạm vi, cũng như gọi hàm predicate.
Các công thức này có thể sử dụng nhiều loại kết nối logic để tạo ra các biểu thức phức tạp, giúp bạn khai thác dữ liệu một cách linh hoạt và mạnh mẽ

## Annotations

Annotation trong QL là các chuỗi ký tự đặc biệt mà bạn có thể thêm vào trước khi khai báo một thực thể hoặc tên thực thể trong mã của bạn.
Chúng giúp điều chỉnh hành vi hoặc tính chất của các thực thể đó, như là một lớp, hàm, hoặc predicate.

private module M {
    ...
}

Ở đây, private là annotation dùng để khai báo module M là private, tức là chỉ có thể được truy cập trong phạm vi module này.

**Các loại Annotation**
Các annotation có thể tác động trực tiếp lên thực thể (entity) hoặc tên thực thể (name). Dưới đây là các loại annotation phổ biến:

**Annotation tác động lên thực thể (Entity):**
abstract: Được sử dụng để khai báo một thực thể là trừu tượng (abstract). Những thực thể này không có thân hàm (body) và cần phải được ghi đè (override) trong các thực thể con.

abstract class Configuration {
    abstract predicate isSource(Node source);
}

Trong ví dụ trên, isSource là một predicate trừu tượng cần được ghi đè trong các lớp con.
cached: Đánh dấu thực thể cần được lưu trữ trong bộ nhớ cache. Điều này có thể cải thiện hiệu suất khi một thực thể được tính toán nhiều lần.

cached predicate expensivePredicate() { ... }

Với annotation cached, predicate này sẽ được tính toán một lần và sử dụng lại kết quả trong các lần gọi sau.

external: Đánh dấu predicate là “bên ngoài”, tương tự như việc định nghĩa một predicate từ cơ sở dữ liệu. Các predicate này thường không được tính toán trong hệ thống QL mà sẽ liên kết với một dịch vụ bên ngoài.

external predicate externalFunction(int i);

transient: Được áp dụng khi bạn muốn predicate không bị cache khi đánh dấu là external. Điều này giúp tránh việc lưu trữ dữ liệu vào đĩa trong quá trình tính toán.

transient external predicate myExternalPredicate();

final: Đánh dấu một thực thể không thể bị ghi đè hay mở rộng. Một lớp, predicate, hoặc trường được đánh dấu là final không thể được kế thừa hay thay đổi trong các lớp con.

final predicate isValid(string value) { value = "valid" }

Annotation tác động lên tên thực thể (Name):
private: Đánh dấu một thực thể là private, chỉ có thể được truy cập trong module hiện tại. Điều này hữu ích khi bạn muốn giới hạn quyền truy cập vào các thực thể.

Ví dụ:

e int foo() { return 1; }
Ở đây, foo là một hàm private, chỉ có thể được gọi trong module hiện tại.

deprecated: Đánh dấu một thực thể là đã lỗi thời và sẽ bị loại bỏ trong các phiên bản sau. Các thực thể này nên được thay thế bằng các thực thể mới hơn.

Ví dụ:

deprecated class OldClass { ... }
library: Được sử dụng để đánh dấu một thực thể chỉ có thể được tham chiếu từ trong một tệp .qll. Tuy nhiên, annotation này hiện đã bị deprecated.

Ví dụ:

library class MyLibraryClass { ... }
query: Được sử dụng để biến một predicate thành một query, tức là nó sẽ trở thành một phần của kết quả đầu ra của chương trình QL.

Ví dụ:

`query predicate fetchData() { ... }`

Các pragmas biên dịch (Compiler pragmas)
Những pragmas này ảnh hưởng đến việc biên dịch và tối ưu hóa các truy vấn trong QL. Chúng giúp bạn điều chỉnh hành vi của trình biên dịch QL khi gặp phải các vấn đề hiệu suất.

pragma[inline]: Được sử dụng để yêu cầu trình biên dịch "inline" (thay thế) predicate với thân hàm của nó tại các vị trí được gọi. Điều này có thể giúp cải thiện hiệu suất nếu predicate đó tốn nhiều thời gian để tính toán.

Ví dụ:

pragma[inline]
predicate expensiveFunction() { ... }
pragma[noinline]: Ngược lại với inline, annotation này yêu cầu trình biên dịch không thực hiện hành động inlining, có thể hữu ích khi bạn muốn tránh mất hiệu suất trong một số trường hợp nhất định.

Ví dụ:

pragma[noinline]
predicate helperFunction() { ... }
pragma[nomagic]: Được sử dụng để tắt tối ưu hóa "magic sets", một kỹ thuật giúp tối ưu hóa các truy vấn bằng cách đưa thông tin từ ngữ cảnh vào thân predicate.

Ví dụ:

pragma[nomagic]
predicate complexPredicate() { ... }
pragma[noopt]: Tắt tất cả các tối ưu hóa của trình biên dịch cho predicate, chỉ khi nào cần thiết cho việc biên dịch và đánh giá thì mới được thực hiện.

Ví dụ:

pragma[noopt]
predicate complexQuery() { ... }

**Pragmas Ngôn Ngữ (Language Pragmas)**
Những annotation này ảnh hưởng đến cách ngôn ngữ QL xử lý các cú pháp hoặc phép toán nhất định.

language[monotonicAggregates]: Được sử dụng khi bạn muốn sử dụng các phép toán tổng hợp đơn điệu thay vì các phép toán tổng hợp mặc định của QL.

Ví dụ:

`language[monotonicAggregates]`

**Binding Sets**
bindingset[...]: Annotation này được sử dụng để chỉ rõ các tập hợp biến (binding sets) cho một predicate hoặc class. Tập hợp này giúp QL tối ưu hóa cách thức các phép toán được đánh giá.

bindingset[x, y]
predicate myPredicate(int x, int y) { ... }

**Tóm lại:**
Annotations trong QL giúp kiểm soát và tối ưu hóa cách các thực thể và tên thực thể được xử lý trong chương trình.
Việc sử dụng các annotation đúng cách có thể giúp bạn cải thiện hiệu suất, đảm bảo tính chính xác và khả năng tái sử dụng của mã nguồn.
Hãy lựa chọn các annotation phù hợp với mục đích và yêu cầu cụ thể của chương trình bạn.

## Recursion
QL hỗ trợ mạnh mẽ việc sử dụng đệ quy trong các truy vấn. Một predicate trong QL được gọi là đệ quy nếu nó phụ thuộc vào chính nó, trực tiếp hoặc gián tiếp.

Để tính toán một predicate đệ quy, trình biên dịch của QL tìm điểm cố định nhỏ nhất của đệ quy. Cụ thể, nó bắt đầu với một tập hợp giá trị rỗng, sau đó tìm ra các giá trị mới bằng cách áp dụng predicate nhiều lần cho đến khi tập hợp các giá trị không còn thay đổi. Khi đó, tập hợp này được gọi là điểm cố định nhỏ nhất và nó chính là kết quả của phép tính toán.

Các ví dụ về predicate đệ quy
Ví dụ 1: Đếm từ 0 đến 100
Giả sử bạn muốn tạo ra một truy vấn liệt kê tất cả các số nguyên từ 0 đến 100. Bạn có thể sử dụng predicate đệ quy như sau:

int getANumber() {
  result = 0
  or
  result <= 100 and result = getANumber() + 1
}

select getANumber()
Giải thích: Predicate getANumber() bắt đầu với giá trị 0. Sau đó, ở mỗi lần gọi tiếp theo, nó sẽ lấy một giá trị lớn hơn giá trị trước đó. Lệnh or đảm bảo rằng predicate tiếp tục tính toán và thêm các giá trị mới cho đến khi đạt đến 100.
Kết quả: Tập hợp kết quả là các số từ 0 đến 100, vì getANumber() sẽ liên tục tính toán các giá trị mới cho đến khi không thể thêm được giá trị nào nữa.

Ví dụ 2: Đệ quy tương hỗ (Mutual Recursion)
Đệ quy không chỉ có thể xảy ra trong một predicate mà còn có thể giữa các predicate khác nhau, tạo thành một chu trình đệ quy. Ví dụ sau sử dụng các số chẵn và lẻ:

int getAnEven() {
  result = 0
  or
  result <= 100 and result = getAnOdd() + 1
}

int getAnOdd() {
  result = getAnEven() + 1
}

select getAnEven()
Giải thích: getAnEven() bắt đầu từ 0 và sử dụng getAnOdd() để lấy số lẻ tiếp theo, và ngược lại, getAnOdd() lại gọi getAnEven() để lấy số chẵn tiếp theo. Quá trình này tiếp diễn cho đến khi giá trị đạt tới 100.
Kết quả: Truy vấn select getAnEven() sẽ trả về các số chẵn từ 0 đến 100. Nếu thay thế bằng select getAnOdd(), kết quả sẽ là các số lẻ từ 1 đến 101.

Ví dụ 3: Closure truyền (Transitive Closure)
Closure truyền là một loại đệ quy phổ biến, trong đó các kết quả của predicate được tính bằng cách áp dụng predicate ban đầu nhiều lần.

QL hỗ trợ một cú pháp ngắn gọn cho closure truyền bằng cách thêm dấu + vào tên predicate, hoặc closure truyền phản chiếu bằng dấu *.

Transitive Closure +
Giả sử bạn có một lớp Person với một predicate là getAParent(), trả về các bậc phụ huynh của một người. Để tìm ra tổ tiên của người đó, bạn có thể sử dụng closure truyền như sau:

Person getAnAncestor() {
  result = this.getAParent()
  or
  result = this.getAParent().getAnAncestor()
}

Tuy nhiên, bạn có thể sử dụng cú pháp + đơn giản hơn để có kết quả tương tự:

Person getAnAncestor+()
Giải thích: this.getAParent+() sẽ trả về tất cả các tổ tiên của người this (bố, mẹ, ông bà, v.v...), và cứ thế tiếp tục theo chiều dọc của cây gia đình.
Reflexive Transitive Closure *
Cú pháp * dùng để áp dụng predicate đến chính nó, có thể lặp lại từ 0 lần trở lên. Ví dụ sau tìm tổ tiên bao gồm cả chính người đó:

Person getAnAncestor2() {
  result = this
  or
  result = this.getAParent().getAnAncestor2()
}

Tương đương với cú pháp *:

Person getAnAncestor*()
Giải thích: Ở đây, this.getAParent*() sẽ trả về tất cả tổ tiên của this và cả chính this nếu có. Ví dụ, nếu this là một người thì kết quả có thể bao gồm this (người hiện tại), bố, mẹ, ông bà, v.v...

3. Những hạn chế và lỗi phổ biến trong đệ quy
Đệ quy có thể dễ dàng gặp phải lỗi, đặc biệt khi không có điểm khởi đầu hoặc khi recursion không monotonic. Dưới đây là một số lỗi phổ biến:

Đệ quy rỗng (Empty Recursion)
Để định nghĩa một predicate đệ quy hợp lệ, bạn cần phải có một điểm khởi đầu. Nếu không, predicate sẽ không bao giờ tạo ra kết quả, dẫn đến một đệ quy rỗng.

Ví dụ sai:

Person getAnAncestor() {
  result = this.getAParent().getAnAncestor()
}

Lỗi này xảy ra vì getAnAncestor() bắt đầu với một predicate rỗng, không có cơ sở khởi đầu để bắt đầu quá trình đệ quy. Để sửa lỗi, bạn cần thêm một trường hợp cơ sở.

Ví dụ đúng:

Person getAnAncestor() {
  result = this.getAParent()
  or
  result = this.getAParent().getAnAncestor()
}

Đệ quy không monotonic (Non-monotonic Recursion)
Một predicate đệ quy hợp lệ phải monotonic, nghĩa là khi áp dụng predicate nhiều lần, tập hợp các giá trị phải tăng lên hoặc giữ nguyên, không thể giảm đi. Nếu recursion không monotonic, sẽ xuất hiện các tình huống không thể giải quyết, ví dụ như "liar’s paradox".

Ví dụ sai:

predicate isParadox() {
  not isParadox()
}

Lỗi ở đây là predicate isParadox() mâu thuẫn với chính nó vì nó chỉ đúng khi nó không đúng, tạo ra một vòng lặp vô hạn.

Đệ quy hợp lệ với số lần phủ định chẵn
Để tránh vấn đề "liar’s paradox", recursion chỉ hợp lệ khi có số lần phủ định chẵn. Ví dụ về một predicate hợp lệ có thể viết lại như sau:

predicate isExtinct() {
  this.isDead() and
  not exists(Person descendant | descendant.getAParent+() = this |
    not descendant.isExtinct()
  )
}

Ở đây, recursion được bao quanh bởi số lượng phủ định chẵn, đảm bảo tính hợp lệ.

4. Kết luận
Đệ quy là một công cụ mạnh mẽ trong QL, giúp bạn dễ dàng truy vấn các dữ liệu có cấu trúc đệ quy như cây hay đồ thị. Tuy nhiên, để sử dụng đệ quy hiệu quả và tránh lỗi, bạn cần đảm bảo rằng predicate có điểm khởi đầu rõ ràng và tuân thủ nguyên tắc monotonicity. Các cú pháp transitive closure (+ và *) cũng giúp đơn giản hóa việc định nghĩa các predicate đệ quy phức tạp.

## Lexical Syntax

**Cú pháp từ vựng (Lexical Syntax) trong QL**
Cú pháp từ vựng trong QL bao gồm các từ khóa, định danh (identifiers), và các chú thích. Những yếu tố này cấu thành nên cách thức mà mã nguồn được viết và hiểu bởi trình biên dịch QL.

Cụ thể, trong QL:

Từ khóa (keywords): Đây là những từ có nghĩa đặc biệt trong ngữ pháp của QL, chẳng hạn như class, int, or, select, v.v.
Định danh (identifiers): Đây là tên của các đối tượng như lớp, biến, predicate, hàm, v.v.
Chú thích (comments): Chú thích là phần không được trình biên dịch QL xử lý, chỉ nhằm mục đích cung cấp thông tin cho lập trình viên. Các loại chú thích trong QL bao gồm chú thích một dòng, chú thích nhiều dòng, và chú thích QLDoc.

**Các loại chú thích trong QL**
QL hỗ trợ ba loại chú thích chính: chú thích một dòng, chú thích nhiều dòng, và QLDoc comments. Mỗi loại có mục đích sử dụng khác nhau và giúp lập trình viên ghi chú mã nguồn một cách rõ ràng hơn.

Chú thích một dòng
Chú thích một dòng được dùng để giải thích nhanh về một phần cụ thể trong mã. Chú thích này bắt đầu với ký tự // và kéo dài đến hết dòng.

class Digit extends int {  // Một chú thích một dòng
  Digit() {
    this in [0 .. 9]
  }
}

Giải thích: Trong ví dụ trên, chú thích một dòng // Một chú thích một dòng giải thích rằng đây là phần khai báo một lớp Digit, và dòng mã phía trước định nghĩa rằng đối tượng this thuộc phạm vi từ 0 đến 9.

**Chú thích nhiều dòng**
Chú thích nhiều dòng được sử dụng khi bạn cần ghi chú dài hoặc cần giải thích nhiều chi tiết. Chú thích này được bắt đầu bằng /* và kết thúc bằng */.

/*
  Một chú thích nhiều dòng, có thể dùng để cung cấp
  thông tin chi tiết hơn, hoặc để viết một chú thích TODO.
*/

Giải thích: Trong ví dụ này, chú thích nhiều dòng được sử dụng để ghi chú giải thích chi tiết hơn về một phần mã hoặc có thể dùng để ghi chú những công việc cần làm sau (TODO comment).

**QLDoc comments**
QLDoc là một loại chú thích đặc biệt dùng để mô tả các thực thể trong QL như lớp, predicate, hàm, v.v. Chúng giúp tạo tài liệu tự động và thường xuất hiện dưới dạng pop-up trong các trình soạn thảo mã nguồn hỗ trợ QL. Đây là công cụ hữu ích để tạo tài liệu mô tả về các đối tượng trong mã nguồn của bạn.

QLDoc comments bắt đầu bằng /** và kết thúc bằng */, và thường được dùng để mô tả mục đích hoặc chi tiết về các thực thể trong QL.

/**
 * Một chú thích QLDoc mô tả lớp `Digit`.
 */
class Digit extends int {
  Digit() {
    this in [0 .. 9]
  }
}

Giải thích: Ở đây, chú thích /** ... */ mô tả lớp Digit trong QL, giải thích rằng lớp này kế thừa từ kiểu dữ liệu int và các đối tượng của nó có giá trị từ 0 đến 9. Các công cụ hỗ trợ QL sẽ hiển thị chú thích này dưới dạng pop-up khi bạn di chuột vào lớp Digit.

**Tóm tắt các loại chú thích trong QL**
Chú thích một dòng (//): Dùng để giải thích nhanh một phần cụ thể trong mã.
Chú thích nhiều dòng (/* ... */): Dùng để cung cấp thông tin chi tiết hơn hoặc chú thích nhiều dòng.
QLDoc comments (/** ... */): Dùng để tạo tài liệu mô tả các thực thể trong mã, giúp người khác hiểu rõ hơn về các thành phần của chương trình khi sử dụng các công cụ hỗ trợ QL.

**Kết luận**
Chú thích trong QL rất quan trọng để giúp người lập trình viên ghi chú và giải thích mã nguồn. Chúng không chỉ giúp bạn hiểu rõ mã nguồn của mình mà còn có thể hỗ trợ trong việc tạo ra tài liệu mô tả cho dự án. Trong QL, bạn có thể sử dụng chú thích một dòng, nhiều dòng hoặc chú thích QLDoc tùy theo mục đích sử dụng và mức độ chi tiết bạn muốn cung cấp.

## Name resolution
Biên dịch viên QL sẽ giải quyết các tên thành các phần tử chương trình.

Cũng giống như các ngôn ngữ lập trình khác, có sự phân biệt giữa tên được sử dụng trong mã QL và các thực thể (entities) QL mà chúng đại diện.

Có thể có nhiều thực thể trong QL có cùng tên, ví dụ như khi chúng được định nghĩa trong các module riêng biệt. Do đó, rất quan trọng để biên dịch viên QL có thể giải quyết tên thành thực thể đúng.

Khi bạn viết mã QL của riêng mình, bạn có thể sử dụng các biểu thức khác nhau để tham chiếu đến các thực thể. Các biểu thức này sẽ được giải quyết thành các thực thể trong không gian tên (namespace) phù hợp.

**Các loại biểu thức:**

Biểu thức Module
Đây là những biểu thức tham chiếu đến các module.
Chúng có thể là tên đơn giản, tham chiếu có tên đầy đủ (trong câu lệnh import), lựa chọn, hoặc khởi tạo.

Biểu thức Kiểu
Đây là những biểu thức tham chiếu đến các kiểu dữ liệu.
Chúng có thể là tên đơn giản hoặc lựa chọn.

Biểu thức Dự đoán (Predicate)
Đây là những biểu thức tham chiếu đến các predicate.
Chúng có thể là tên đơn giản hoặc tên kèm độ dài (arity) (ví dụ trong định nghĩa alias), hoặc lựa chọn.

Biểu thức Chữ ký (Signature)
Đây là những biểu thức tham chiếu đến các chữ ký của module, kiểu, hoặc predicate.
Chúng có thể là tên đơn giản, tên kèm độ dài, lựa chọn, hoặc khởi tạo.

**Tên (Names)**
Để giải quyết tên đơn giản (cùng với độ dài), biên dịch viên sẽ tìm tên đó (và độ dài) trong không gian tên của module hiện tại.

Trong câu lệnh import, việc giải quyết tên phức tạp hơn một chút. Ví dụ, giả sử bạn định nghĩa một module truy vấn Example.ql với câu lệnh import sau:

import javascript

Biên dịch viên sẽ kiểm tra đầu tiên module thư viện javascript.qll. Nếu không tìm thấy, nó sẽ tìm kiếm một module rõ ràng có tên javascript trong không gian tên của module Example.ql.

**Tham chiếu có tên đầy đủ (Qualified References)**
Tham chiếu có tên đầy đủ là biểu thức module sử dụng dấu . như dấu phân cách đường dẫn tệp. Bạn chỉ có thể sử dụng biểu thức này trong các câu lệnh import, để nhập một module thư viện được định nghĩa bằng một đường dẫn tương đối.

Ví dụ, nếu bạn định nghĩa một module truy vấn Example.ql với câu lệnh import sau:

import examples.security.MyLibrary

Biên dịch viên sẽ xử lý câu lệnh import như sau:

Đầu tiên, nó sẽ tìm tệp examples/security/MyLibrary.qll trong thư mục chứa Example.ql.
Nếu không tìm thấy, nó sẽ tìm tệp examples/security/MyLibrary.qll trong thư mục truy vấn, nếu có. Thư mục truy vấn là thư mục bao quanh đầu tiên chứa tệp có tên qlpack.yml (hoặc trong các sản phẩm cũ, tệp queries.xml).
Nếu không tìm thấy ở hai bước trên, biên dịch viên sẽ tìm tệp trong từng mục đường dẫn thư viện.

Nếu biên dịch viên không thể giải quyết câu lệnh import, nó sẽ báo lỗi biên dịch.

**Lựa chọn (Selections)**
Bạn có thể sử dụng một lựa chọn để tham chiếu đến một module, kiểu, hoặc predicate trong một module cụ thể. Lựa chọn có dạng:

<module_expression>::<name>

Biên dịch viên sẽ giải quyết biểu thức module trước, sau đó tìm kiếm tên trong không gian tên của module đó.

**Ví dụ:**

Giả sử bạn có module thư viện CountriesLib.qll với nội dung:

class Countries extends string {
  Countries() {
    this = "Belgium"
    or
    this = "France"
    or
    this = "India"
  }
}

module M {
  class EuropeanCountries extends Countries {
    EuropeanCountries() {
      this = "Belgium"
      or
      this = "France"
    }
  }
}

Bạn có thể viết một truy vấn nhập CountriesLib và sau đó sử dụng M::EuropeanCountries để tham chiếu đến lớp EuropeanCountries:

import CountriesLib

from M::EuropeanCountries ec
select ec

Hoặc bạn có thể nhập trực tiếp nội dung của module M bằng cách sử dụng lựa chọn CountriesLib::M trong câu lệnh import:

import CountriesLib::M

from EuropeanCountries ec
select ec

Điều này giúp truy vấn có quyền truy cập vào tất cả các thành phần trong M, nhưng không có quyền truy cập vào các thành phần trong CountriesLib mà không có trong M.

**Không gian tên (Namespaces)**
Khi viết mã QL, việc hiểu cách không gian tên hoạt động là rất quan trọng.

Như trong nhiều ngôn ngữ lập trình khác, một không gian tên là một ánh xạ từ khóa (key) đến thực thể (entity). Một khóa có thể là một kiểu định danh, ví dụ như tên, và một thực thể QL có thể là một module, một kiểu, hoặc một predicate.

Mỗi module trong QL có sáu không gian tên:

Không gian tên module: Chứa tên các module và các thực thể là module.
Không gian tên kiểu (type): Chứa tên các kiểu và các thực thể là kiểu.
Không gian tên predicate: Chứa tên các predicate và độ dài (arity) của chúng.
Không gian tên chữ ký module: Chứa tên các chữ ký module và các thực thể là chữ ký module.
Không gian tên chữ ký kiểu: Chứa tên các chữ ký kiểu và các thực thể là chữ ký kiểu.
Không gian tên chữ ký predicate: Chứa tên các chữ ký predicate và các thực thể là chữ ký predicate.
Các không gian tên này không hoàn toàn độc lập với nhau. Ví dụ, không thể chia sẻ khóa giữa không gian tên module và không gian tên chữ ký module, hoặc giữa không gian tên kiểu và không gian tên chữ ký kiểu.

**Không gian tên toàn cầu (Global namespaces)**
Các không gian tên chứa tất cả các thực thể xây dựng sẵn được gọi là không gian tên toàn cầu, và chúng luôn có sẵn trong mọi module.

Ví dụ về không gian tên trong module: Trong module Villagers.qll, bạn có thể định nghĩa các lớp và predicate, ví dụ:

import tutorial

predicate isBald(Person p) {
  not exists(string c | p.getHairColor() = c)
}

class Child extends Person {
  Child() {
    this.getAge() < 10
  }
}

module S {
  predicate isSouthern(Person p) {
    p.getLocation() = "south"
  }

  class Southerner extends Person {
    Southerner() {
      isSouthern(this)
    }
  }
}

import tutorial

predicate isBald(Person p) {
  not exists(string c | p.getHairColor() = c)
}

class Child extends Person {
  Child() {
    this.getAge() < 10
  }
}

module S {
  predicate isSouthern(Person p) {
    p.getLocation() = "south"
  }

  class Southerner extends Person {
    Southerner() {
      isSouthern(this)
    }
  }
}

Không gian tên module sẽ chứa các module đã nhập, như S, và bất kỳ module nào được xuất khẩu từ tutorial.

## Evaluation of QL programs
Đánh giá chương trình QL
Một chương trình QL được đánh giá qua một số bước khác nhau.

Quy trình
Khi một chương trình QL chạy trên một cơ sở dữ liệu, nó sẽ được biên dịch thành một biến thể của ngôn ngữ lập trình logic Datalog. Sau khi biên dịch, chương trình sẽ được tối ưu hóa để nâng cao hiệu suất và sau đó thực thi để tạo ra kết quả.

Các kết quả này là các tập hợp các bộ giá trị có thứ tự (ordered tuples). Một bộ giá trị có thứ tự là một chuỗi hữu hạn các giá trị có thứ tự. Ví dụ, (1, 2, "three") là một bộ giá trị có thứ tự bao gồm hai số nguyên và một chuỗi. Trong khi chương trình được đánh giá, có thể có các kết quả trung gian được tạo ra: những kết quả này cũng là các tập hợp bộ giá trị.

Chương trình QL được đánh giá từ dưới lên (bottom-up), điều này có nghĩa là một predicate thường chỉ được đánh giá sau khi tất cả các predicate mà nó phụ thuộc đã được đánh giá.

Cơ sở dữ liệu bao gồm các tập hợp bộ giá trị cho các predicate xây dựng sẵn (built-in predicates) và predicate bên ngoài (external predicates). Mỗi lần đánh giá bắt đầu từ các tập hợp bộ giá trị này. Các predicate và kiểu còn lại trong chương trình được tổ chức thành nhiều lớp, dựa trên sự phụ thuộc giữa chúng. Các lớp này sẽ được đánh giá để tạo ra các tập hợp bộ giá trị riêng, bằng cách tìm điểm cố định nhỏ nhất (least fixed point) của mỗi predicate. (Ví dụ, xem phần "Đệ quy (Recursion)").

Các truy vấn của chương trình sẽ xác định các tập hợp bộ giá trị nào sẽ tạo thành kết quả cuối cùng của chương trình. Kết quả sẽ được sắp xếp theo các chỉ thị sắp xếp (order by) trong các truy vấn.

Để biết thêm chi tiết về từng bước trong quá trình đánh giá, bạn có thể tham khảo “QL language specification.”

**Tính hợp lệ của chương trình**
Kết quả của một truy vấn phải luôn là một tập hợp hữu hạn các giá trị, nếu không nó sẽ không thể được đánh giá. Nếu mã QL của bạn chứa một predicate hoặc truy vấn vô hạn, biên dịch viên QL sẽ thường xuyên thông báo lỗi, giúp bạn dễ dàng xác định lỗi.

Dưới đây là một số cách phổ biến mà bạn có thể định nghĩa các predicate vô hạn. Tất cả các ví dụ này sẽ gây ra lỗi biên dịch:

Truy vấn chọn tất cả các giá trị kiểu int mà không hạn chế:
Truy vấn này sẽ gây lỗi: 'i' is not bound to a value (biến i chưa được gắn giá trị):

from int i
select i

Predicate không có giá trị gắn kết:
Predicate dưới đây gây lỗi vì cả hai biến n và result đều không có giá trị gắn kết:

int timesTwo(int n) {
  result = n * 2
}

Lớp Person chứa tất cả các chuỗi bắt đầu bằng "Peter":
Lớp này chứa vô số chuỗi, vì vậy nó là một định nghĩa không hợp lệ. Biên dịch viên QL sẽ báo lỗi 'this' is not bound to a value (biến this chưa được gắn giá trị):

class Person extends string {
  Person() {
    this.matches("Peter%")
  }
}

Để sửa những lỗi này, bạn cần đảm bảo rằng không có biến nào không được gắn giá trị. Một predicate hoặc truy vấn được coi là hạn chế phạm vi (range-restricted) nếu mỗi biến trong đó có ít nhất một lần gắn giá trị. Một biến không có lần gắn giá trị nào gọi là không gắn (unbound).

**Gắn kết (Binding)**
Để tránh các quan hệ vô hạn trong truy vấn, bạn cần đảm bảo rằng không có biến nào không được gắn giá trị. Để làm điều này, bạn có thể sử dụng các cơ chế sau:

Các kiểu hữu hạn: Các biến có kiểu hữu hạn là đã được gắn kết. Cụ thể, bất kỳ kiểu nào không phải là kiểu nguyên thủy đều là hữu hạn. Để gán kiểu hữu hạn cho một biến, bạn có thể khai báo nó với một kiểu hữu hạn, sử dụng phép ép kiểu (cast) hoặc kiểm tra kiểu (type check).

Gọi predicate: Một predicate hợp lệ thường là hạn chế phạm vi, vì vậy nó gắn kết tất cả các đối số của nó. Do đó, nếu bạn gọi một predicate trên một biến, biến đó sẽ được gắn kết.

Toán tử gắn kết: Hầu hết các toán tử, chẳng hạn như các toán tử số học, yêu cầu tất cả các toán hạng của chúng phải được gắn kết. Ví dụ, bạn không thể cộng hai biến trong QL trừ khi bạn có một tập hợp hữu hạn các giá trị có thể có cho cả hai biến.

Tuy nhiên, cũng có một số toán tử xây dựng sẵn có thể gắn kết các đối số của chúng. Ví dụ, nếu một phía của phép so sánh bằng (=) đã được gắn kết và phía còn lại là một biến, thì biến đó cũng sẽ được gắn kết.

**Ví dụ về Gắn kết và Không Gắn kết**
Dưới đây là một số ví dụ để làm rõ sự khác biệt giữa các sự kiện gắn kết và không gắn kết của biến:

x = 1: Gắn kết: Giới hạn x chỉ có giá trị là 1.
x != 1: Không gắn kết: Không có sự ràng buộc nào đối với x.
x = 2 + 3: Gắn kết: Biến x sẽ nhận giá trị là 5.
x in [0 .. 3]: Gắn kết: Biến x bị giới hạn trong phạm vi [0, 1, 2, 3].
Bạn có thể sửa các ví dụ “vô hạn” trên bằng cách cung cấp một lần gắn kết. Ví dụ, thay vì định nghĩa predicate như sau:

int timesTwo(int n) {
  result = n * 2
}

Bạn có thể sửa lại như sau để gắn kết n trong phạm vi hữu hạn:

int timesTwo(int n) {
  n in [0 .. 10] and
  result = n * 2
}

Khi đó, n sẽ được gắn kết, và biến result sẽ tự động được gắn kết qua phép tính result = n * 2.

## Final: QL language specification
QL (Query Language) là một ngôn ngữ lập trình logic được sử dụng để truy vấn dữ liệu trong các cơ sở dữ liệu. QL có những đặc điểm và quy định quan trọng trong ngữ pháp và cách hoạt động mà bạn cần lưu ý khi lập trình với nó.

**1. Cấu trúc cơ bản của QL**
Predicate (Điều kiện): Đây là các hàm logic để xác định các mối quan hệ giữa các đối tượng. Các predicate có thể nhận một hoặc nhiều đối số và trả về giá trị boolean (đúng/sai).
Class (Lớp): QL hỗ trợ việc định nghĩa lớp để mô tả các đối tượng với các thuộc tính và hành vi (predicate). Một lớp có thể kế thừa từ lớp khác.
Module (Mô-đun): QL hỗ trợ việc chia mã thành các mô-đun để tổ chức và tái sử dụng code. Một mô-đun có thể chứa nhiều lớp và predicate.

**2. Biểu thức và cú pháp**
Biểu thức: Các biểu thức có thể là các tên module, kiểu, predicate, hoặc chữ ký. Cú pháp này giúp xác định và truy vấn các thực thể trong chương trình.
Cú pháp truy vấn: Truy vấn trong QL thường có dạng from ... select ..., trong đó bạn chỉ định nguồn dữ liệu (thường là các đối tượng hoặc các predicate) và cách truy xuất các giá trị.

**3. Namespaces (Không gian tên)**
Không gian tên trong QL: Các đối tượng, kiểu, predicate được tổ chức trong không gian tên khác nhau. Điều này giúp phân biệt các đối tượng có thể trùng tên nhưng khác loại hoặc khác phạm vi.
Không gian tên toàn cục và cục bộ: Toàn cục chứa các đối tượng chuẩn như kiểu dữ liệu và predicate được định nghĩa sẵn. Cục bộ là những đối tượng được định nghĩa trong mỗi mô-đun.

**4. Quy trình đánh giá (Evaluation Process)**
Chương trình QL được đánh giá từ dưới lên, tức là các predicate chỉ được đánh giá sau khi các predicate mà chúng phụ thuộc đã được tính toán.
Điểm cố định nhỏ nhất (least fixed point): Khi đánh giá một predicate, hệ thống tìm điểm cố định nhỏ nhất, tức là tập hợp giá trị không thay đổi thêm khi các predicate được đánh giá thêm.

**5. Binding (Gắn kết)**
Một biến chỉ được coi là "được gắn kết" nếu nó có một giá trị cố định. Các biến không được gắn kết sẽ tạo ra vòng lặp vô hạn trong truy vấn.
QL yêu cầu rằng các biến phải có ít nhất một lần gắn kết trong mỗi predicate để tránh sự vô hạn. Các cơ chế như kiểu dữ liệu hữu hạn, các phép toán và predicate giúp gắn kết các biến.

**6. Các kiểu dữ liệu (Types)**
QL hỗ trợ nhiều kiểu dữ liệu bao gồm kiểu cơ bản (int, string, boolean, float, date) và các kiểu dữ liệu phức tạp như lớp (classes).
Các kiểu dữ liệu có thể được sử dụng để khai báo biến và đối số trong các predicate.

**7. Các phép toán và toán tử (Operators)**
QL cung cấp các phép toán logic, toán học, và so sánh để thao tác với các giá trị trong các predicate. Các phép toán này cũng có ảnh hưởng đến việc gắn kết các biến.

**8. Quy tắc về phạm vi (Scope rules)**
Các tên trong QL có thể có phạm vi trong mô-đun, trong lớp, hoặc phạm vi toàn cục. Các tên không thể trùng lặp trong cùng một phạm vi, nhưng có thể trùng tên giữa các phạm vi khác nhau.

**9. Xử lý lỗi và các điều kiện không hợp lệ**
QL đảm bảo rằng kết quả truy vấn luôn là một tập hợp hữu hạn các giá trị. Nếu chương trình chứa các predicate vô hạn hoặc các biến không gắn kết, hệ thống sẽ báo lỗi để giúp người dùng dễ dàng xác định và sửa lỗi.

**10. Tối ưu hóa và hiệu suất**
QL hỗ trợ các kỹ thuật tối ưu hóa trong quá trình đánh giá để giảm thiểu thời gian tính toán. Các bước đánh giá được tổ chức trong các lớp tùy thuộc vào sự phụ thuộc giữa các predicate.

**11. Đệ quy (Recursion)**
QL hỗ trợ đệ quy trong các predicate, điều này cho phép bạn viết các truy vấn phức tạp và các mối quan hệ phụ thuộc lẫn nhau giữa các đối tượng.

[Source](https://codeql.github.com/docs/ql-language-reference/)