Dependencies have played a significant role in database design for many years. They have also been shown to be useful in query optimization. In this paper, we discuss the new type of dependency for polarized lexicographically ordered sets of tuples. We introduce formally the concept of polarized order dependencies (PODs). We discuss their potential significance for database systems, and present a chase procedure for testing logical implication for them.
select year, quarter, month, sales from Sales s, Dates d where s.date_id = d.date_id group by year, quarter, month, sales order by year asc, quarter asc, month asc, sales desc In the schema, Dates is a dimension table with a row per day, and Sales is a large fact table recording all individual sales. The column date_id is the primary key for Dates, each row describes a given day with explicit columns as year, quarter, month, and day that describe the natural date values.
Of course, quarter is logically redundant in the group by, as month (which
follows it in the group by) functionally determines quarter. (First quarter
encompasses the months of January, February, and March, second quarter, the months
of April, May, and June, and so forth.) The query’s author could not leave quarter
out of the group by, because it is stated in the select. The query optimizer could,
however, remove quarter to accomplish the group by on year, quarter,
month, sales if it recognizes that year, month and year, quarter, month offer
the same partition. This is done by query optimizers today – given the functional
dependency (FD) information that month → quarter is available to the optimizer
– by rewrite [
For the query above, the rewrite might still not be applied, however since the query also specifies the answers to be ordered by year asc, quarter asc, month asc, sales desc. The FD that month → quarter is not logically sufficient to eliminate quarter from the order by, as it was to eliminate it from the group by. To see that the functional dependency does not suffice to eliminate quarter from the order by, imagine the values for quarter were the strings first, second, third, and fourth. Data would be lexicographically ordered as first, fourth, second, then third! Of course, we intend that values of quarter are, say, 1, 2, 3, and 4, so the data would order naturally as by date. It is unfortunate, then, that quarter is, in fact, redundant (in this query) in the order by also, but that the optimizer does not have the means to eliminate it. What is missing is the semantic information that month asc orders quarter asc, which is more than just that month functionally determines quarter. This states that as values rise from one tuple to another on month, they must rise, or stay the same, from the one tuple to the other on quarter (that is, the values do not descend from the one tuple to the other on quarter). The order by criteria can be a mix of asc and desc (as in Example 1). With this generalization we call it polarized order dependencies (POD). As best we know, polarized order dependencies have not been studied before.
Our objective is to bring a reasoning about PODs into the query optimizer. A query
plan for the query above could then eliminate quarter from both the order by
and the group by clauses. We are interested in PODs because polarized
(asc/desc) lexicographical orders are part of SQL via order by, and it is how
ordered tuple streams in a query are ordered. Therefore, PODs could be used to great
effect in query optimization. A first question for any class of a dependencies is the
inference problem: when does one POD logically follow from a collection of
prescribed PODs? In this paper, we present a chase procedure for testing logical
implication for PODs. Chase is a fixpoint algorithm enforcing satisfaction of data
dependencies in databases [
Outline. Section 2 provides background with our notational conventions and definitions. We motivate PODs, and discuss practical applications of them. The core of the paper is in Section 3, where we devise a chase procedure for testing logical implication. Related work is presented in Section 4. In Section 5, we make concluding remarks and discuss future work.
We adopt the notational conventions below. We consider a relation over the set of attributes . Let be an arbitrary table instance over ; thus, a set of tuples over ’s schema with attributes . We assume a column (#) in R that takes a unique value per tuple, without loss of generality. This alleviates any need to work with a table instance as bags of tuples; we consider them as sets. This also removes the possibility that we might “lose” a row from r when we modify the value of one of its columns (besides #), since # will still distinguish it from other tuples. Our notational conventions are as follows.
• Relations. A capital letter in bold italics represents a relation: R. Capital letters represent single attributes: A, B, C. A small letter in bold represent a relational instance: r. Tuples are marked with small letters in italics: s, t. • Sets. Calligraphic letters stand for sets of attributes: , , . Proximity is used for union of sets: is shorthand for ∪ . Likewise, A or A, where is a set of attributes and A is a single attribute, stands for ∪ {A}. AB denotes {A, B}. • Lists. Bold letters stand for lists of attributes: , , . Note that list X could be the empty list, []. Square brackets denote a list: [A, B, C]. The notation [A | Z] denotes that A is the head of the list, and Z is the tail of the list, the remaining list with the first element removed. Proximity is used for concatenation of lists of attributes: is shorthand for ∘ . Likewise, A and A stands respectively for [A] ∘ and ∘ [A], where is list of attributes and A is a single attribute. AB denotes [A, B]. 2.1
We consider ascending (asc) and descending (desc) order in the lexicographical ordering. (This is part of the SQL’s standard). This also includes mixing of asc and desc (e.g., order by X desc, Y asc). Our work can be also easily extended to use of functions in the order directives (e.g., order by -1*X asc, Y asc).
Definition 1. (marked attributes) For each attribute A, the marked attributes of A are the formal symbols A and A.
Marked attributes are used in the following way, giving us a polarization of attributes.
Definition 2. (operator ≼ and operator ≺ ) Let L be a list of marked attributes, s and t be two tuples in relation instance r. Operator ≼ is defined as follows: ! ≼ "! where L = [H | Z] if (H is of the form A and # < "#) or if (H is of the form A and # > "#) or if (( # = "#) and (Z = [] or ≼ " )) Operator ≺ is defined as follows: ≺ " iff ≼ " and " ⋠ .
We are now ready to define polarized order dependency.
Definition 3. (polarized order dependency) Let X and Y be a list of marked attributes. Call ↦ a polarized order dependency over the relation iff, for every pair of permissible tuples s and t in relation instance over , ≼ " implies ≼ " . and
Whenever ↦ , we say that ↦ . We denote this by
orders . ↔ .
and are order equivalent iff ↦ # s t
The order of the attributes for FDs is not important. For PODs only particular permutations of attributes may hold as dependencies because they are built on lists. The order of the attributes is important as well as how they are polarized. PODs are prescriptive statements on the relation, as are FDs. That is, they can be used as a type of integrity constraint to prescribe which instances are admissible.
EXAMPLE 2. Let r be a relation instance over with attributes {A, B, C, D, E} as shown in Table 1. Note ⊨ ACD ↦ EB but ⊭ ACD ↦ BE. Furthermore, ⊨ CA ↦ BDE but ⊭ CA ↦ EBD.
There is a relationship between PODs and FDs. We show that every POD infers a FD.
THEOREM 1. (relationship between PODs and FDs) For every instance r of relation R, if r satisfies OD ↦ , then r satisfies FD → (in which is the set of attributes in X, and in Y).
PROOF. Let s, t ∈ r, such that definition of POD ≼ " and " ≼ = " . Therefore, as ↦
≼ " and " ≼ is given, hence = " .
. By the THEOREM 2. (FD/POD correspondence) For every instance r of relation R, r ⊨ → iff r ⊨ ↦ , for all lists that order the attributes of and all lists likewise for .
PROOF. (IF) If flexivity, → true. (ONLY IF) If ↦ does not hold, there exists s, t ∈ r, such that ⋠PL " . This implies that = " and " ≺PL . Therefore ≠ " and → is not true.
↦ , then → by Theorem 1. By Armstrong’s axiom Reholds. Therefore, by Armstrong’s axiom Transitivity, → is ≼PL " but = " , The concept of functional dependencies has come to have profound importance in databases, especially in schema design. While functional dependencies are a simple Note that the weakening rule FDs and PODs are distinct. 2.2
PODs in Databases ↦ implies ↦
does not hold and as such,
notion in some ways, reasoning over them is, somewhat surprisingly, not nearly as
simple. To gain insight into how sets of FDs behave, and to simplify the reasoning
process over them, Armstrong provided an axiomatization for them [
We have introduced PODs in analogy to FDs: FDs are to group by as PODs are to order by. Order plays pivotal roles on the physical side, in the physical database and in query optimization. Data is often stored sorted by a clustered (tree) index’s key. In a query plan, an operator that takes as input the output stream of another operator can benefit in cases when the stream is sorted in a particular way. Given POD ↦ , if one has an SQL query with order by , one can rewrite the query with order by instead, and meet the intent of the original query. However, the rewritten query is not semantically equivalent to the original (unless ↔ )! One could not legally rewrite the query with order by with order by instead. Strengthening the order by conditions is permitted, but weakening them is not. (This is true too inside query plans for ordered tuple streams.)
A POD can be declared as an integrity constraint to prescribe which instances are admissible. If one knows a collection of PODs, ℳ – declared as integrity constraints over relation – one might soundly infer additionally PODs that must be true for and use them for query optimization. For example, if ↦ and ↦ are true, then ↦ is true also.
Polarized order dependencies are not just limited to the time domain as used in Example 1, however. They arise naturally in many other domains from the real-world semantics associated with given data. Consider Example 3, which concerns taxes.
EXAMPLE 3. Consider a table Taxes that includes columns for taxable income, tax bracket, and taxes on the income. The tax brackets are based on the level on income (the values of the tax brackets are: A, B, C, D and decrease with income level). Assume taxes go up with income. Then, from [ income] ↦ [ bracket ] and [income] ↦ [taxes] it follows that [income] ↦ [bracket, taxes]. Assume the table has a tree (clustered) index on income. Given a query on the table with an order by on bracket desc, taxes asc, with the POD above, it could be evaluated using the index on income (for order by income asc), avoiding potentially an expensive sorting operation.
Instead of being columns with explicit data, bracket and taxes could be derived
by functions or case expressions – say, if Taxes were a view – or generated columns
in the table. In these cases, it would be possible for the database system to derive the
polarized order dependency constraints above automatically. In [
In [
By recognizing that a tuple stream ordered with respect to some criteria is
equivalently ordered with respect to other criteria, a sort on input can be removed for a
sortmerge join. Order by and group by operators can be satisfied with no need for a
sorting or partitioning operation more often. Likewise, as the distinct operator is
exchangeable with group by, the need for a sorting or partitioning operation to
satisfy distinct can be lessened. In [
A goal in any dependency theory is to develop algorithms for testing logical implication; that is, testing whether a dependency is satisfied based on a given set of dependencies. In this section, we show how to test logical implication for PODs using chase procedure.
Definition 4. (equalize) Let s and t be two tuples in relation instance r, and let A be a single attribute. Also let x = min( #, "#). The operation equalize(r, A, s, t) returns a relational instance r', with s and t modified in r so # = x and "# = x.
EXAMPLE 4. Consider Table 2 and Table 3 as an example of an operation equalize.
Definition 5. (chase rules) Let s and t be two tuples in relation instance r, and let X and Y be lists of marked attributes such that X ↦ Y is falsified in r ( ≼ " but ⋠ " ), let A be the first attribute in X such that # ≠ "# (if such an attribute A exists) and let B be first attribute in Y such that "B ≠ B . Two chase rules are defined. • Split rule: If = " , then r' = equalize(r, B, s, t). • Swap rule: If # ≠ "# and B ≠ "B , then r' = equalize(r, B, s, t).
EXAMPLE 5. Let ℳ = {A ↦ BC, B ↦ C} and let r be an instance over R with attributes {A, B, C}. From Table 4 to Table 5 demonstrates an example of applying the split rule (A ↦ BC is falsified in r in Table 4). From Table 5 to Table 6 demonstrates applying the swap rule (B ↦ C is falsified in r' in Table 5).
Let ℳ be a set of prescribed PODs, and let r = {"C, … , "E} be an instance relation over R. The chase algorithm is as follows.
Current := r;
Previous := {}; //empty instance while Current ≠ Previous {
Previous := Current; if (∃ t,s ∊ Current, ∃ X ↦ Y in ℳ such that ≼ " but t ⋠ " ) { Apply one of the chase rules (split or swap from Definition 5) to s and t, assigning the table which is returned from equalize operation to Current. } } return Current;
EXAMPLE 6. Let ℳ = {A ↦ BC, B ↦ C} be a set of PODs and r an instance over R with attributes {A, B, C}. The sequence from Table 4, Table 5, to Table 6 is an example of applying Algorithm 1 (chase(r, ℳ)) to r as in Table 4. In Table 6, there is no s and t that matches (as in step 5 of Algorithm 1), so the procedure terminates with it.
PROOF. Consider a given relational instance r, and any relational instance s, over schema R. Without loss of generality let all values in r and s be zero or greater. Let ∑L be the sum of all the values of all the columns in s. Let there be an applicable chase rule – split or swap – on s with respect to ℳ, and s' be the result of its application. Instance s' has the same number of rows as s. Also ∑LM < ∑L as the equalize replaced a value in some column of some row by a smaller value. (Note that equalize does not introduce new values.) Zero is the lower bound on the ∑LM. As a chase procedure is a finite sequence of such transformations starting with r, it must terminate. # s t u
The remaining step is to show that the resulting table of Algorithm 1 satisfies a set of PODs ℳ. The instance chase(r, ℳ) satisfies ℳ as no split or swap with respect to ℳ applies. If not the chase procedure would not have terminated at that point. □
THEOREM 3. Let relation instance r be over R and let ℳ be a set of PODs. Then r ⊨ ℳ iff r = chase(r, ℳ).
PROOF. (IF): If any split or swap applies to table instance s with respect to ℳ, for the resulting s', ∑LM < ∑L. Then clearly s ≠ s'. Thus r = chase(r, ℳ) if no swap or split applies, meaning r ⊨ ℳ. (ONLY IF): From Definition 5 it follows that chase rules split or swap are only used if it breaks a dependency in ℳ. □ Let us define a table template.
Definition 6. (table template) Let R be relation schema with n attributes and m be a POD ↦ , where list of marked attributes contains attributes [XC, … , XP ]. A table template for a POD m, denoted as Q, is a table consisting of two tuples s and t, such that is either equal to R or S, for j in 1,..., k. In R and S, symbols pT and qT represents one of the following three cases, where the ordering of variables bT and tT is defined as bT < tT: # s t a) b) c) XC bC bC pT = bT and qT = bT, pT = bT and qT = tT, pT = tT and qT = bT.
Definition 7. (mapping Q to ö( Q)) Let Q be a table template from Definition 6. A mapping of Q to ö( Q) is any instance with values that satisfy the ordering from Definition 6.
EXAMPLE 7. Consider Table 9 as one of possible mappings from Definition 7. (In fact it can be any relation instance which satisfies the Definition 6 of ordering of variables).
PROOF. The proof follows directly from Theorem 3 by replacing Q with r and applying chase rules split and swap on variables bT, tT using ordering defined in Definition 6. □ LEMMA 3. Let Q be a table template from Definition 6 and ö( Q) be mapping from Q (Definition 7). Then Q ⊨ X ↦ Y iff ö( Q) ⊨ X ↦ Y.
PROOF. The proof follows from the definition of ordering of variables in Definition 6. Since ordering of values in ö( Q ) corresponds with ordering of variables in Q respectively (Definition 7). □
Definition 8. (tableaux c Q) Let m be a POD X ↦ Y. We define c Q to be the set of all table templates Q, as defined in Definition 6.
Note that c Q is not just a single table template. It is a set of table templates (each consisting of two rows). The chase of c Q is defined as follows.
Definition 9. (chase of tableaux c Q) The chase of c Q over a set of PODs ℳ, denoted as CHASEc f ,ℳ is defined by CHASEc f ,ℳ = {chase( Q, ℳ) | Q ∊ c Q }. CHASEc f ,ℳ satisfies X ↦ Y, denoted by CHASEc f ,ℳ⊨ X ↦ Y, if, for all Q ∊ c Q, chase( Q, ℳ) ⊨ X ↦ Y. CHASEc f ,ℳ satisfies ℳM denoted by CHASEc f ,ℳ ⊨ ℳ', if for all X ↦ Y ∊ ℳ', CHASEc f ,ℳ⊨ X ↦ Y.
THEOREM 4. (chase procedure for PODs is sound and complete) Let ℳ be a set of PODs over R and m be a POD X ↦ Y. Then ℳ ⊨ X ↦ Y iff CHASEc f ,ℳ ⊨ X ↦ Y.
PROOF. (IF): Assume CHASEc f ,ℳ ⊭ X ↦ Y. By Definition 9, there exists Q ∊ c Q, such that chase( Q, ℳ) ⊭ X ↦ Y. Note chase( Q, ℳ) ⊨ ℳ, by Lemma 1. Hence, there is a mapping ö to generate a relation instance ö(chase( Q, ℳ)) and by Lemma 3, ö(chase( Q, ℳ)) ⊨ ℳ, but ö(chase( Q, ℳ)) ⊭ X ↦ Y. This implies that ℳ ⊭ ↦ because we have found a relation instance which satisfies ℳ but does not satisfy ↦ . Therefore, if ℳ ⊨ X ↦ Y then CHASEc f ,ℳ ⊨ X ↦ Y. (ONLY IF): Assume CHASEc f ,ℳ⊨ ↦ . Let s, t be any two tuples in any relation r such that ≼ " and satisfying ℳ. We would like to present that ≼ " . Let Q ∊ c Q, let Q = {p, q} be the template relation such that ö(p) = s and ö(q) = t. It is possible always to find such a pair of tuples Q since c Q considers all possibilities of two tuples which satisfy the condition ≼ " . Therefore, we have ö( Q) = {s, t} and ö( Q ) ⊨ ℳ . By Lemma 3, it follows that Q ⊨ ℳ . Therefore, it follows by Lemma 2 that Q = chase( Q, ℳ). Since we have assumed that CHASEc f ,ℳ⊨ ↦ , we have chase( Q , ℳ ) ⊨ ↦ . As ö ( Q ) = ö (chase( Q , ℳ )), it implies that ö( Q) ⊨ ↦ by Lemma 3. So ≼ " . Hence, if CHASEc f ,ℳ ⊨ X ↦ Y, then ℳ ⊨ X ↦ Y. □ THEOREM 5. (decidable) The implication problem of the PODs is decidable.
PROOF. Testing implication problem of the PODs is decidable as the chase procedure is a sound and complete inference algorithm for PODs (Theorem 4). □
THEOREM 6. (complexity of chase procedure for PODs) The complexity of building templates is exponential for the PODs chase procedure.
PROOF. According to Definition 6 there are 3hZP templates for R and 3hZS templates for each, S . Therefore there are 3hZP + (3hZP +…3hZC ) templates in total. Because (3hZP +…+ 3hZC ) is geometric progression this can be simplified to the form 3hZP + 3hZP (1 - 3P )/(1-3) which is equal to (3h + 3hZP )/2. So the complexity of building the templates is shown to be O(3E ). □ 4
Ordered sets and lattices have been a subject of research in mathematics. Our
concept of polarized order dependency is equivalent to order-preserving mappings
between ordered sets [
Order dependencies were introduced for the first time in the context of database
systems in [
Dependencies defined over lexicographically ordered domains were introduced in
[
Sorting is at the heart of many database operations: for instance sort-merge join,
index generation, duplicate elimination and ordering the output through the SQL
order by operator. The importance of sorted sets for query optimization and
processing has been recognized very early on. The query optimizer of System R [
throughout the process of query optimization. In more recent work, [
While order of tuples is purposely excluded in the relational model – an answer to a query is a set of tuples – order plays a vital role in the evaluation of queries and in real-world query languages as SQL with order by. (In other data/query models, order is part of semantics, as for XML/XQuery.) We provide a sound and complete chase procedure for the inference problem for PODs. The goal of this work was to develop a theory behind dependencies over polarized lexicographically ordered sets. To the best of our knowledge, this is the first attempt to develop a procedure for testing logical implication for PODs. We explored some correspondence between FDs and PODs. The story of PODs is not over. We plan next to pursue the following. •
We would like to extend our work for all-ascending order dependencies [
Acknowledgments. We thank Calisto Zuzarte and Wenbin Ma from IBM laboratory in Toronto for their encouragement and helpful suggestions throughout the project. 6