41 lines
2.6 KiB
TeX
41 lines
2.6 KiB
TeX
%root: main.tex
|
|
|
|
\paragraph{Outline of 1st ICDT Introduction Submission}
|
|
|
|
\begin{outline}[enumerate]
|
|
\1 Problem Introduction and Background
|
|
\2 Set-\abbrPDB notation, concepts, common (known) results \isIncluded{I. B. vi.}
|
|
\3 \notIncluded{Dichotomy} \isIncluded{Can be included in I. B. vi.}
|
|
\3 Exact Computation \sharpphard \isIncluded{I. B. vi.}
|
|
\2 Formal definition of expected result multiplicity \isIncluded{Can be included in I. C. ii. a.}
|
|
\2 \notIncluded{Example} \isIncluded{Can be used potentially sometime after I. C. ii. a.; maybe around D.}
|
|
\3 Assumed setting of {\emph set inputs} \isIncluded{I. D.}
|
|
\3 \notIncluded{Example based on explaining and motivating formal definition of expected result multiplicity}
|
|
\1 \notIncluded{Discussion of set-\abbrPDB\xplural} \isIncluded{Perhaps this might be useful around I. B. vi.}
|
|
\2 \notIncluded{Lineage from PosBool$[\vct{X}]$}
|
|
\2 \notIncluded{Encoding of possible worlds via $\vct{X}$}
|
|
\2 \notIncluded{Computing probability can be done using only the lineage}
|
|
\1 \notIncluded{Discussion of bag-\abbrPDB\xplural} \isIncluded{Might be useful around I. C.}
|
|
\2 \notIncluded{Link to $\domN[\vct{X}]$}
|
|
\2 \notIncluded{Link to computing the expected count of a lineage polynomial}
|
|
\2 \notIncluded{Example to illustrate computing an expected count over a lineage polynomial}
|
|
\1 \isIncluded{Computing expected multiplicity for an \abbrSOP representation versus a factorized representation -- I. B. iii. and I. B. iv.}
|
|
\2 Linear for \abbrSOP
|
|
\2 Introduce the problem by asking if it's linear in the size of the representation for factorized representation produced by such query optimizations as projection push-down.
|
|
\2 State our theoretical results (informally) that it is not linear in general
|
|
\1 \notIncluded{Contributions}
|
|
\2 \notIncluded{Hardness results for the expected multiplicity problem}
|
|
\3 \notIncluded{Reduction to counting $\kElem$-matchings}
|
|
\2 \isIncluded{Introduce our approximation algorithm and its guarantees -- I. B. v.}
|
|
\2 \notIncluded{Generalization to bag-\abbrPDB\xplural}
|
|
\2 \notIncluded{Result over $\raPlus$ queries }
|
|
\2 \isIncluded{Higher moments I. C. e.}
|
|
\1 \notIncluded{Overview of our techniques}
|
|
\2 \notIncluded{Informal introduction to $\rpoly$ with example}
|
|
\2 \notIncluded{Definition of reduced polynomial}
|
|
\2 \notIncluded{Equivalence of $\rpoly$ and computing $\expct$}
|
|
\2 \notIncluded{Further details into the technique of obtaining our hardness result}
|
|
\1 \notIncluded{Paper organization}
|
|
\2 \notIncluded{Also includes evaluation semantics figure}
|
|
\end{outline}
|