Show simple item record

dc.contributor.authorStafylopatis, Andreas
dc.contributor.authorPaschos, Vangelis
dc.contributor.authorFernandez de la Vega, Wenceslas
dc.date.accessioned2010-04-07T10:29:46Z
dc.date.available2010-04-07T10:29:46Z
dc.date.issued1998
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3877
dc.language.isoenen
dc.subjectRelational databasesen
dc.subject.ddc005en
dc.titleAverage-case complexity for the execution of recursive definitions on relational databasesen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe execution costs of various types of database queries, expressed in terms of linear recusive definitions, are evaluated for two common query evaluation algorithms in the case where the database relations are represented by forests of labelled oriented trees. In a first stage, the execution costs are computed for a given forest. A key issue in this computation is the partition of the set of nodes in the forest into equivalence classes, the properties of which are explored. Moreover, the representation adopted is conceptually simple and provides additional results which are of interest by themselves. In a second stage, the averages of these costs, computed over all databases representable by forests with a given number of nodes, are also evaluated. Finally, the execution cost of the considered database queries is computed for the case where the underlined database relations are modelled as Hamiltonian digraphs.en
dc.relation.isversionofjnlnameActa Informatica
dc.relation.isversionofjnlvol35en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate1998-03
dc.relation.isversionofjnlpages211-243en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/s002360050119en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record