Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Conjunctive query
Résumé
In database theory, a conjunctive query is a restricted form of first-order queries using the logical conjunction operator. Many first-order queries can be written as conjunctive queries. In particular, a large part of queries issued on relational databases can be expressed in this way. Conjunctive queries also have a number of desirable theoretical properties that larger classes of queries (e.g., the relational algebra queries) do not share.
The conjunctive queries are the fragment of (domain independent) first-order logic given by the set of
formulae that can be constructed from atomic formulae using conjunction ∧ and
existential quantification ∃, but not using disjunction ∨, negation ¬,
or universal quantification ∀.
Each such formula can be rewritten (efficiently) into an equivalent formula in prenex normal form, thus this form is usually simply assumed.
Thus conjunctive queries are of the following general form:
with the free variables being called distinguished variables, and the bound variables being called undistinguished variables. are atomic formulae.
As an example of why the restriction to domain independent first-order logic is important, consider , which is not domain independent; see Codd's theorem. This formula cannot be implemented in the select-project-join fragment of relational algebra, and hence should not be considered a conjunctive query.
Conjunctive queries can express a large proportion of queries that are frequently issued on relational databases. To give an example, imagine a relational database for storing information about students, their address, the courses they take and their gender. Finding all male students and their addresses who attend a course that is also attended by a female student is expressed by the following conjunctive query:
(student, address) . ∃ (student2, course) .
attends(student, course) ∧ gender(student, 'male') ∧
attends(student2, course) ∧
gender(student2, 'female') ∧ lives(student, address)
Note that since the only entity of interest is the male student and his address, these are the only distinguished variables, while the variables course, student2 are only existentially quantified, i.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.