#758

Committed 04 Sep 2023 08:37PM UTC coverage: 0.0% (-78.3%) from 78.333%

Build # #758

Build Type

push

circle-ci

Committed by

hershd23

Commit Message

Increased underline length in at line 75 in text_summarization.rst
	modified:   docs/source/benchmarks/text_summarization.rst

Run Details

0 of 11303 relevant lines covered (0.0%)

0.0 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/evadb/expression/expression_utils.py

# coding=utf-8
# Copyright 2018-2023 EvaDB
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

from typing import List, Set

from evadb.expression.abstract_expression import AbstractExpression, ExpressionType
from evadb.expression.comparison_expression import ComparisonExpression
from evadb.expression.constant_value_expression import ConstantValueExpression
from evadb.expression.logical_expression import LogicalExpression
from evadb.expression.tuple_value_expression import TupleValueExpression


def to_conjunction_list(
    expression_tree: AbstractExpression,
) -> List[AbstractExpression]:
    """Convert expression tree to list of conjunctives

    Note: It does not normalize the expression tree before extracting the conjunctives.

    Args:
        expression_tree (AbstractExpression): expression tree to transform

    Returns:
        List[AbstractExpression]: list of conjunctives

    Example:
        to_conjunction_list(AND(AND(a,b), OR(c,d))): [a, b, OR(c,d)]
        to_conjunction_list(OR(AND(a,b), c)): [OR(AND(a,b), c)]
            returns the original expression, does not normalize
    """
    expression_list = []
    if expression_tree.etype == ExpressionType.LOGICAL_AND:
        expression_list.extend(to_conjunction_list(expression_tree.children[0]))
        expression_list.extend(to_conjunction_list(expression_tree.children[1]))
    else:
        expression_list.append(expression_tree)

    return expression_list


def conjunction_list_to_expression_tree(
    expression_list: List[AbstractExpression],
) -> AbstractExpression:
    """Convert expression list to expression tree using conjunction connector

    [a, b, c] -> AND( AND(a, b), c)
    Args:
        expression_list (List[AbstractExpression]): list of conjunctives

    Returns:
        AbstractExpression: expression tree

    Example:
        conjunction_list_to_expression_tree([a, b, c] ): AND( AND(a, b), c)
    """
    if len(expression_list) == 0:
        return None
    prev_expr = expression_list[0]
    for expr in expression_list[1:]:
        if expr is not None:
            prev_expr = LogicalExpression(ExpressionType.LOGICAL_AND, prev_expr, expr)
    return prev_expr


def extract_range_list_from_comparison_expr(
    expr: ComparisonExpression, lower_bound: int, upper_bound: int
) -> List:
    """Extracts the valid range from the comparison expression.

    The expression needs to be amongst <, >, <=, >=, =, !=.

    Args:
        expr (ComparisonExpression): comparison expression with two children
            that are leaf expression nodes. If the input does not match,
            the function return False
        lower_bound (int): lower bound of the comparison predicate
        upper_bound (int): upper bound of the comparison predicate

    Returns:
        List[Tuple(int)]: list of valid ranges

    Raises:
        RuntimeError: Invalid expression

    Example:
        extract_range_from_comparison_expr(id < 10, 0, inf): True, [(0,9)]
    """

    if not isinstance(expr, ComparisonExpression):
        raise RuntimeError(f"Expected Comparison Expression, got {type(expr)}")
    left = expr.children[0]
    right = expr.children[1]
    expr_type = expr.etype
    val = None
    const_first = False
    if isinstance(left, TupleValueExpression) and isinstance(
        right, ConstantValueExpression
    ):
        val = right.value
    elif isinstance(left, ConstantValueExpression) and isinstance(
        right, TupleValueExpression
    ):
        val = left.value
        const_first = True
    else:
        raise RuntimeError(
            f"Only supports extracting range from Comparison Expression \
                with two children TupleValueExpression and \
                ConstantValueExpression, got {left} and {right}"
        )

    if const_first:
        if expr_type is ExpressionType.COMPARE_GREATER:
            expr_type = ExpressionType.COMPARE_LESSER
        elif expr_type is ExpressionType.COMPARE_LESSER:
            expr_type = ExpressionType.COMPARE_GREATER
        elif expr_type is ExpressionType.COMPARE_GEQ:
            expr_type = ExpressionType.COMPARE_LEQ
        elif expr_type is ExpressionType.COMPARE_LEQ:
            expr_type = ExpressionType.COMPARE_GEQ

    valid_ranges = []
    if expr_type == ExpressionType.COMPARE_EQUAL:
        valid_ranges.append((val, val))
    elif expr_type == ExpressionType.COMPARE_NEQ:
        valid_ranges.append((lower_bound, val - 1))
        valid_ranges.append((val + 1, upper_bound))
    elif expr_type == ExpressionType.COMPARE_GREATER:
        valid_ranges.append((val + 1, upper_bound))
    elif expr_type == ExpressionType.COMPARE_GEQ:
        valid_ranges.append((val, upper_bound))
    elif expr_type == ExpressionType.COMPARE_LESSER:
        valid_ranges.append((lower_bound, val - 1))
    elif expr_type == ExpressionType.COMPARE_LEQ:
        valid_ranges.append((lower_bound, val))
    else:
        raise RuntimeError(f"Unsupported Expression Type {expr_type}")
    return valid_ranges


def extract_range_list_from_predicate(
    predicate: AbstractExpression, lower_bound: int, upper_bound: int
) -> List:
    """The function converts the range predicate on the column in the
        `predicate` to a list of [(start_1, end_1), ... ] pairs.

        It assumes the predicate contains conditions on only one column.
        It is the responsibility of the caller that `predicate` does not contains conditions on multiple columns.

    Args:
        predicate (AbstractExpression): Input predicate to extract
            valid ranges. The predicate should contain conditions on
            only one columns, else it raise error.
        lower_bound (int): lower bound of the comparison predicate
        upper_bound (int): upper bound of the comparison predicate

    Returns:
        List[Tuple]: list of (start, end) pairs of valid ranges

    Example:
            id < 10 : [(0, 9)]
            id > 5 AND id < 10 : [(6, 9)]
            id < 10 OR id >20 : [(0, 9), (21, Inf)]
    """

    def overlap(x, y):
        overlap = (max(x[0], y[0]), min(x[1], y[1]))
        if overlap[0] <= overlap[1]:
            return overlap

    def union(ranges: List):
        # union all the ranges
        reduced_list = []
        for begin, end in sorted(ranges):
            if reduced_list and reduced_list[-1][1] >= begin - 1:
                reduced_list[-1] = (
                    reduced_list[-1][0],
                    max(reduced_list[-1][1], end),
                )
            else:
                reduced_list.append((begin, end))
        return reduced_list

    if predicate.etype == ExpressionType.LOGICAL_AND:
        left_ranges = extract_range_list_from_predicate(
            predicate.children[0], lower_bound, upper_bound
        )
        right_ranges = extract_range_list_from_predicate(
            predicate.children[1], lower_bound, upper_bound
        )
        valid_overlaps = []
        for left_range in left_ranges:
            for right_range in right_ranges:
                over = overlap(left_range, right_range)
                if over:
                    valid_overlaps.append(over)
        return union(valid_overlaps)

    elif predicate.etype == ExpressionType.LOGICAL_OR:
        left_ranges = extract_range_list_from_predicate(
            predicate.children[0], lower_bound, upper_bound
        )
        right_ranges = extract_range_list_from_predicate(
            predicate.children[1], lower_bound, upper_bound
        )
        return union(left_ranges + right_ranges)

    elif isinstance(predicate, ComparisonExpression):
        return union(
            extract_range_list_from_comparison_expr(predicate, lower_bound, upper_bound)
        )

    else:
        raise RuntimeError(f"Contains unsupported expression {type(predicate)}")


def get_columns_in_predicate(predicate: AbstractExpression) -> Set[str]:
    """Get columns accessed in the predicate

    Args:
        predicate (AbstractExpression): input predicate

    Returns:
        Set[str]: list of column aliases used in the predicate
    """
    if isinstance(predicate, TupleValueExpression):
        return set([predicate.col_alias])
    cols = set()
    for child in predicate.children:
        child_cols = get_columns_in_predicate(child)
        if len(child_cols):
            cols.update(child_cols)
    return cols


def contains_single_column(predicate: AbstractExpression, column: str = None) -> bool:
    """Checks if predicate contains conditions on single predicate

    Args:
        predicate (AbstractExpression): predicate expression
        column_alias (str): check if the single column matches
            the input column_alias
    Returns:
        bool: True, if contains single predicate, else False
            if predicate is None, return False
    """

    if not predicate:
        return False

    cols = get_columns_in_predicate(predicate)
    if len(cols) == 1:
        if column is None:
            return True
        pred_col = cols.pop()
        if pred_col == column:
            return True
    return False


def is_simple_predicate(predicate: AbstractExpression) -> bool:
    """Checks if conditions in the predicate are on a single column and
        only contains LogicalExpression, ComparisonExpression,
        TupleValueExpression or ConstantValueExpression

    Args:
        predicate (AbstractExpression): predicate expression to check

    Returns:
        bool: True, if it is a simple predicate, else False
    """

    def _has_simple_expressions(expr):
        simple = type(expr) in simple_expressions
        for child in expr.children:
            simple = simple and _has_simple_expressions(child)
        return simple

    simple_expressions = [
        LogicalExpression,
        ComparisonExpression,
        TupleValueExpression,
        ConstantValueExpression,
    ]

    return _has_simple_expressions(predicate) and contains_single_column(predicate)

1	# coding=utf-8
2	# Copyright 2018-2023 EvaDB
3	#
4	# Licensed under the Apache License, Version 2.0 (the "License");
5	# you may not use this file except in compliance with the License.
6	# You may obtain a copy of the License at
7	#
8	# http://www.apache.org/licenses/LICENSE-2.0
9	#
10	# Unless required by applicable law or agreed to in writing, software
11	# distributed under the License is distributed on an "AS IS" BASIS,
12	# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	# See the License for the specific language governing permissions and
14	# limitations under the License.
15
16	from typing import List, Set	×
17
18	from evadb.expression.abstract_expression import AbstractExpression, ExpressionType	×
19	from evadb.expression.comparison_expression import ComparisonExpression	×
20	from evadb.expression.constant_value_expression import ConstantValueExpression	×
21	from evadb.expression.logical_expression import LogicalExpression	×
22	from evadb.expression.tuple_value_expression import TupleValueExpression	×
23
24
25	def to_conjunction_list(	×
26	expression_tree: AbstractExpression,
27	) -> List[AbstractExpression]:
28	"""Convert expression tree to list of conjunctives
29
30	Note: It does not normalize the expression tree before extracting the conjunctives.
31
32	Args:
33	expression_tree (AbstractExpression): expression tree to transform
34
35	Returns:
36	List[AbstractExpression]: list of conjunctives
37
38	Example:
39	to_conjunction_list(AND(AND(a,b), OR(c,d))): [a, b, OR(c,d)]
40	to_conjunction_list(OR(AND(a,b), c)): [OR(AND(a,b), c)]
41	returns the original expression, does not normalize
42	"""
43	expression_list = []	×
44	if expression_tree.etype == ExpressionType.LOGICAL_AND:	×
45	expression_list.extend(to_conjunction_list(expression_tree.children[0]))	×
46	expression_list.extend(to_conjunction_list(expression_tree.children[1]))	×
47	else:
48	expression_list.append(expression_tree)	×
49
50	return expression_list	×
51
52
53	def conjunction_list_to_expression_tree(	×
54	expression_list: List[AbstractExpression],
55	) -> AbstractExpression:
56	"""Convert expression list to expression tree using conjunction connector
57
58	[a, b, c] -> AND( AND(a, b), c)
59	Args:
60	expression_list (List[AbstractExpression]): list of conjunctives
61
62	Returns:
63	AbstractExpression: expression tree
64
65	Example:
66	conjunction_list_to_expression_tree([a, b, c] ): AND( AND(a, b), c)
67	"""
68	if len(expression_list) == 0:	×
69	return None	×
70	prev_expr = expression_list[0]	×
71	for expr in expression_list[1:]:	×
72	if expr is not None:	×
73	prev_expr = LogicalExpression(ExpressionType.LOGICAL_AND, prev_expr, expr)	×
74	return prev_expr	×
75
76
77	def extract_range_list_from_comparison_expr(	×
78	expr: ComparisonExpression, lower_bound: int, upper_bound: int
79	) -> List:
80	"""Extracts the valid range from the comparison expression.
81
82	The expression needs to be amongst <, >, <=, >=, =, !=.
83
84	Args:
85	expr (ComparisonExpression): comparison expression with two children
86	that are leaf expression nodes. If the input does not match,
87	the function return False
88	lower_bound (int): lower bound of the comparison predicate
89	upper_bound (int): upper bound of the comparison predicate
90
91	Returns:
92	List[Tuple(int)]: list of valid ranges
93
94	Raises:
95	RuntimeError: Invalid expression
96
97	Example:
98	extract_range_from_comparison_expr(id < 10, 0, inf): True, [(0,9)]
99	"""
100
101	if not isinstance(expr, ComparisonExpression):	×
102	raise RuntimeError(f"Expected Comparison Expression, got {type(expr)}")
103	left = expr.children[0]	×
104	right = expr.children[1]	×
105	expr_type = expr.etype	×
106	val = None	×
107	const_first = False	×
108	if isinstance(left, TupleValueExpression) and isinstance(	×
109	right, ConstantValueExpression
110	):
111	val = right.value	×
112	elif isinstance(left, ConstantValueExpression) and isinstance(	×
113	right, TupleValueExpression
114	):
115	val = left.value	×
116	const_first = True	×
117	else:
118	raise RuntimeError(
119	f"Only supports extracting range from Comparison Expression \
120	with two children TupleValueExpression and \
121	ConstantValueExpression, got {left} and {right}"
122	)
123
124	if const_first:	×
125	if expr_type is ExpressionType.COMPARE_GREATER:	×
126	expr_type = ExpressionType.COMPARE_LESSER	×
127	elif expr_type is ExpressionType.COMPARE_LESSER:	×
128	expr_type = ExpressionType.COMPARE_GREATER	×
129	elif expr_type is ExpressionType.COMPARE_GEQ:	×
130	expr_type = ExpressionType.COMPARE_LEQ	×
131	elif expr_type is ExpressionType.COMPARE_LEQ:	×
132	expr_type = ExpressionType.COMPARE_GEQ	×
133
134	valid_ranges = []	×
135	if expr_type == ExpressionType.COMPARE_EQUAL:	×
136	valid_ranges.append((val, val))	×
137	elif expr_type == ExpressionType.COMPARE_NEQ:	×
138	valid_ranges.append((lower_bound, val - 1))	×
139	valid_ranges.append((val + 1, upper_bound))	×
140	elif expr_type == ExpressionType.COMPARE_GREATER:	×
141	valid_ranges.append((val + 1, upper_bound))	×
142	elif expr_type == ExpressionType.COMPARE_GEQ:	×
143	valid_ranges.append((val, upper_bound))	×
144	elif expr_type == ExpressionType.COMPARE_LESSER:	×
145	valid_ranges.append((lower_bound, val - 1))	×
146	elif expr_type == ExpressionType.COMPARE_LEQ:	×
147	valid_ranges.append((lower_bound, val))	×
148	else:
149	raise RuntimeError(f"Unsupported Expression Type {expr_type}")
150	return valid_ranges	×
151
152
153	def extract_range_list_from_predicate(	×
154	predicate: AbstractExpression, lower_bound: int, upper_bound: int
155	) -> List:
156	"""The function converts the range predicate on the column in the
157	`predicate` to a list of [(start_1, end_1), ... ] pairs.
158
159	It assumes the predicate contains conditions on only one column.
160	It is the responsibility of the caller that `predicate` does not contains conditions on multiple columns.
161
162	Args:
163	predicate (AbstractExpression): Input predicate to extract
164	valid ranges. The predicate should contain conditions on
165	only one columns, else it raise error.
166	lower_bound (int): lower bound of the comparison predicate
167	upper_bound (int): upper bound of the comparison predicate
168
169	Returns:
170	List[Tuple]: list of (start, end) pairs of valid ranges
171
172	Example:
173	id < 10 : [(0, 9)]
174	id > 5 AND id < 10 : [(6, 9)]
175	id < 10 OR id >20 : [(0, 9), (21, Inf)]
176	"""
177
178	def overlap(x, y):	×
179	overlap = (max(x[0], y[0]), min(x[1], y[1]))	×
180	if overlap[0] <= overlap[1]:	×
181	return overlap	×
182
183	def union(ranges: List):	×
184	# union all the ranges
185	reduced_list = []	×
186	for begin, end in sorted(ranges):	×
187	if reduced_list and reduced_list[-1][1] >= begin - 1:	×
188	reduced_list[-1] = (	×
189	reduced_list[-1][0],
190	max(reduced_list[-1][1], end),
191	)
192	else:
193	reduced_list.append((begin, end))	×
194	return reduced_list	×
195
196	if predicate.etype == ExpressionType.LOGICAL_AND:	×
197	left_ranges = extract_range_list_from_predicate(	×
198	predicate.children[0], lower_bound, upper_bound
199	)
200	right_ranges = extract_range_list_from_predicate(	×
201	predicate.children[1], lower_bound, upper_bound
202	)
203	valid_overlaps = []	×
204	for left_range in left_ranges:	×
205	for right_range in right_ranges:	×
206	over = overlap(left_range, right_range)	×
207	if over:	×
208	valid_overlaps.append(over)	×
209	return union(valid_overlaps)	×
210
211	elif predicate.etype == ExpressionType.LOGICAL_OR:	×
212	left_ranges = extract_range_list_from_predicate(	×
213	predicate.children[0], lower_bound, upper_bound
214	)
215	right_ranges = extract_range_list_from_predicate(	×
216	predicate.children[1], lower_bound, upper_bound
217	)
218	return union(left_ranges + right_ranges)	×
219
220	elif isinstance(predicate, ComparisonExpression):	×
221	return union(	×
222	extract_range_list_from_comparison_expr(predicate, lower_bound, upper_bound)
223	)
224
225	else:
226	raise RuntimeError(f"Contains unsupported expression {type(predicate)}")
227
228
229	def get_columns_in_predicate(predicate: AbstractExpression) -> Set[str]:	×
230	"""Get columns accessed in the predicate
231
232	Args:
233	predicate (AbstractExpression): input predicate
234
235	Returns:
236	Set[str]: list of column aliases used in the predicate
237	"""
238	if isinstance(predicate, TupleValueExpression):	×
239	return set([predicate.col_alias])	×
240	cols = set()	×
241	for child in predicate.children:	×
242	child_cols = get_columns_in_predicate(child)	×
243	if len(child_cols):	×
244	cols.update(child_cols)	×
245	return cols	×
246
247
248	def contains_single_column(predicate: AbstractExpression, column: str = None) -> bool:	×
249	"""Checks if predicate contains conditions on single predicate
250
251	Args:
252	predicate (AbstractExpression): predicate expression
253	column_alias (str): check if the single column matches
254	the input column_alias
255	Returns:
256	bool: True, if contains single predicate, else False
257	if predicate is None, return False
258	"""
259
260	if not predicate:	×
261	return False	×
262
263	cols = get_columns_in_predicate(predicate)	×
264	if len(cols) == 1:	×
265	if column is None:	×
266	return True	×
267	pred_col = cols.pop()	×
268	if pred_col == column:	×
269	return True	×
270	return False	×
271
272
273	def is_simple_predicate(predicate: AbstractExpression) -> bool:	×
274	"""Checks if conditions in the predicate are on a single column and
275	only contains LogicalExpression, ComparisonExpression,
276	TupleValueExpression or ConstantValueExpression
277
278	Args:
279	predicate (AbstractExpression): predicate expression to check
280
281	Returns:
282	bool: True, if it is a simple predicate, else False
283	"""
284
285	def _has_simple_expressions(expr):	×
286	simple = type(expr) in simple_expressions	×
287	for child in expr.children:	×
288	simple = simple and _has_simple_expressions(child)	×
289	return simple	×
290
291	simple_expressions = [	×
292	LogicalExpression,
293	ComparisonExpression,
294	TupleValueExpression,
295	ConstantValueExpression,
296	]
297
298	return _has_simple_expressions(predicate) and contains_single_column(predicate)	×

georgia-tech-db / eva / #758

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous