Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Survival Tree01:19

Survival Tree

236
Survival trees are a non-parametric method used in survival analysis to model the relationship between a set of covariates and the time until an event of interest occurs, often referred to as the "time-to-event" or "survival time." This method is particularly useful when dealing with censored data, where the event has not occurred for some individuals by the end of the study period, or when the exact time of the event is unknown.
 Building a Survival Tree
Constructing a...
236
Simple Trusses01:21

Simple Trusses

2.4K
A truss is a structural framework consisting of slender members connected at joints, designed to support external loads while minimizing material usage and weight. Simple trusses are a type of planar truss where all members lie within a single two-dimensional plane.
The most basic planar truss is a simple truss with three members arranged in a triangular formation. This triangular truss is inherently stable and rigid due to its geometry, making it an ideal starting point for creating more...
2.4K
Theorems of Pappus and Guldinus: Problem Solving01:12

Theorems of Pappus and Guldinus: Problem Solving

906
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
906
Design Example: Traverse Angle Computations01:25

Design Example: Traverse Angle Computations

200
Traverse angle computations are a critical component of surveying, used to compute the internal angles within a closed traverse. A traverse consists of a series of connected lines forming a closed loop, often used for land boundary delineation or mapping. Calculating the internal angles ensures accuracy in the traverse geometry and is essential for checking survey data integrity.The process begins with known azimuths and bearings of the traverse sides. Internal angles at each vertex are...
200
Phylogenetic Trees03:21

Phylogenetic Trees

48.6K
Phylogenetic trees come in many forms. It matters in which sequence the organisms are arranged from the bottom to the top of the tree, but the branches can rotate at their nodes without altering the information. The lines connecting individual nodes can be straight, angled, or even curved.
48.6K
Castigliano's Theorem: Problem Solving01:14

Castigliano's Theorem: Problem Solving

980
The deflection of a simply supported beam that carries a central point load can be analyzed using structural mechanics principles, particularly by applying Castigliano's theorem. This theorem relates the displacement at the load application point to the partial derivatives of the strain energy in the structure. The simply supported beam with a point load at its center has symmetric reaction forces at the supports, each bearing half of the load. The bending moment at any point along the beam is...
980

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same journal

FullSynesth: Syntenic Reconciliation of a Set of Consistent Gene Trees.

Theory of computing systems·2026
Same journal

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths.

Theory of computing systems·2026
Same journal

The Ground-Set-Cost Budgeted Maximum Coverage Problem.

Theory of computing systems·2025
Same journal

Rudin-Shapiro Sums Via Automata Theory and Logic.

Theory of computing systems·2025
Same journal

Prediction and MDL for infinite sequences.

Theory of computing systems·2024
Same journal

On Polynomial Recursive Sequences.

Theory of computing systems·2024

Related Experiment Video

Updated: Nov 17, 2025

A Practical Guide to Phylogenetics for Nonexperts
12:00

A Practical Guide to Phylogenetics for Nonexperts

Published on: February 5, 2014

35.7K

Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection.

Stefan Mengel1, Sebastian Skritek2

  • 1CRIL, CNRS & Université d'Artois, Lens, France.

Theory of Computing Systems
|February 11, 2021
PubMed
Summary
This summary is machine-generated.

This study characterizes tractable query classes for well-designed pattern trees with projection, crucial for incomplete data in Semantic Web settings. It extends previous work by including projection, offering a complete description for simple trees and new cases for non-simple ones.

Keywords:
Characterizing tractable classesFPTQuery evaluationSPARQLWell-designed pattern trees

More Related Videos

Author Spotlight: Advancements in X-ray CT Tool Chain for Tree Core Analysis
06:56

Author Spotlight: Advancements in X-ray CT Tool Chain for Tree Core Analysis

Published on: September 22, 2023

1.4K
A Simple Protocol for Mapping the Plant Root System Architecture Traits
11:09

A Simple Protocol for Mapping the Plant Root System Architecture Traits

Published on: February 10, 2023

3.3K

Related Experiment Videos

Last Updated: Nov 17, 2025

A Practical Guide to Phylogenetics for Nonexperts
12:00

A Practical Guide to Phylogenetics for Nonexperts

Published on: February 5, 2014

35.7K
Author Spotlight: Advancements in X-ray CT Tool Chain for Tree Core Analysis
06:56

Author Spotlight: Advancements in X-ray CT Tool Chain for Tree Core Analysis

Published on: September 22, 2023

1.4K
A Simple Protocol for Mapping the Plant Root System Architecture Traits
11:09

A Simple Protocol for Mapping the Plant Root System Architecture Traits

Published on: February 10, 2023

3.3K

Area of Science:

  • Database Theory
  • Query Optimization
  • Semantic Web Technologies

Background:

  • Well-designed pattern trees extend conjunctive queries with optional parts, vital for handling incomplete data.
  • Previous research characterized tractable pattern trees but excluded query projection.
  • Projection is a key feature in many database query languages.

Purpose of the Study:

  • To characterize tractable classes of simple well-designed pattern trees that include projection.
  • To extend this characterization to non-simple pattern trees, capturing additional tractable cases.
  • To provide a complete description of tractable queries within the well-designed {AND, OPTIONAL}-SPARQL fragment based on graph structures.

Main Methods:

  • Analyzing the structural properties of well-designed pattern trees.
  • Applying complexity theory to determine tractability criteria for queries with projection.
  • Developing characterizations for both simple and non-simple pattern trees.

Main Results:

  • A characterization of all tractable classes of simple well-designed pattern trees with projection was established.
  • The tractability criteria were extended to encompass certain non-simple pattern trees.
  • This work provides a comprehensive understanding of tractable queries in a significant SPARQL fragment.

Conclusions:

  • The study successfully closes the gap in understanding the complexity of pattern trees by incorporating projection.
  • The findings offer a complete description of tractable queries based on graph structures for simple pattern trees.
  • The extended characterization for non-simple trees broadens the scope of efficient query evaluation in Semantic Web scenarios.