via operations that are entirely devoid of any need to understand low-level disk layout issues.
The idea of data independence gained popularity in the 70s, both in the area
of programming languages, e.g., with languages such as SETL [
The goal of this presentation is to outline a direction of research that, in
the realm of database and information systems, enables simultaneous high level
abstractions at the user level and extreme flexibility at the physical design level,
that is, in the choice of concrete data structures and their access algorithms.
Indeed, our ultimate goal of this direction of research is to compete with
handwritten code in low-level languages such as C, while providing the high level
of abstraction in the original RM [
Data Independence (through an Example) We begin outlining how data independence can be understood more formally in terms of first-order (relational) signatures and integrity constraints (i.e., firstorder sentences over these signatures). 2.1
The Logical Schema The logical schema is a first order signature SL and an accompanying set of integrity constraints ΣL that are specific to the domain of the application (that require user familiarity). The situation can be depicted as follows: ΣL
SL o ϕ
Logical Schema and User Queries The users interacting with the data use queries, in our case open first order formulae over SL, to formulate their requests (we will deal with modifying the data later in Section 4). There are two important observations that follow from this arrangement: 1. The user only requires familiarity with SL and ΣL to be able to develop applications; and 2. The user can assume that the actual data is a single interpretation on SL that is a model of ΣL over which her requests are evaluated (i.e., without the need to comprehend subtle issues related to logical entailment and/or belief revision). We call such interpretations instances of the schema.
We will use the following logical schema formulated in SQL as our running example.
num INTEGER NOT NULL, name CHAR(20), worksin INTEGER NOT NULL PRIMARY KEY (num), FOREIGN KEY (worksin)
REFERENCES department )
num INTEGER NOT NULL, name CHAR(50), manager INTEGER NOT NULL, PRIMARY KEY (num), FOREIGN KEY (manager)
REFERENCES employee ) The (instances of) employee and department relation declarations are intuitively meant to store information about employee numbers, names and departments they work in, and about departments, their names and managers. In our formalism, this is simply a syntactic sugar for a signature
SL = {employee/3, department/3} (where “/i” indicates predicate arity) and integrity constraints ΣL = { employee(x, y1, z1) ∧ employee(x, y2, z2) → y1 = y2 ∧ z1 = z2, employee(x, y, z) → ∃u, v.department(z, u, v), . . . } stating that employees are identified by their number, that they must work for exactly one department, and so on.
The ability of specifying integrity constraints in ΣL allows one to go beyond what is available in typical implementations of the relational model, for example: – managers are employees that manage a department (a view)
manager(x, y, z) ↔ employee(x, y, z) ∧ ∃u, v.department(u, v, x) – managers work in their own departnemts (business rule)
employee(x, y, z) ∧ department(u, v, x) → z = u – workers and managers partition employees (partition) employee(x, y, z) ↔ (manager(x, y, z) ∨ worker(x, y, z)) manager(x, y, z) ∧ worker(x, y, z) → ⊥ Observe that this extends the signature of the logical schema with additional predicate symbols manager/3 and worker/3 that a user can now reference in queries. 2.2
The Physical Schema We use a similar strategy to define the physical schema where we again use relational signatures and constraints for this purpose. However, these symbols will correspond to actual data structures that are called access paths in database literature. These access paths correspond to various ways to access data, ranging from dereferencing a pointer in main memory or extracting a field from a main memory record (abstracted by binary predicate symbols whose interpretations are address-value pairs) to using main memory data structures such as linked lists (again abstracted by appropriate predicate symbols) to reading data from external storage, and to communicating with other agents. The situation can be again depicted as follows: ΣL ΣP
SL ΣLP
o SA ⊆ SP o (compile) ϕ ψ
Logical Schema and User Queries Physical Schema and Query Plans Note that there can be additional helper predicate symbols in SP in addition to the access paths SA.
There are two issues with this strategy that must be addressed:
1. Will it suffice to associate access paths (data structures and their associated
search algorithms) with predicate symbols?
2. Is it reasonable to also think about generated code using access paths as
formulae (ψ above)?
To address the 1st question, we annotate the symbols in SA with so called binding
patterns [
We illustrate the first issue by defining the physical schema for our running example. Our physical design consists of a linked list of employee records that use pointers (references) to indicate department records an employee works in.
In a similar fashion, the department records use a pointer to indicate which employee is a manager. The records in a Pascal-like notation are as follows: record emp of integer num string name reference dept record dept of integer num string name reference mgr In our formalism this looks as follows: we define the following predicates to be associated with access paths (i.e., in SA): – empfile/1/0: set of addresses of emp records; this access path abstracts navigating a linked list (of emp records) in main memory. – emp-num/2/1: a set of address of emp records paired with the emp numbers; this access path corresponds to extracting a field (num in this case) from an emp record (given an address of such a record). The access paths emp-name/2/1 and emp-dept/2/1 and dept-num/2/1, dept-name/2/1, and dept-mgr/2/1 similarly abstract the field extraction of the remaining fields from the emp and dept records.
We also use two auxiliary predicates emp/1 and dept/1 to stand for the sets of addresses of emp and dept records. Integrity constraints (ΣP ∪ΣLP) then capture the properties of instances of the physical schema and how they relate to the logical schema. For example the fact that records have appropriate fields can be specified as follows: emp(e) → ∃d.emp-dept(e, d) emp records have a dept field emp-dept(e, d1) ∧ emp-dept(e, d2) → d1 = d2 the dept field is functional emp-dept(e, d) → dept(d) the value of the dept field is a pointer to a dept record For full listing of the constraints see Appendix A. This completes our description of the physical schema for our example. 2.3
Queries and Plans
Now we are ready to give an answer to our 2nd question, how to interpret
formulae as query plans. This is straightforward: atomic formulae are mapped to
(the code associated with) access paths and logical connectives and quantifiers
to “control flow code fragments” as follows:
atomic formula 7→
conjunction 7→
existential quantifier 7→
disjunction
negation
7→
7→
access path (a get-first / get-next iterator)
nested loops join
projection (with optional duplicate information)
concatenation
simple complement
For a formula to correspond to a plan (i.e., executable code), it is also necessary
to obey binding patterns [
We illustrate this framework by worked examples of several user queries together with possible query plans for these queries over our running physical design case. Q1: List employee numbers, names, and departments (employee(x, y, z)). We can show that this user query is logically equivalent under the integrity constraints to the following formula over SA: ∃e, d.empfile(e) ∧ emp-num(e, x) ∧ emp-name(e, y)
∧ emp-dept(e, d) ∧ dept-num(d, z) Assuming our formulas as plans mapping, this formula would correspond to the following C-like code (with trivial simplifications and inlining of the ea-xxx(x, y) access paths to y := x->xxx): for e in empfile do x := e->num; y := e->name; d := e->dept; z := d->num; return (x, y, z); Note also that the formula above satisfies the binding patterns associated with the access paths used as it retrieves the address of an emp record before attempting to extract the values of it’s fields.
Q2: List worker numbers and names (∃z.worker(x, y, z)). Again, this query is equivalent to the following formula over SA: ∃e, d.empfile(e) ∧ emp-num(e, x) ∧ emp-name(e, y)
∧ emp-dept(e, d) ∧ ¬dept-mgr(d, e) Note that a negation, ¬dept-mgr(d, e), is required, and that there is no negation in the query nor in the schema that provides any direct clue that it is needed. (We are not aware of any system that can synthesize this plan, that is, that compiles queries using this framwork.) Q3: List all department numbers and their names (∃z.department(x, y, z)). Finding a plan for this query is more difficult since we do not have a direct way to “scan” dept records. However, it is an easy exercise to verify that the following two formulae over SA are logically equivalent to the query: ∃d, e.empfile(e) ∧ emp-dept(e, d)
∧ dept-num(d, x) ∧ dept-name(d, y) (relying on the constraint that “departments have at least one employee”) ∃d, e.empfile(e) ∧ emp-dept(e, d)
∧ dept-num(d, x) ∧ dept-name(d, y) ∧ dept-mgr(d, e) (relying on the constraint that “managers work in their own departments”) Both correspond to plans. However, while the second might seem to be less efficient than the first, a query optimizer should prefer it on the grounds that, in this case, the quantified variables d and e are functionally determined by the answer variable x. Hence, the final projection generated for the second has no need to eliminate duplicate answers. This is not the case for the first of these formulae since it would return a copy of the department information for every employee of the department should duplicate elimination in the final projection not be performed.
Many other problems and issues in physical design and query plans can be
revolved in this framework, including standard RDBMS physical designs (and
more), access to search structures (index access and selection), horizontal
partitioning/sharding, column store/index-only plans, hash-based access to data
(including hash-joins), multi-level storage (aka disk/remote/distributed files),
materialized views, etc., all without any need for coding in C beyond the need
for the generic specifications of get-first / get-next templates for concrete
data structures [
Interpolation and Query Optimization Now we turn our attention to the description of a query compiler/optimizer that, given the logical and physical schemata and a user query, generates a query plan that correctly implements the user request. 3.1
What Queries Make Sense ?? (to users) However, before we begin, it is important to resolve what queries make sense to a user who presumes there is a single interpretation of symbols in SL at any point in time, no matter how it is represented/stored physically. To satisfy to this expectation, the queries that make sense should have the same answer in every model of the overall physical design Σ in which the interpretation of SA is fixed, that is, where the stored data is always the same. This arrangement also guarantees that artifacts facilitating efficient storage and retrieval of information won’t be leaked in the results of queries (since they do not exist in the logical view of the data). The consequence of this observation is that either 1. there are situations in which a seemingly reasonable user query cannot be answered (that would be the case for Q3 in Section 2.3, were the constraint “departments have at least one employee” absent from the schema), or 2. queries must adhere to syntactic restrictions in which, e.g., symbols corresponding to built-in operations cannot be used completely freely, and physical designs must also adhere to syntactic restrictions such as so-called standard designs (i.e., where an access path exists for every logical table in ΣL, thus guaranteeing that every user query can be answered).
To make the definition of sensible queries more formal, we appeal to a well-known
notion of definability:
Proposition 4 (Projective Beth Definability [
We say that ϕ is explicitly definable w.r.t. Σ and L0.
Definability (over SA w.r.t. Σ) formally captures the idea of (physical) data independence, the illusion of a single interpretation of the logical schema that satisfies integrity constraints that is presented to the users, and therefore provides the means of determining which queries can be answered over a particular physical design.
The first question is how to test for definability. The following observation reduces this test to determining whether a particular formula constructed from the user query is entailed by a theory constructed from the schema: ϕ is explicitly definable (w.r.t. Σ and over SA) if and only if Σ ∪ Σ0 |= ϕ → ϕ0 (1) where Σ0 (ϕ0) is Σ (ϕ) in which symbols NOT in SA are primed, respectively.
The next question is how to find a plan for a given query. Our observations
on how formulae can be interpreted as query plans in Section 2.3 then mostly
reduces query compilation to a search for the formula ψ in Proposition 4(2). To
find ψ, we rely on a variant of the following result [
If Σ ∪ Σ0 |= ϕ → ϕ0 then there is ψ s.t. Σ ∪ Σ0 |= ϕ → ψ → ϕ0
where L(ψ) ⊆ L(SA). Here, ψ is called the Craig interpolant. Moreover, we can
extract any such ψ from a Tableau proof of (1) in linear time [
Architecture
The above discussion might seem to solve the query compilation problem.
However there are additional issues that need to be addressed:
1. The search for interpolants and their implied query plans must consider
that alternative but logically equivalent plans might have vastly different
performance characteristics.1 Hudek et al. [
In this section, we sketch how the problem of compiling updates on a logical design can be translated to the problem of compiling queries on a related logical design, thus enabling the same framework above to also be used to compile inserts, updates and deletes on logical tables.
As already mentioned in Section 2.1, user updates are formulated with respect to the logical schema (SL and ΣL). Moreover, physical data independence presents the user with a illusion that he is modifying an instance of SL by adding/removing ground tuples to/from the interpretations of symbols in SL. This process can be formalized in three parts as follows: 1. For every symbol R ∈ SL, introduce two additional symbols, R+ and R−, whose (disjoint) interpretations correspond to the ground tuples the user wants to add or remove to/from the current instance; 2. The updated instance is then defined by executing an simultaneous assignments R := (R ∪ R+) − R− for all R ∈ SL; and 3. At the end of the assignment the new interpretation must be a model of ΣL. The symbols R+ and R− are commonly called the delta relations and Part 3 of this process on user updates ensures so-called consistency preserving transactions. formulae
To convert the update problem to the problem of synthesizing plans for queries, consider two copies of the schema Σ, in which all symbols are superscripted by o and n
, respectively. The intuition is that the o and n symbols correspond to the interpretations of SL before and after the update. The actual assignment (Part 2 of the above process) can be then captured as additional
Ro(x) ∨ R−(x) ↔ Rn(x) ∨ R+(x) for each R ∈ SL as depicted below.
Σo
L ΣPo
S o
L ΣLoP SA ⊆ SP o
U+,U− compile
A+,A− Σn
L ΣPn In the same way, the changes to access paths in SA can be captured by analogous constraints, as depicted in the lower half of the figure. Thus, user inserts, updates and deletes on logical tables (comprising a transaction) are mapped to a definability question of the following form:
SA and of all delta relations for SL? Is An (or A+, A−) definable in terms of Aio and Uj+, Uj− (user updates) for every access path A ∈ SA, given the instance of all access paths in A positive answer to this question yields a update plan that applies the delta relations corresponding to the access paths to their current interpretations. 5
We have outlined how projective Beth definability can be used in database and information systems to facilitate physical data independence. Moreover, we have shown how a variation on Craig interpolation can be used to compile and optimize user queries and user updates that are formulated over a logical schema to an executable plan over a fine-grained physical design. There are many avenues for further research and development, including: (1) admitting more powerful languages for user requests, such as languages with aggregation; (2) enhancements to the tableau provers, as well as alternatives such as superposition-based provers; and (3) improvements to the planning component of query compilation responsible for exploring the search space of alternative query plans.
A
Constraints for the Running Example The following listing is a complete specification of constraints needed for our running example. Note that some of the constraints in Section 2.1 are entailed by the constraints below (and are thus omited). % % logical schema (entailed constraints omited) % % a (virtual) view for managers manager(x,y,z) <-> (employee(x,y,z) and ex(n,department(z,n,x))), % % disjoint partition of employees to managers and workers employee(x,y,z) <-> (manager(x,y,z) or worker(x,y,z)), manager(x,y,z) and worker(x,u,v) -> bot, % % businness logic: managers work for their own departments (department(x,y,z) and employee(z,u,w)) -> x=w, % % physical schema and mappings % % design of emp and dept structs; emp/dept addresses, fields functional emp(e) -> ex(y,emp_num(e,y)), emp_num(e,y) and emp_num(e,z)-> y=z, emp_num(y,x) and emp_num(z,x)-> y=z, emp(e) -> ex(y,emp_name(e,y)), emp_name(e,y) and emp_name(e,z)-> y=z, emp(e) -> ex(y,emp_dept(e,y)), emp_dept(e,y) and emp_dept(e,z)-> y=z, emp_dept(e,d) -> dept(d), % dept(d) -> ex(y,dept_num(d,y)), dept_num(d,y) and dept_num(d,z)-> y=z, dept_num(y,x) and dept_num(z,x)-> y=z, dept(d) -> ex(y,dept_name(d,y)), dept_name(d,y) and dept_name(d,z)-> y=z, dept(d) -> ex(y,dept_mgr(d,y)), dept_mgr(d,y) and dept_mgr(d,z)-> y=z, dept_mgr(d,e) -> emp(e),